From 26d89788658df8a65eebc64eff021882efc1e819 Mon Sep 17 00:00:00 2001 From: J08nY Date: Mon, 2 Jul 2018 18:04:15 +0200 Subject: Add method for generating supersingular curves. --- README.md | 5 +++ src/exhaustive/exhaustive.c | 4 ++ src/exhaustive/supersingular.c | 44 +++++++++++++++++++++ src/exhaustive/supersingular.h | 28 +++++++++++++ src/io/cli.c | 89 ++++++++++++++++++++++++------------------ src/misc/config.h | 3 +- test/common.sh | 5 +++ test/ecgen.sh | 14 ++++++- 8 files changed, 151 insertions(+), 41 deletions(-) create mode 100644 src/exhaustive/supersingular.c create mode 100644 src/exhaustive/supersingular.h diff --git a/README.md b/README.md index c6bb216..37d6402 100644 --- a/README.md +++ b/README.md @@ -14,6 +14,7 @@ Tool for generating Elliptic curve domain parameters. #### Generation methods - `--anomalous` Generate an anomalous curve (of trace one, with field order equal to curve order). + - `--supersingular` Generate a supersingular curve. - `-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). - `-s / --ansi[=SEED]` Generate a curve from `SEED` (ANSI X9.62 verifiable procedure). @@ -196,6 +197,10 @@ Four different EC curve parameters generation methods are implemented. - [Constructing elliptic curves of prescribed order - [Broker (thesis)]](https://openaccess.leidenuniv.nl/bitstream/handle/1887/4425/Thesis.pdf) - [Generating Elliptic Curves of Prime Order - [Savas, Schmidt, Koc]](http://people.oregonstate.edu/~schmidtt/ourPapers/SavasKoc/ches01curve.pdf) +#### Supersingular curves + + - [CONSTRUCTING SUPERSINGULAR ELLIPTIC CURVES - [Broker]](https://pdfs.semanticscholar.org/56c5/5b9cf0b218f93b8d263cc9f64ccb5fb97f52.pdf) + #### Anomalous curve generation - Generates curves of order equal to field order. diff --git a/src/exhaustive/exhaustive.c b/src/exhaustive/exhaustive.c index dbc1125..5ecac24 100644 --- a/src/exhaustive/exhaustive.c +++ b/src/exhaustive/exhaustive.c @@ -20,6 +20,7 @@ #include "io/output.h" #include "misc/config.h" #include "obj/curve.h" +#include "supersingular.h" #include "util/memory.h" #include "util/timeout.h" @@ -124,6 +125,9 @@ static void exhaustive_ginit(gen_f *generators) { if (cfg->method == METHOD_ANOMALOUS) { generators[OFFSET_A] = &gen_skip; generators[OFFSET_B] = &anomalous_gen_equation; + } else if (cfg->method == METHOD_SUPERSINGULAR) { + generators[OFFSET_A] = &gen_skip; + generators[OFFSET_B] = &supersingular_gen_equation; } else if (cfg->koblitz) { switch (cfg->koblitz_value) { case 0: diff --git a/src/exhaustive/supersingular.c b/src/exhaustive/supersingular.c new file mode 100644 index 0000000..87e6786 --- /dev/null +++ b/src/exhaustive/supersingular.c @@ -0,0 +1,44 @@ +/* + * ecgen, tool for generating Elliptic curve domain parameters + * Copyright (C) 2017-2018 J08nY + */ +#include "supersingular.h" + +GENERATOR(supersingular_gen_equation) { + if (equalis(curve->field, 2)) { + return -2; + } + if (mod4(curve->field) == 3) { + curve->a = mkintmod(subis(curve->field, 1), curve->field); + curve->b = mkintmod(stoi(0), curve->field); + return 1; + } + GEN q = stoi(3); + while (mod4(q) != 3 && kronecker(curve->field, q) != -1) { + q = nextprime(q); + } + + if (equalis(q, 3)) { + curve->a = mkintmod(stoi(0), curve->field); + curve->b = mkintmod(stoi(1), curve->field); + return 1; + } else { + GEN H = polclass(negi(q), 0, 0); + GEN r = FpX_roots(H, curve->field); + GEN root = gel(r, 1); + curve->a = + Fp_div(Fp_mul(stoi(27), root, curve->field), + Fp_mul(stoi(4), Fp_sub(stoi(1728), root, curve->field), + curve->field), + curve->field); + curve->b = negi(curve->a); + return 1; + } +} + +GENERATOR(supersingular_gen_order) { + // copy field to order + curve->order = addis(curve->field, 1); + obj_insert(curve->curve, 1, curve->order); + return 1; +} diff --git a/src/exhaustive/supersingular.h b/src/exhaustive/supersingular.h new file mode 100644 index 0000000..bf7f267 --- /dev/null +++ b/src/exhaustive/supersingular.h @@ -0,0 +1,28 @@ +/* + * ecgen, tool for generating Elliptic curve domain parameters + * Copyright (C) 2017-2018 J08nY + */ +#ifndef ECGEN_EXHAUSTIVE_SUPERSINGULAR_H +#define ECGEN_EXHAUSTIVE_SUPERSINGULAR_H + +#include "misc/types.h" + +/** + * @brief + * @param curve + * @param args + * @param state + * @return + */ +GENERATOR(supersingular_gen_equation); + +/** + * @brief + * @param curve + * @param args + * @param state + * @return + */ +GENERATOR(supersingular_gen_order); + +#endif // ECGEN_EXHAUSTIVE_SUPERSINGULAR_H diff --git a/src/io/cli.c b/src/io/cli.c index 32888a8..aa9628a 100644 --- a/src/io/cli.c +++ b/src/io/cli.c @@ -40,50 +40,52 @@ enum opt_keys { OPT_ANOMALOUS, OPT_HEXCHECK, OPT_METADATA, + OPT_SUPERSINGULAR, OPT_BRAINPOOL_RFC, OPT_TWIST, }; // clang-format off struct argp_option cli_options[] = { - {0, 0, 0, 0, "Field specification:", 1}, - {"fp", OPT_FP, 0, 0, "Prime field.", 1}, - {"f2m", OPT_F2M, 0, 0, "Binary field.", 1}, + {0, 0, 0, 0, "Field specification:", 1}, + {"fp", OPT_FP, 0, 0, "Prime field.", 1}, + {"f2m", OPT_F2M, 0, 0, "Binary field.", 1}, - {0, 0, 0, 0, "Generation methods:", 2}, - {"order", OPT_ORDER, "ORDER", 0, "Generate a curve with given order (using Complex Multiplication). **NOT IMPLEMENTED**", 2}, - {"anomalous", OPT_ANOMALOUS, 0, 0, "Generate an anomalous curve (of trace one, with field order equal to curve order).", 2}, - {"ansi", OPT_ANSI, "SEED", OPTION_ARG_OPTIONAL, "Generate a curve from SEED (ANSI X9.62 verifiable procedure).", 2}, - {"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, "RANGE",OPTION_ARG_OPTIONAL, "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 methods:", 2}, + {"order", OPT_ORDER, "ORDER", 0, "Generate a curve with given order (using Complex Multiplication).", 2}, + {"supersingular", OPT_SUPERSINGULAR, 0, 0, "Generate a supersingular curve.", 2}, + {"anomalous", OPT_ANOMALOUS, 0, 0, "Generate an anomalous curve (of trace one, with field order equal to curve order).", 2}, + {"ansi", OPT_ANSI, "SEED", OPTION_ARG_OPTIONAL, "Generate a curve from SEED (ANSI X9.62 verifiable procedure).", 2}, + {"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, "RANGE", OPTION_ARG_OPTIONAL, "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, "WHAT", OPTION_ARG_OPTIONAL, "Generate a random curve (using Random approach). " - "Optionally, only generate random parameters WHAT (seed,field,a,b,equation).", 3}, - {"prime", OPT_PRIME, 0, 0, "Generate a curve with prime order.", 3}, - {"cofactor", OPT_COFACTOR, "VALUE", 0, "Generate a curve with cofactor of VALUE.", 3}, - {"koblitz", OPT_KOBLITZ, "A", OPTION_ARG_OPTIONAL, "Generate a Koblitz curve (a in {0, 1}, b = 1).", 3}, - {"unique", OPT_UNIQUE, 0, 0, "Generate a curve with only one generator.", 3}, - {"hex-check", OPT_HEXCHECK, "HEX", 0, "Check a generated curve param hex expansion for the HEX string.", 3}, - {"points", OPT_POINTS, "TYPE", 0, "Generate points of given type (random/prime/all/nonprime/none).", 3}, - {"count", OPT_COUNT, "COUNT", 0, "Generate multiple curves.", 3}, - {"metadata", OPT_METADATA, 0, 0, "Compute curve metadata " - "(j-invariant, discriminant, trace of Frobenius, embedding degree, CM discriminant).", 3}, + {0, 0, 0, 0, "Generation options:", 3}, + {"random", OPT_RANDOM, "WHAT", OPTION_ARG_OPTIONAL, "Generate a random curve (using Random approach). " + "Optionally, only generate random parameters WHAT (seed,field,a,b,equation).", 3}, + {"prime", OPT_PRIME, 0, 0, "Generate a curve with prime order.", 3}, + {"cofactor", OPT_COFACTOR, "VALUE", 0, "Generate a curve with cofactor of VALUE.", 3}, + {"koblitz", OPT_KOBLITZ, "A", OPTION_ARG_OPTIONAL, "Generate a Koblitz curve (a in {0, 1}, b = 1).", 3}, + {"unique", OPT_UNIQUE, 0, 0, "Generate a curve with only one generator.", 3}, + {"hex-check", OPT_HEXCHECK, "HEX", 0, "Check a generated curve param hex expansion for the HEX string.", 3}, + {"points", OPT_POINTS, "TYPE", 0, "Generate points of given type (random/prime/all/nonprime/none).", 3}, + {"count", OPT_COUNT, "COUNT", 0, "Generate multiple curves.", 3}, + {"metadata", OPT_METADATA, 0, 0, "Compute curve metadata " + "(j-invariant, discriminant, trace of Frobenius, embedding degree, CM discriminant).", 3}, - {0, 0, 0, 0, "Input/Output options:", 4}, - {"input", OPT_INPUT, "FILE", 0, "Input from file.", 4}, - {"output", OPT_OUTPUT, "FILE", 0, "Output into file. Overwrites any existing file!", 4}, - {"append", OPT_APPEND, 0, 0, "Append to output file (don't overwrite).", 4}, - {"verbose", OPT_VERBOSE, "FILE", OPTION_ARG_OPTIONAL, "Verbose logging (to stdout or file).", 4}, + {0, 0, 0, 0, "Input/Output options:", 4}, + {"input", OPT_INPUT, "FILE", 0, "Input from file.", 4}, + {"output", OPT_OUTPUT, "FILE", 0, "Output into file. Overwrites any existing file!", 4}, + {"append", OPT_APPEND, 0, 0, "Append to output file (don't overwrite).", 4}, + {"verbose", OPT_VERBOSE, "FILE", OPTION_ARG_OPTIONAL, "Verbose logging (to stdout or file).", 4}, - {0, 0, 0, 0, "Other:", 5}, - {"data-dir", OPT_DATADIR, "DIR", 0, "Set PARI/GP data directory (containing seadata package).", 5}, - {"memory", OPT_MEMORY, "SIZE", 0, "Use PARI stack of SIZE (can have suffix k/m/g).", 5}, - {"threads", OPT_THREADS, "NUM", 0, "Use NUM threads.", 5}, - {"thread-stack", OPT_TSTACK, "SIZE", 0, "Use PARI stack of SIZE (per thread, can have suffix k/m/g).", 5}, - {"timeout", OPT_TIMEOUT, "TIME", 0, "Timeout computation of a curve parameter after TIME (can have suffix s/m/h/d).", 5}, + {0, 0, 0, 0, "Other:", 5}, + {"data-dir", OPT_DATADIR, "DIR", 0, "Set PARI/GP data directory (containing seadata package).", 5}, + {"memory", OPT_MEMORY, "SIZE", 0, "Use PARI stack of SIZE (can have suffix k/m/g).", 5}, + {"threads", OPT_THREADS, "NUM", 0, "Use NUM threads.", 5}, + {"thread-stack", OPT_TSTACK, "SIZE", 0, "Use PARI stack of SIZE (per thread, can have suffix k/m/g).", 5}, + {"timeout", OPT_TIMEOUT, "TIME", 0, "Timeout computation of a curve parameter after TIME (can have suffix s/m/h/d).", 5}, {0} }; // clang-format on @@ -141,6 +143,7 @@ static void cli_end(struct argp_state *state) { case METHOD_SEED: case METHOD_INVALID: case METHOD_TWIST: + case METHOD_SUPERSINGULAR: break; default: printf("%u\n", cfg->method); @@ -158,6 +161,11 @@ static void cli_end(struct argp_state *state) { argp_failure(state, 1, 0, "Complex multiplication only creates prime field curves."); } + if (cfg->method == METHOD_SUPERSINGULAR && cfg->field == FIELD_BINARY) { + argp_failure(state, 1, 0, + "Can only generate supersingular curves over prime fields " + "currently."); + } // default values if (!cfg->count) { cfg->count = 1; @@ -187,7 +195,7 @@ error_t cli_parse(int key, char *arg, struct argp_state *state) { cfg->field |= FIELD_BINARY; break; - /* Generation method */ + /* Generation method */ case OPT_INVALID: cfg->method |= METHOD_INVALID; if (arg) { @@ -207,6 +215,9 @@ error_t cli_parse(int key, char *arg, struct argp_state *state) { case OPT_ANOMALOUS: cfg->method |= METHOD_ANOMALOUS; break; + case OPT_SUPERSINGULAR: + cfg->method |= METHOD_SUPERSINGULAR; + break; case OPT_ANSI: cfg->method |= METHOD_SEED; cfg->seed_algo = SEED_ANSI; @@ -247,7 +258,7 @@ error_t cli_parse(int key, char *arg, struct argp_state *state) { cfg->method |= METHOD_TWIST; break; - /* Generation options */ + /* Generation options */ case OPT_COUNT: cfg->count = strtoul(arg, NULL, 10); break; @@ -336,7 +347,7 @@ error_t cli_parse(int key, char *arg, struct argp_state *state) { } break; } - /* IO options */ + /* IO options */ case OPT_INPUT: cfg->input = arg; break; @@ -353,7 +364,7 @@ error_t cli_parse(int key, char *arg, struct argp_state *state) { } break; - /* Misc options */ + /* Misc options */ case OPT_DATADIR: cfg->datadir = arg; break; @@ -381,7 +392,7 @@ error_t cli_parse(int key, char *arg, struct argp_state *state) { } break; - /* Args */ + /* Args */ case ARGP_KEY_ARG: if (state->arg_num >= 1) { argp_usage(state); diff --git a/src/misc/config.h b/src/misc/config.h index 55a3cdd..7db13de 100644 --- a/src/misc/config.h +++ b/src/misc/config.h @@ -47,7 +47,8 @@ typedef enum { METHOD_ANOMALOUS = 1 << 1, METHOD_SEED = 1 << 2, METHOD_INVALID = 1 << 3, - METHOD_TWIST = 1 << 4 + METHOD_TWIST = 1 << 4, + METHOD_SUPERSINGULAR = 1 << 5 } method_e; /** diff --git a/test/common.sh b/test/common.sh index 5e2cb38..c7fbb6e 100644 --- a/test/common.sh +++ b/test/common.sh @@ -35,4 +35,9 @@ strip_num() { num="${num:2}" num="${num##+(0)}" echo $num +} + +canonical_num() { + num=$(strip_num "$1") + echo "ibase=16;${num^^}" | bc } \ No newline at end of file diff --git a/test/ecgen.sh b/test/ecgen.sh index 5de7f34..3a94564 100755 --- a/test/ecgen.sh +++ b/test/ecgen.sh @@ -93,12 +93,22 @@ function brainpool() { function anomalous() { start_test assert_raises "${ecgen} --fp --anomalous -r 20" - out=$(${ecgen} --fp -tjson --anomalous -r 20 2>/dev/null) + out=$(${ecgen} --fp --anomalous -r 20 2>/dev/null) p=$(echo $out | ${JSON} -x field\",\"p | cut -f 2) order=$(echo $out | ${JSON} -x ^0,\"order\" | cut -f 2) assert "strip_num $p" $(strip_num $order) } +function supersingular() { + start_test + assert_raises "${ecgen} --fp --supersingular -r 20" + out=$(${ecgen} --fp --supersingular -r 20 2>/dev/null) + p=$(echo $out | ${JSON} -x field\",\"p | cut -f 2) + order=$(echo $out | ${JSON} -x ^0,\"order\" | cut -f 2) + order_m1=$(echo $(canonical_num $order) - 1 | bc) + assert "canonical_num $p" $order_m1 +} + function invalid() { start_test assert_raises "${ecgen} --fp -r -i 10" @@ -133,6 +143,7 @@ function cli() { assert_raises "${ecgen} --ansi=01234 --fp 10" 1 assert_raises "${ecgen} --hex-check=not_hex --fp 10" 1 assert_raises "${ecgen} abc" 1 + assert_raises "${ecgen} --supersingular --f2m 10" 1 } function hex() { @@ -171,6 +182,7 @@ exhaustive ansix962 brainpool anomalous +supersingular invalid twist cli -- cgit v1.2.3-70-g09d2