From 5307f9318a01ed29a11202ad0915efae9dec44d0 Mon Sep 17 00:00:00 2001 From: J08nY Date: Tue, 17 Oct 2017 00:16:37 +0200 Subject: Add several check_fs for standard security requirements. - Check for trace one(anomalous) curve, check for multiplicative transfer(embedding degree), factors of generator order and cm discriminant. --- src/exhaustive/arg.h | 1 + src/gen/gens.c | 40 +++++++++++++++ src/gen/gens.h | 18 +++++++ src/gen/order.c | 63 ++++++++++++++++++++++- src/gen/order.h | 24 ++++++++- test/src/gen/test_field.c | 18 +------ test/src/gen/test_gens.c | 128 ++++++++++++++++++++++++++++++++++++++++++++++ test/src/gen/test_order.c | 8 +++ test/src/test/io.c | 14 +++++ test/src/test/io.h | 13 +++++ 10 files changed, 309 insertions(+), 18 deletions(-) create mode 100644 test/src/gen/test_gens.c create mode 100644 test/src/gen/test_order.c create mode 100644 test/src/test/io.c create mode 100644 test/src/test/io.h diff --git a/src/exhaustive/arg.h b/src/exhaustive/arg.h index 0b10715..62cafd0 100644 --- a/src/exhaustive/arg.h +++ b/src/exhaustive/arg.h @@ -8,6 +8,7 @@ #ifndef ECGEN_ARG_H #define ECGEN_ARG_H +#include "io/output.h" #include "misc/types.h" #define HAS_ARG(args) \ diff --git a/src/gen/gens.c b/src/gen/gens.c index f5f9fcb..d40de67 100644 --- a/src/gen/gens.c +++ b/src/gen/gens.c @@ -3,6 +3,8 @@ * Copyright (C) 2017 J08nY */ #include "gens.h" +#include +#include "exhaustive/arg.h" #include "point.h" static int gens_put(curve_t *curve, GEN generators, long len) { @@ -37,6 +39,44 @@ GENERATOR(gens_gen_one) { return gens_put(curve, generators, len); } +CHECK(gens_check_anomalous) { + if (cfg->field == FIELD_BINARY) return 1; + pari_sp ltop = avma; + for (size_t i = 0; i < curve->ngens; ++i) { + if (mpcmp(curve->field, curve->generators[i]->order) == 0) { + avma = ltop; + return -5; + } + } + return 1; +} + +CHECK(gens_check_embedding) { + HAS_ARG(args); + if (cfg->field == FIELD_BINARY) return 1; + pari_sp ltop = avma; + + const char *min_degree = args->args; + GEN mind = strtoi(min_degree); + + for (size_t i = 0; i < curve->ngens; ++i) { + GEN power = gen_0; + GEN pm; + do { + power = addii(power, gen_1); + GEN ppow = powii(curve->field, power); + pm = subii(ppow, gen_1); + } while (!dvdii(pm, curve->generators[i]->order)); + + if (mpcmp(power, mind) <= 0) { + avma = ltop; + return -5; + } + } + avma = ltop; + return 1; +} + UNROLL(gens_unroll) { if (curve->generators) { points_free_deep(&curve->generators, curve->ngens); diff --git a/src/gen/gens.h b/src/gen/gens.h index ace1a88..18c9815 100644 --- a/src/gen/gens.h +++ b/src/gen/gens.h @@ -29,6 +29,24 @@ GENERATOR(gens_gen_any); */ GENERATOR(gens_gen_one); +/** + * + * @param curve + * @param args + * @param state + * @return + */ +CHECK(gens_check_anomalous); + +/** + * + * @param curve + * @param args + * @param state + * @return + */ +CHECK(gens_check_embedding); + /** * UNROLL(unroll_f) * diff --git a/src/gen/order.c b/src/gen/order.c index 1ad7a93..92b1489 100644 --- a/src/gen/order.c +++ b/src/gen/order.c @@ -3,9 +3,9 @@ * Copyright (C) 2017 J08nY */ #include "order.h" +#include #include "exhaustive/arg.h" #include "io/input.h" -#include "io/output.h" GENERATOR(order_gen_input) { pari_sp ltop = avma; @@ -92,3 +92,64 @@ GENERATOR(order_gen_prime) { return 1; } } + +CHECK(order_check_pohlig_hellman) { + HAS_ARG(args); + pari_sp ltop = avma; + + const char *min_fact = args->args; + GEN minf = strtoi(min_fact); + + GEN factors = factor(curve->order); + GEN primes = gel(factors, 1); + + long len = glength(primes); + if (mpcmp(gel(primes, len), minf) <= 0) { + avma = ltop; + return -4; + } else { + avma = ltop; + return 1; + } +} + +CHECK(order_check_discriminant) { + HAS_ARG(args); + if (cfg->field == FIELD_BINARY) return 1; + pari_sp ltop = avma; + + const char *min_disc = args->args; + GEN mind = strtoi(min_disc); + + GEN t = negi(subii(curve->order, addii(curve->field, gen_1))); + GEN tp = subii(sqri(t), mulis(curve->field, 4)); + GEN tp_factors = factor(tp); + + GEN tp_primes = gel(tp_factors, 1); + GEN tp_pows = gel(tp_factors, 2); + long tp_pow_len = glength(tp_pows); + GEN max_value = gen_1; + for (long i = 1; i <= tp_pow_len; ++i) { + if (!dvdis(gel(tp_pows, i), 2)) { + continue; + } + + GEN value = powii(gel(tp_primes, i), gel(tp_pows, i)); + if (mpcmp(max_value, value) < 0) { + max_value = value; + } + } + GEN s = max_value; + + GEN D = divii(tp, s); + if (mod4(D) != 1) { + D = mulis(D, 4); + } + + if (mpcmp(D, mind) <= 0) { + avma = ltop; + return -4; + } + avma = ltop; + return 1; +} \ No newline at end of file diff --git a/src/gen/order.h b/src/gen/order.h index da06de5..bd1a204 100644 --- a/src/gen/order.h +++ b/src/gen/order.h @@ -16,7 +16,7 @@ * * @param curve A curve_t being generated * @param args Current optional generator argument - * @return state diff + * @param state * @return state diff */ GENERATOR(order_gen_input); @@ -28,6 +28,7 @@ GENERATOR(order_gen_input); * * @param curve A curve_t being generated * @param args Current optional generator argument + * @param state * @return state diff */ GENERATOR(order_gen_any); @@ -38,6 +39,7 @@ GENERATOR(order_gen_any); * * @param curve A curve_t being generated * @param args unused + * @param state * @return state diff */ GENERATOR(order_gen_sea); @@ -47,6 +49,7 @@ GENERATOR(order_gen_sea); * * @param curve A curve_t being generated * @param args pari_ulong passed to ellsea(curve, smallfact) + * @param state * @return state diff */ GENERATOR(order_gen_smallfact); @@ -59,8 +62,27 @@ GENERATOR(order_gen_smallfact); * * @param curve A curve_t being generated * @param args unused + * @param state * @return state diff */ GENERATOR(order_gen_prime); +/** + * + * @param curve + * @param args + * @param state + * @return + */ +CHECK(order_check_pohlig_hellman); + +/** + * + * @param curve + * @param args + * @param state + * @return + */ +CHECK(order_check_discriminant); + #endif // ECGEN_ORDER_H diff --git a/test/src/gen/test_field.c b/test/src/gen/test_field.c index fb1f1e3..81bd1ca 100644 --- a/test/src/gen/test_field.c +++ b/test/src/gen/test_field.c @@ -6,23 +6,9 @@ #include "gen/field.h" #include "math/poly.h" #include "misc/types.h" -#include "test/default.h" -#include "test/input.h" -#include "test/output.h" - -void field_setup() { - default_setup(); - input_setup(); - output_setup(); -} - -void field_teardown() { - default_teardown(); - input_teardown(); - output_teardown(); -} +#include "test/io.h" -TestSuite(field, .init = field_setup, .fini = field_teardown); +TestSuite(field, .init = io_setup, .fini = io_teardown); Test(field, test_field_gen_random_fp) { curve_t curve = {0}; diff --git a/test/src/gen/test_gens.c b/test/src/gen/test_gens.c new file mode 100644 index 0000000..2092aed --- /dev/null +++ b/test/src/gen/test_gens.c @@ -0,0 +1,128 @@ +/* + * ecgen, tool for generating Elliptic curve domain parameters + * Copyright (C) 2017 J08nY + */ +#include +#include "exhaustive/arg.h" +#include "gen/gens.h" +#include "test/io.h" + +TestSuite(gens, .init = io_setup, .fini = io_teardown); + +Test(gens, test_gens_gen_any) { + cfg->field = FIELD_PRIME; + curve_t curve = {.field = stoi(19), + .a = mkintmodu(3, 19), + .b = mkintmodu(5, 19), + .curve = ellinit(mkvec2(stoi(3), stoi(5)), stoi(19), 0), + .order = stoi(16)}; + + pari_sp to = avma; + int ret = gens_gen_any(&curve, NULL, OFFSET_GENERATORS); + pari_sp from = avma; + cr_assert_eq(ret, 1, ); + cr_assert_not_null(curve.generators, ); + cr_assert_eq(curve.ngens, 1, ); + gens_unroll(&curve, from, to); + + memset(&curve, 0, sizeof(curve_t)); + + curve.field = stoi(29); + curve.a = mkintmodu(5, 29); + curve.b = mkintmodu(1, 29); + curve.curve = ellinit(mkvec2(stoi(5), stoi(1)), stoi(29), 0); + curve.order = stoi(32); + + ret = gens_gen_any(&curve, NULL, OFFSET_GENERATORS); + cr_assert_eq(ret, 1, ); + cr_assert_not_null(curve.generators, ); + cr_assert_eq(curve.ngens, 2, ); +} + +Test(gens, test_gens_gen_one) { + cfg->field = FIELD_PRIME; + curve_t curve = {.field = stoi(19), + .a = mkintmodu(3, 19), + .b = mkintmodu(5, 19), + .curve = ellinit(mkvec2(stoi(3), stoi(5)), stoi(19), 0), + .order = stoi(16)}; + + pari_sp to = avma; + int ret = gens_gen_one(&curve, NULL, OFFSET_GENERATORS); + pari_sp from = avma; + cr_assert_eq(ret, 1, ); + cr_assert_not_null(curve.generators, ); + cr_assert_eq(curve.ngens, 1, ); + gens_unroll(&curve, from, to); + + memset(&curve, 0, sizeof(curve_t)); + + curve.field = stoi(29); + curve.a = mkintmodu(5, 29); + curve.b = mkintmodu(1, 29); + curve.curve = ellinit(mkvec2(stoi(5), stoi(1)), stoi(29), 0); + curve.order = stoi(32); + + ret = gens_gen_one(&curve, NULL, OFFSET_GENERATORS); + cr_assert_eq(ret, -5, ); + cr_assert_null(curve.generators, ); +} + +Test(gens, test_gens_check_anomalous) { + cfg->field = FIELD_PRIME; + curve_t curve = { + .field = stoi(19), + .a = mkintmodu(3, 19), + .b = mkintmodu(6, 19), + .curve = ellinit(mkvec2(stoi(3), stoi(6)), stoi(19), 0), + .order = stoi(16), + }; + point_t gen = {.point = mkvec2(mkintmodu(4, 19), mkintmodu(14, 19)), + .order = stoi(16)}; + point_t *generators[1] = {&gen}; + curve.generators = generators; + curve.ngens = 1; + + int ret = gens_check_anomalous(&curve, NULL, OFFSET_GENERATORS); + cr_assert_eq(ret, 1, ); + + memset(&curve, 0, sizeof(curve_t)); + + curve.field = stoi(23); + curve.a = mkintmodu(5, 23); + curve.b = mkintmodu(14, 23); + curve.curve = ellinit(mkvec2(stoi(5), stoi(14)), stoi(23), 0); + curve.order = stoi(23); + gen.point = mkvec2(mkintmodu(20, 23), mkintmodu(8, 23)); + gen.order = stoi(23); + gen.cofactor = stoi(1); + curve.generators = generators; + curve.ngens = 1; + + ret = gens_check_anomalous(&curve, NULL, OFFSET_GENERATORS); + cr_assert_eq(ret, -5, ); +} + +Test(gens, test_gens_check_embedding) { + cfg->field = FIELD_PRIME; + curve_t curve = { + .field = stoi(19), + .a = mkintmodu(3, 19), + .b = mkintmodu(12, 19), + .curve = ellinit(mkvec2(stoi(3), stoi(12)), stoi(19), 0), + .order = stoi(18), + }; + point_t gen1 = {.point = mkvec2(mkintmodu(1, 19), mkintmodu(4, 19)), + .order = stoi(6)}; + point_t gen2 = {.point = mkvec2(mkintmodu(10, 19), mkintmodu(4, 19)), + .order = stoi(3)}; + point_t *generators[2] = {&gen1, &gen2}; + curve.generators = generators; + curve.ngens = 2; + + char *min_degree = "5"; + arg_t arg = {.args = min_degree, .nargs = 1}; + + int ret = gens_check_embedding(&curve, &arg, OFFSET_GENERATORS); + cr_assert_eq(ret, -5, ); +} \ No newline at end of file diff --git a/test/src/gen/test_order.c b/test/src/gen/test_order.c new file mode 100644 index 0000000..e88724a --- /dev/null +++ b/test/src/gen/test_order.c @@ -0,0 +1,8 @@ +/* + * ecgen, tool for generating Elliptic curve domain parameters + * Copyright (C) 2017 J08nY + */ +#include +#include "test/io.h" + +TestSuite(order, .init = io_setup, .fini = io_teardown); \ No newline at end of file diff --git a/test/src/test/io.c b/test/src/test/io.c new file mode 100644 index 0000000..e53dd4b --- /dev/null +++ b/test/src/test/io.c @@ -0,0 +1,14 @@ + +#include "io.h" + +void io_setup() { + default_setup(); + input_setup(); + output_setup(); +} + +void io_teardown() { + default_teardown(); + input_teardown(); + output_teardown(); +} \ No newline at end of file diff --git a/test/src/test/io.h b/test/src/test/io.h new file mode 100644 index 0000000..dbff925 --- /dev/null +++ b/test/src/test/io.h @@ -0,0 +1,13 @@ + +#ifndef ECGEN_IO_H +#define ECGEN_IO_H + +#include "default.h" +#include "input.h" +#include "output.h" + +void io_setup(); + +void io_teardown(); + +#endif // ECGEN_IO_H -- cgit v1.2.3-70-g09d2