8 files changed, 151 insertions, 41 deletions

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