aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--README.md2
-rw-r--r--src/exhaustive/exhaustive.c2
-rw-r--r--src/exhaustive/family.c80
-rw-r--r--src/io/cli.c6
-rw-r--r--src/io/input.c8
-rw-r--r--src/io/output.c12
-rw-r--r--src/misc/types.h2
-rw-r--r--src/util/bits.c46
-rwxr-xr-xtest/ecgen.sh14
-rw-r--r--test/src/util/test_bits.c2
10 files changed, 114 insertions, 60 deletions
diff --git a/README.md b/README.md
index f4f1e8a..65b5d23 100644
--- a/README.md
+++ b/README.md
@@ -22,7 +22,7 @@ Tool for generating Elliptic curve domain parameters.
- `-s / --ansi[=SEED]` Generate a curve from `SEED` (ANSI X9.62 verifiable procedure).
- `-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.
- - `-F / --family=FAMILY` Generate a pairing friendly curve from a curve family (e.g. "BN", "BLS12", "BLS24").
+ - `-F / --family=FAMILY` Generate a pairing friendly curve from a curve family (e.g. "BN", "BLS12", "BLS24", "KSS16", "KSS18", "KSS36", "KSS40").
- `--nums` Generate a curve using the NUMS procedure (as per draft-black-numscurves-02).
- `--twist` Generate a twist of a given curve.
diff --git a/src/exhaustive/exhaustive.c b/src/exhaustive/exhaustive.c
index bf915c0..e8870f8 100644
--- a/src/exhaustive/exhaustive.c
+++ b/src/exhaustive/exhaustive.c
@@ -148,7 +148,7 @@ static void exhaustive_ginit(gen_f *generators) {
}
generators[OFFSET_FIELD] = &family_gen_field;
generators[OFFSET_A] = &gen_skip;
- if (cfg->family == FAMILY_KSS16) {
+ if (cfg->family == FAMILY_KSS16 || cfg->family == FAMILY_KSS40) {
generators[OFFSET_B] = &family_gen_equation_cm;
} else {
generators[OFFSET_B] = &family_gen_equation_iter;
diff --git a/src/exhaustive/family.c b/src/exhaustive/family.c
index 9d48026..08505b6 100644
--- a/src/exhaustive/family.c
+++ b/src/exhaustive/family.c
@@ -7,7 +7,9 @@
#include "cm/cm_any.h"
#include "gen/seed.h"
#include "misc/config.h"
+#include "util/bits.h"
#include "util/random.h"
+#include "io/output.h"
#define FAMILIES (FAMILY_KSS40 + 1)
@@ -17,49 +19,54 @@ static GEN rz_store[FAMILIES] = {0};
static GEN tz_store[FAMILIES] = {0};
static GEN D_store[FAMILIES] = {0};
+// clang-format off
void family_init() {
pari_sp ltop = avma;
nz_store[FAMILY_BN] = gclone(closure_evalgen(compile_str("(z) -> z")));
- pz_store[FAMILY_BN] = gclone(closure_evalgen(
- compile_str("(z) -> 36*z^4 + 36*z^3 + 24*z^2 + 6*z + 1")));
- rz_store[FAMILY_BN] = gclone(closure_evalgen(
- compile_str("(z) -> 36*z^4 + 36*z^3 + 18*z^2 + 6*z + 1")));
- tz_store[FAMILY_BN] =
- gclone(closure_evalgen(compile_str("(z) -> 6*z + 1")));
+ pz_store[FAMILY_BN] = gclone(closure_evalgen(compile_str("(z) -> 36*z^4 + 36*z^3 + 24*z^2 + 6*z + 1")));
+ rz_store[FAMILY_BN] = gclone(closure_evalgen(compile_str("(z) -> 36*z^4 + 36*z^3 + 18*z^2 + 6*z + 1")));
+ tz_store[FAMILY_BN] = gclone(closure_evalgen(compile_str("(z) -> 6*z + 1")));
D_store[FAMILY_BN] = gclone(stoi(-3));
nz_store[FAMILY_BLS12] = gclone(closure_evalgen(compile_str("(z) -> z")));
- pz_store[FAMILY_BLS12] = gclone(closure_evalgen(
- compile_str("(z) -> (z - 1)^2 * (z^4 - z^2 + 1)/3 + z")));
- rz_store[FAMILY_BLS12] =
- gclone(closure_evalgen(compile_str("(z) -> z^4 - z^2 + 1")));
- tz_store[FAMILY_BLS12] =
- gclone(closure_evalgen(compile_str("(z) -> z + 1")));
+ pz_store[FAMILY_BLS12] = gclone(closure_evalgen(compile_str("(z) -> (z - 1)^2 * (z^4 - z^2 + 1)/3 + z")));
+ rz_store[FAMILY_BLS12] = gclone(closure_evalgen(compile_str("(z) -> z^4 - z^2 + 1")));
+ tz_store[FAMILY_BLS12] = gclone(closure_evalgen(compile_str("(z) -> z + 1")));
D_store[FAMILY_BLS12] = gclone(stoi(-3));
nz_store[FAMILY_BLS24] = gclone(closure_evalgen(compile_str("(z) -> z")));
- pz_store[FAMILY_BLS24] = gclone(closure_evalgen(
- compile_str("(z) -> (z - 1)^2 * (z^8 - z^4 + 1)/3 + z")));
- rz_store[FAMILY_BLS24] =
- gclone(closure_evalgen(compile_str("(z) -> z^8 - z^4 + 1")));
- tz_store[FAMILY_BLS24] =
- gclone(closure_evalgen(compile_str("(z) -> z + 1")));
+ pz_store[FAMILY_BLS24] = gclone(closure_evalgen(compile_str("(z) -> (z - 1)^2 * (z^8 - z^4 + 1)/3 + z")));
+ rz_store[FAMILY_BLS24] = gclone(closure_evalgen(compile_str("(z) -> z^8 - z^4 + 1")));
+ tz_store[FAMILY_BLS24] = gclone(closure_evalgen(compile_str("(z) -> z + 1")));
D_store[FAMILY_BLS24] = gclone(stoi(-3));
- //TODO: This does not work...
- nz_store[FAMILY_KSS16] =
- gclone(closure_evalgen(compile_str("(z) -> 70*z + 25")));
- pz_store[FAMILY_KSS16] = gclone(closure_evalgen(
- compile_str("(z) -> (z^10 + 2*z^9 + 5*z^8 + 48*z^6 + 152*z^5 + 240*z^4 "
- "+ 625*z^2 + 2398*z + 3125)/980")));
- rz_store[FAMILY_KSS16] = gclone(
- closure_evalgen(compile_str("(z) -> (z^8 + 48*z^4 + 625)/61250")));
- tz_store[FAMILY_KSS16] =
- gclone(closure_evalgen(compile_str("(z) -> (2*z^5 + 41*z + 35)/35")));
- D_store[FAMILY_KSS16] = gclone(stoi(-1));
+ nz_store[FAMILY_KSS16] = gclone(closure_evalgen(compile_str("(z) -> 70*z + 25")));
+ pz_store[FAMILY_KSS16] = gclone(closure_evalgen(compile_str("(z) -> (z^10 + 2*z^9 + 5*z^8 + 48*z^6 + 152*z^5 + 240*z^4 + 625*z^2 + 2398*z + 3125)/980")));
+ rz_store[FAMILY_KSS16] = gclone(closure_evalgen(compile_str("(z) -> (z^8 + 48*z^4 + 625)/61250")));
+ tz_store[FAMILY_KSS16] = gclone(closure_evalgen(compile_str("(z) -> (2*z^5 + 41*z + 35)/35")));
+ D_store[FAMILY_KSS16] = gclone(stoi(-4));
+
+ nz_store[FAMILY_KSS18] = gclone(closure_evalgen(compile_str("(z) -> 42*z + 14")));
+ pz_store[FAMILY_KSS18] = gclone(closure_evalgen(compile_str("(z) -> (z^8 + 5*z^7 + 7*z^6 + 37*z^5 + 188*z^4 + 259*z^3 + 343*z^2 + 1763*z + 2401)/21")));
+ rz_store[FAMILY_KSS18] = gclone(closure_evalgen(compile_str("(z) -> (z^6 + 37*z^3 + 343)/343")));
+ tz_store[FAMILY_KSS18] = gclone(closure_evalgen(compile_str("(z) -> (z^4 + 16*z + 7)/7")));
+ D_store[FAMILY_KSS18] = gclone(stoi(-3));
+
+ nz_store[FAMILY_KSS36] = gclone(closure_evalgen(compile_str("(z) -> 777 * z + 287")));
+ pz_store[FAMILY_KSS36] = gclone(closure_evalgen(compile_str("(z) -> (z^14 - 4*z^13 + 7*z^12 + 683*z^8 - 2510*z^7 + 4781*z^6 + 117649*z^2 - 386569*z + 823543)/28749")));
+ rz_store[FAMILY_KSS36] = gclone(closure_evalgen(compile_str("(z) -> (z^12 + 683*z^6 + 117649)/161061481")));
+ tz_store[FAMILY_KSS36] = gclone(closure_evalgen(compile_str("(z) -> (2*z^7 + 757*z + 259)/259")));
+ D_store[FAMILY_KSS36] = gclone(stoi(-3));
+
+ nz_store[FAMILY_KSS40] = gclone(closure_evalgen(compile_str("(z) -> 2370*z + 1205")));
+ pz_store[FAMILY_KSS40] = gclone(closure_evalgen(compile_str("(z) -> (z^22 - 2*z^21 + 5*z^20 + 6232*z^12 - 10568*z^11 + 31160*z^10 + 9765625*z^2 - 13398638*z + 48828125)/1123380")));
+ rz_store[FAMILY_KSS40] = gclone(closure_evalgen(compile_str("(z) -> (z^16 + 8*z^14 + 39*z^12 + 112*z^10 - 79*z^8 + 2800*z^6 + 24375*z^4 + 125000*z^2 + 390625)/2437890625")));
+ tz_store[FAMILY_KSS40] = gclone(closure_evalgen(compile_str("(z) -> (2*z^11 + 6469*z + 1185)/1185")));
+ D_store[FAMILY_KSS40] = gclone(stoi(-4));
avma = ltop;
}
+// clang-format on
static seed_t *family_new_seed() {
seed_t *result = seed_new();
@@ -70,21 +77,18 @@ static seed_t *family_new_seed() {
GENERATOR(family_gen_seed_random) {
curve->seed = family_new_seed();
curve->seed->family.z = random_int(cfg->bits);
+ if (random_bits(1)) {
+ togglesign(curve->seed->family.z);
+ }
+ curve->seed->seed = bits_from_i(curve->seed->family.z);
return 1;
}
GENERATOR(family_gen_seed_input) {
- pari_sp ltop = avma;
GEN inp = input_int("z:", cfg->bits);
- if (gequalm1(inp)) {
- avma = ltop;
- return 0;
- } else if (equalii(inp, gen_m2)) {
- avma = ltop;
- return INT_MIN;
- }
curve->seed = family_new_seed();
curve->seed->family.z = inp;
+ curve->seed->seed = bits_from_i(curve->seed->family.z);
return 1;
}
@@ -96,13 +100,11 @@ GENERATOR(family_gen_field) {
avma = ltop;
return -1;
}
- printf("p");
GEN rz = closure_callgen1(rz_store[cfg->family], n);
if (typ(rz) != t_INT || !isprime(rz)) {
avma = ltop;
return -1;
}
- printf("r");
curve->field = gerepilecopy(ltop, pz);
return 1;
}
diff --git a/src/io/cli.c b/src/io/cli.c
index 0da0770..d98a0c0 100644
--- a/src/io/cli.c
+++ b/src/io/cli.c
@@ -63,7 +63,7 @@ struct argp_option cli_options[] = {
{"nums", OPT_NUMS, 0, 0, "Generate a curve using the NUMS procedure.", 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},
- {"family", OPT_FAMILY, "NAME", 0, "Generate a curve from a curve family (e.g. BN, BLS12, BLS24, KSS)."},
+ {"family", OPT_FAMILY, "NAME", 0, "Generate a curve from a curve family (e.g. BN, BLS12, BLS24, KSS16, KSS18, KSS36, KSS40).", 2},
{0, 0, 0, 0, "Generation options:", 3},
{"random", OPT_RANDOM, "WHAT", OPTION_ARG_OPTIONAL, "Generate a random curve (using Random approach). "
@@ -294,16 +294,12 @@ error_t cli_parse(int key, char *arg, struct argp_state *state) {
} else if (strcasecmp(arg, "BLS24") == 0) {
cfg->family = FAMILY_BLS24;
} else if (strcasecmp(arg, "KSS16") == 0) {
- argp_failure(state, 1, 0, "Family not yet supported.");
cfg->family = FAMILY_KSS16;
} else if (strcasecmp(arg, "KSS18") == 0) {
- argp_failure(state, 1, 0, "Family not yet supported.");
cfg->family = FAMILY_KSS18;
} else if (strcasecmp(arg, "KSS36") == 0) {
- argp_failure(state, 1, 0, "Family not yet supported.");
cfg->family = FAMILY_KSS36;
} else if (strcasecmp(arg, "KSS40") == 0) {
- argp_failure(state, 1, 0, "Family not yet supported.");
cfg->family = FAMILY_KSS40;
} else {
argp_failure(state, 1, 0, "Unknown curve family = %s", arg);
diff --git a/src/io/input.c b/src/io/input.c
index 971ffdf..507bd59 100644
--- a/src/io/input.c
+++ b/src/io/input.c
@@ -32,11 +32,13 @@ static GEN input_i(const char *prompt, unsigned long bits) {
free(line);
return gen_m1;
}
- for (size_t i = 0, j = 0; (line[j] = line[i]); j += !isspace(line[i++]))
- ;
+ bool sign = line[0] == '-';
pari_sp ltop = avma;
- GEN in = strtoi(line);
+ GEN in = strtoi(line + sign);
+ if (sign) {
+ togglesign(in);
+ }
free(line);
// check bitsize here
diff --git a/src/io/output.c b/src/io/output.c
index 32b2de4..c4704c1 100644
--- a/src/io/output.c
+++ b/src/io/output.c
@@ -84,9 +84,17 @@ static JSON_Value *output_jjson(curve_t *curve) {
if (curve->seed && curve->seed->seed) {
char *hex_str = bits_to_hex(curve->seed->seed);
char *hex = try_calloc(strlen(hex_str) + 3);
- hex[0] = '0';
- hex[1] = 'x';
+ if (curve->seed->seed->sign) {
+ hex[0] = '-';
+ hex[1] = '0';
+ } else {
+ hex[0] = '0';
+ hex[1] = 'x';
+ }
strcat(hex, hex_str);
+ if (curve->seed->seed->sign) {
+ hex[2] = 'x';
+ }
json_object_set_string(root_object, "seed", hex);
try_free(hex_str);
try_free(hex);
diff --git a/src/misc/types.h b/src/misc/types.h
index ed9cd18..4bc2114 100644
--- a/src/misc/types.h
+++ b/src/misc/types.h
@@ -15,11 +15,13 @@
/**
* @brief
* @param bits
+ * @param sign
* @param bitlen
* @param allocated
*/
typedef struct {
unsigned char *bits;
+ bool sign;
size_t bitlen;
size_t allocated;
} bits_t;
diff --git a/src/util/bits.c b/src/util/bits.c
index b9fc4c8..0d60c26 100644
--- a/src/util/bits.c
+++ b/src/util/bits.c
@@ -44,10 +44,12 @@ void bits_cpy(bits_t *dest, const bits_t *src) {
memcpy(dest->bits, src->bits, src->allocated);
dest->allocated = src->allocated;
dest->bitlen = src->bitlen;
+ dest->sign = src->sign;
}
bits_t *bits_copy(const bits_t *bits) {
bits_t *result = try_calloc(sizeof(bits_t));
+ result->sign = bits->sign;
result->bitlen = bits->bitlen;
result->allocated = bits->allocated;
if (bits->allocated != 0)
@@ -70,6 +72,7 @@ bits_t *bits_from_i(GEN i) {
GEN bitvec = binary_zv(i);
size_t bit_len = (size_t)glength(bitvec);
bits_t *result = bits_new(bit_len);
+ result->sign = signe(i) == -1;
for (size_t j = 0; j < bit_len; ++j) {
if (gel(bitvec, j + 1) == (GEN)1) {
result->bits[j / 8] |= 1 << (7 - (j % 8));
@@ -84,6 +87,7 @@ bits_t *bits_from_i_len(GEN i, size_t bit_len) {
GEN bitvec = binary_zv(i);
size_t i_len = (size_t)glength(bitvec);
bits_t *result = bits_new(bit_len);
+ result->sign = signe(i) == -1;
size_t offset = 0;
if (i_len < bit_len) {
offset = bit_len - i_len;
@@ -150,22 +154,53 @@ GEN bits_to_i(const bits_t *bits) {
if (GET_BIT(bits->bits, i) != 0)
result = addii(result, int2n(bits->bitlen - i - 1));
}
+ if (bits->sign) {
+ setsigne(result, -1);
+ }
return gerepilecopy(ltop, result);
}
char *bits_to_hex(const bits_t *bits) {
- char *result = try_calloc(BYTE_LEN(bits->bitlen) * 2 + 1);
- // probably right pad with zeroes, as thats what is actually stored.
+ char *result =
+ try_calloc(BYTE_LEN(bits->bitlen) * 2 + 1 + (bits->sign ? 1 : 0));
+ if (bits->sign) {
+ result[0] = '-';
+ }
+ size_t offset = bits->bitlen % 8;
+ // if offset == 0
+ // | a b | c d |
+ // ^-----^ first byte
+ // ^-----^ second byte
+ // else
+ // 0 0 | a b | c d | e
+ // ^-----^ (8-offset zero bits, offset bits from first byte)
+ // ^-----^ (8-offset bits from first byte, offset bits from second byte)
+ // ....
+ // ^-----^ (8-offset bits from second to last byte, offset bits from last byte)
for (size_t i = 0; i < BYTE_LEN(bits->bitlen); ++i) {
- sprintf(result + (i * 2), "%02x", bits->bits[i]);
+ size_t pos = (i * 2) + (bits->sign ? 1 : 0);
+ unsigned char value;
+ if (offset) {
+ value = bits->bits[i] >> (8 - offset);
+ if (i != 0) {
+ value |= (bits->bits[i-1] & ~(1 << (8 - offset))) << offset;
+ }
+ } else {
+ value = bits->bits[i];
+ }
+ sprintf(result + pos, "%02x", value);
}
return result;
}
char *bits_to_bin(const bits_t *bits) {
- char *result = try_calloc(bits->bitlen + 1);
+ char *result = try_calloc(bits->bitlen + 1 + (bits->sign ? 1 : 0));
+ if (bits->sign) {
+ result[0] = '-';
+ }
for (size_t i = 0; i < bits->bitlen; ++i) {
- sprintf(result + i, "%1u", GET_BIT(bits->bits, i));
+ sprintf(result + i + (bits->sign ? 1 : 0), "%1u",
+ GET_BIT(bits->bits, i));
}
return result;
}
@@ -459,6 +494,7 @@ void bits_sha1(const bits_t *bits, unsigned char hashout[20]) {
}
bool bits_eq(const bits_t *one, const bits_t *other) {
+ if (one->sign != other->sign) return false;
if (one->bitlen != other->bitlen) return false;
if (one->bitlen == 0) return true;
if (memcmp(one->bits, other->bits, one->bitlen / 8) != 0) return false;
diff --git a/test/ecgen.sh b/test/ecgen.sh
index c067c2e..38670bc 100755
--- a/test/ecgen.sh
+++ b/test/ecgen.sh
@@ -128,9 +128,17 @@ function supersingular() {
function family() {
start_test
- assert_raises "${ecgen} --fp -r --family=BN 32"
- assert_raises "${ecgen} --fp -r --family=BLS12 32"
- assert_raises "${ecgen} --fp -r --family=BLS24 32"
+ assert_raises "${ecgen} --fp -r --family=BN 16"
+ assert_raises "${ecgen} --fp -r --family=BLS12 16"
+ assert_raises "${ecgen} --fp -r --family=BLS24 16"
+
+ assert_raises "${ecgen} --fp --family=BN 16" 0 "0xe5a2"
+ assert_raises "${ecgen} --fp --family=BLS12 16" 0 "0xafa2"
+ assert_raises "${ecgen} --fp --family=BLS24 16" 0 "0x8278"
+ assert_raises "${ecgen} --fp --family=KSS16 16" 0 "0x8acc"
+ assert_raises "${ecgen} --fp --family=KSS18 16" 0 "0xd2ac"
+ assert_raises "${ecgen} --fp --family=KSS36 16" 0 "0xf07f"
+ assert_raises "${ecgen} --fp --family=KSS40 16" 0 "-0xb18f"
}
function invalid() {
diff --git a/test/src/util/test_bits.c b/test/src/util/test_bits.c
index c1dfd6a..269d1f6 100644
--- a/test/src/util/test_bits.c
+++ b/test/src/util/test_bits.c
@@ -172,7 +172,7 @@ Test(bits, test_bits_to_hex) {
char *hex = bits_to_hex(bits);
cr_assert_not_null(hex, );
- cr_assert_str_eq(hex, "abc0", );
+ cr_assert_str_eq(hex, "0abc", );
try_free(hex);
bits_free(&bits);
}
generated by cgit v1.2.3-70-g09d2 (git 2.51.2) at 2025-11-08 11:07:19 +0000