From cf074191532caef918fb9f502b37697094da317a Mon Sep 17 00:00:00 2001 From: J08nY Date: Thu, 18 Jan 2018 18:37:44 +0100 Subject: Add curve twists to CLI and update options in README. --- README.md | 12 ++++++++---- src/ecgen.c | 1 - src/exhaustive/exhaustive.c | 7 ++++++- src/gen/curve.c | 11 +++++++++++ src/gen/curve.h | 11 +++++++++++ src/io/cli.c | 8 +++++++- src/math/twists.c | 12 +++++++++++- src/math/twists.h | 8 +++++++- src/misc/config.h | 3 ++- test/ecgen.sh | 8 ++++++++ test/src/math/test_twists.c | 19 ++++++++++--------- 11 files changed, 81 insertions(+), 19 deletions(-) diff --git a/README.md b/README.md index 7e7d8ae..b067550 100644 --- a/README.md +++ b/README.md @@ -11,19 +11,23 @@ Tool for generating Elliptic curve domain parameters. - `--f2m` Binary field. - `--fp` Prime field. +#### Generation methods + - `--anomalous` Generate an anomalous curve (of trace one, with field order equal to curve order). + - `-b / --brainpool[=SEED]`Generate a curve using the Brainpool verifiably pseudorandom algorithm from the original paper. + - `--brainpool-rfc[=SEED]` Generate a curve using the Brainpool verifiably pseudorandom algorithm as per RFC 5639. + - `-i / --invalid` Generate a set of invalid curves, for a given curve (using Invalid curve algorithm). + - `-n / --order=ORDER` Generate a curve with given `ORDER` (using Complex Multiplication). **TODO - NOT IMPLEMENTED** + - `-s / --ansi[=SEED]` Generate a curve from `SEED` (ANSI X9.62 verifiable procedure). + - `--twist` Generate a twist of a given curve. #### Generation options - `-c / --count=COUNT` Generate multiple curves. - - `-i / --invalid` Generate a set of invalid curves, for a given curve (using Invalid curve algorithm). - `-k / --cofactor=BOUND` Generate a curve with cofactor up to `BOUND`. - - `--anomalous` Generate an anomalous curve (of trace one, with field order equal to curve order). - `-K / --koblitz[=A]` Generate a Koblitz curve (a in {0, 1}, b = 1). - - `-n / --order=ORDER` Generate a curve with given `ORDER` (using Complex Multiplication). **TODO - NOT IMPLEMENTED** - `-p / --prime` Generate a curve with prime order. - `--points=TYPE` Generate points of given `TYPE` (random/prime/all/nonprime/none). - `-r / --random` Generate a random curve (using Random approach). - - `-s / --ansi[=SEED]` Generate a curve from `SEED` (ANSI X9.62 verifiable procedure). - `-u / --unique` Generate a curve with only one generator. #### IO options diff --git a/src/ecgen.c b/src/ecgen.c index 3e5b145..4a7f94a 100644 --- a/src/ecgen.c +++ b/src/ecgen.c @@ -29,7 +29,6 @@ #include "invalid/invalid.h" #include "io/input.h" #include "io/output.h" -#include "misc/config.h" #include "util/timeout.h" const char *argp_program_version = diff --git a/src/exhaustive/exhaustive.c b/src/exhaustive/exhaustive.c index c6b54e9..fa748f5 100644 --- a/src/exhaustive/exhaustive.c +++ b/src/exhaustive/exhaustive.c @@ -3,6 +3,7 @@ * Copyright (C) 2017-2018 J08nY */ #include "exhaustive.h" +#include #include "anomalous.h" #include "ansi.h" #include "brainpool.h" @@ -166,7 +167,11 @@ static void exhaustive_ginit(gen_f *generators) { } } // setup common generators - generators[OFFSET_CURVE] = &curve_gen_any; + if (cfg->method == METHOD_TWIST) { + generators[OFFSET_CURVE] = &curve_gen_any_twist; + } else { + generators[OFFSET_CURVE] = &curve_gen_any; + } switch (cfg->points.type) { case POINTS_RANDOM: diff --git a/src/gen/curve.c b/src/gen/curve.c index 4996c28..f89044a 100644 --- a/src/gen/curve.c +++ b/src/gen/curve.c @@ -3,6 +3,7 @@ * Copyright (C) 2017-2018 J08nY */ #include "curve.h" +#include "math/twists.h" #include "point.h" #include "seed.h" #include "util/memory.h" @@ -116,6 +117,16 @@ GENERATOR(curve_gen_any) { } } +GENERATOR(curve_gen_any_twist) { + int result = curve_gen_any(curve, args, state); + if (result != 1) { + return result; + } else { + twist_rand(curve); + return 1; + } +} + CHECK(curve_check_nonzero) { if (gequal0(ell_get_disc(curve->curve))) { return -3; diff --git a/src/gen/curve.h b/src/gen/curve.h index 8b82fa9..e2316c6 100644 --- a/src/gen/curve.h +++ b/src/gen/curve.h @@ -18,10 +18,21 @@ * * @param curve A curve_t being generated * @param args unused + * @param state * @return state diff */ GENERATOR(curve_gen_any); +/** + * GENERATOR(gen_f) + * + * @param curve + * @param args + * @param state + * @return state diff + */ +GENERATOR(curve_gen_any_twist); + /** * CHECK(check_f) * Checks that the curve has non-zero discriminant. diff --git a/src/io/cli.c b/src/io/cli.c index efedb8b..46ef47a 100644 --- a/src/io/cli.c +++ b/src/io/cli.c @@ -41,7 +41,8 @@ enum opt_keys { OPT_GPGEN, OPT_GPCHECK, OPT_HEXCHECK, - OPT_BRAINPOOL_RFC + OPT_BRAINPOOL_RFC, + OPT_TWIST, }; // clang-format off @@ -57,6 +58,7 @@ struct argp_option cli_options[] = { {"brainpool", OPT_BRAINPOOL, "SEED", OPTION_ARG_OPTIONAL, "Generate a curve from SEED (Brainpool procedure).", 2}, {"brainpool-rfc", OPT_BRAINPOOL_RFC, "SEED", OPTION_ARG_OPTIONAL, "Generate a curve from SEED (Brainpool procedure, as per RFC 5639).", 2}, {"invalid", OPT_INVALID, 0, 0, "Generate a set of invalid curves, for a given curve (using Invalid curve algorithm).", 2}, + {"twist", OPT_TWIST, 0, 0, "Generate a twist of a given curve.", 2}, {0, 0, 0, 0, "Generation options:", 3}, {"random", OPT_RANDOM, 0, 0, "Generate a random curve (using Random approach).", 3}, @@ -139,6 +141,7 @@ static void cli_end(struct argp_state *state) { case METHOD_ANOMALOUS: case METHOD_SEED: case METHOD_INVALID: + case METHOD_TWIST: break; default: printf("%u\n", cfg->method); @@ -257,6 +260,9 @@ error_t cli_parse(int key, char *arg, struct argp_state *state) { cfg->seed = arg; } break; + case OPT_TWIST: + cfg->method |= METHOD_TWIST; + break; /* Generation options */ case OPT_COUNT: diff --git a/src/math/twists.c b/src/math/twists.c index 78481f4..3f1296d 100644 --- a/src/math/twists.c +++ b/src/math/twists.c @@ -3,8 +3,10 @@ * Copyright (C) 2017-2018 J08nY */ #include "twists.h" +#include "gen/point.h" +#include "gen/seed.h" -void curve_twist_rand(curve_t *to, const curve_t *of) { +void twist_rand_to(curve_t *to, const curve_t *of) { to->field = gcopy(of->field); GEN v = elltwist(of->curve, NULL); to->curve = ellinit(v, to->field, -1); @@ -15,4 +17,12 @@ void curve_twist_rand(curve_t *to, const curve_t *of) { to->a = ell_get_a2(to->curve); to->b = ell_get_a6(to->curve); } +} + +void twist_rand(curve_t *what) { + twist_rand_to(what, what); + seed_free(&what->seed); + what->order = NULL; + points_free_deep(&what->points, what->npoints); + points_free_deep(&what->generators, what->ngens); } \ No newline at end of file diff --git a/src/math/twists.h b/src/math/twists.h index 3249047..dcbdb31 100644 --- a/src/math/twists.h +++ b/src/math/twists.h @@ -12,6 +12,12 @@ * @param to The result of the twist. * @param of The curve to be twisted. */ -void curve_twist_rand(curve_t *to, const curve_t *of); +void twist_rand_to(curve_t *to, const curve_t *of); + +/** + * @brief + * @param what + */ +void twist_rand(curve_t *what); #endif // ECGEN_TWIST_H diff --git a/src/misc/config.h b/src/misc/config.h index de1c95e..367de52 100644 --- a/src/misc/config.h +++ b/src/misc/config.h @@ -33,7 +33,8 @@ typedef enum { METHOD_CM = 1 << 0, METHOD_ANOMALOUS = 1 << 1, METHOD_SEED = 1 << 2, - METHOD_INVALID = 1 << 3 + METHOD_INVALID = 1 << 3, + METHOD_TWIST } method_e; /** diff --git a/test/ecgen.sh b/test/ecgen.sh index 0621c48..006025e 100755 --- a/test/ecgen.sh +++ b/test/ecgen.sh @@ -87,6 +87,7 @@ function brainpool() { assert_raises "${ecgen} --fp -r --brainpool-rfc 10" assert_raises "${ecgen} --f2m -r --brainpool-rfc 10" 1 } + function anomalous() { start_test assert_raises "${ecgen} --fp --anomalous -r 20" @@ -106,6 +107,12 @@ function invalid() { assert_raises "${ecgen} --f2m --threads=auto -r -i -u 10" } +function twist() { + start_test + assert_raises "${ecgen} --fp --twist -r 10" + assert_raises "${ecgen} --f2m --twist -r 10" +} + function cli() { start_test assert_raises "${ecgen} --threads=a" 1 @@ -132,6 +139,7 @@ ansix962 brainpool anomalous invalid +twist cli hex end_suite ecgen \ No newline at end of file diff --git a/test/src/math/test_twists.c b/test/src/math/test_twists.c index 30bc958..8a869bf 100644 --- a/test/src/math/test_twists.c +++ b/test/src/math/test_twists.c @@ -3,8 +3,8 @@ * Copyright (C) 2017 J08nY */ #include -#include "gen/point.h" #include "gen/field.h" +#include "gen/point.h" #include "math/poly.h" #include "math/twists.h" #include "test/default.h" @@ -12,7 +12,7 @@ TestSuite(twists, .init = default_setup, .fini = default_teardown); -Test(twists, test_twist_rand_fp) { +Test(twists, test_twist_rand_to_fp) { random_init(); GEN a = mkintmodu(3, 23); GEN b = mkintmodu(4, 23); @@ -22,25 +22,26 @@ Test(twists, test_twist_rand_fp) { .curve = ellinit(mkvec2(a, b), stoi(23), -1)}; curve_t to = {0}; - curve_twist_rand(&to, &curve); + twist_rand_to(&to, &curve); cr_assert_not_null(to.a, ); cr_assert_not_null(to.b, ); cr_assert_not_null(to.field, ); cr_assert_not_null(to.curve, ); } -Test(twists, test_twist_rand_f2m) { +Test(twists, test_twist_rand_to_f2m) { random_init(); GEN field = poly_find_gen(13); GEN a = field_ielement(field, stoi(2)); GEN b = field_ielement(field, stoi(3)); - curve_t curve = {.a = a, - .b = b, - .field = field, - .curve = ellinit(mkvecn(5, gen_1, a, gen_0, gen_0, b), NULL, -1)}; + curve_t curve = { + .a = a, + .b = b, + .field = field, + .curve = ellinit(mkvecn(5, gen_1, a, gen_0, gen_0, b), NULL, -1)}; curve_t to = {0}; - curve_twist_rand(&to, &curve); + twist_rand_to(&to, &curve); cr_assert_not_null(to.a, ); cr_assert_not_null(to.b, ); cr_assert_not_null(to.field, ); -- cgit v1.2.3-70-g09d2