aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/exhaustive/brainpool.c73
-rw-r--r--src/exhaustive/brainpool.h29
-rw-r--r--src/exhaustive/brainpool_rfc.c28
-rw-r--r--src/exhaustive/brainpool_rfc.h6
-rw-r--r--src/exhaustive/exhaustive.c59
-rw-r--r--src/gen/gens.c22
-rw-r--r--src/gen/gens.h13
-rw-r--r--src/misc/types.h2
8 files changed, 182 insertions, 50 deletions
diff --git a/src/exhaustive/brainpool.c b/src/exhaustive/brainpool.c
index d7f0c59..3debaec 100644
--- a/src/exhaustive/brainpool.c
+++ b/src/exhaustive/brainpool.c
@@ -4,6 +4,9 @@
*/
#include "brainpool.h"
+#include <misc/types.h>
+#include "gen/gens.h"
+#include "gen/point.h"
#include "gen/seed.h"
#include "io/output.h"
#include "util/bits.h"
@@ -155,7 +158,8 @@ GENERATOR(brainpool_gen_equation) {
avma = btop;
continue;
}
- z = Fp_sqrtn(Fp_muls(am, -1, curve->field), stoi(4), curve->field, NULL);
+ z = Fp_sqrtn(Fp_muls(am, -1, curve->field), stoi(4), curve->field,
+ NULL);
if (z == NULL) {
brainpool_update_seed(seed->seed);
avma = btop;
@@ -189,13 +193,6 @@ GENERATOR(brainpool_gen_equation) {
continue;
}
- brainpool_update_seed(seed->seed);
- seed->brainpool.seed_bp = bits_copy(seed->seed);
-
- bits_t *mult_bits =
- brainpool_hash(seed->seed, seed->brainpool.w, seed->brainpool.v);
- seed->brainpool.mult = bits_to_i(mult_bits);
-
curve->a = mod_a;
curve->b = mod_b;
gerepileall(btop, 2, &curve->a, &curve->b);
@@ -204,4 +201,64 @@ GENERATOR(brainpool_gen_equation) {
seed->brainpool.update_seed = true;
return 1;
+}
+
+GENERATOR(brainpool_gen_gens) {
+ pari_sp ltop = avma;
+ seed_t *seed = curve->seed;
+ brainpool_update_seed(seed->seed);
+
+ bits_t *k_bits =
+ brainpool_hash(seed->seed, seed->brainpool.w, seed->brainpool.v);
+ GEN k = bits_to_i(k_bits);
+ bits_free(&k_bits);
+ GEN x = gen_0;
+ GEN Qy = ellordinate(curve->curve, x, 0);
+ while (glength(Qy) == 0) {
+ mpaddz(x, gen_1, x);
+ Qy = ellordinate(curve->curve, x, 0);
+ }
+
+ GEN P = NULL;
+ if (glength(Qy) == 1) {
+ P = mkvec2(x, gel(Qy, 1));
+ } else if (glength(Qy) == 2) {
+ if (random_bits(1)) {
+ P = mkvec2(x, gel(Qy, 1));
+ } else {
+ P = mkvec2(x, gel(Qy, 2));
+ }
+ } else {
+ avma = ltop;
+ return INT_MIN;
+ }
+
+ curve->generators = points_new(1);
+ point_t *G = point_new();
+ curve->generators[0] = G;
+ G->point = gerepilecopy(ltop, ellmul(curve->curve, P, k));
+ G->order = ellorder(curve->curve, G->point, NULL);
+ G->cofactor = divii(curve->order, G->order);
+
+ return 1;
+}
+
+CHECK(brainpool_check_gens) {
+ pari_sp ltop = avma;
+ point_t *G = curve->generators[0];
+ GEN min_degree = divis(subii(G->order, gen_1), 100);
+ if (mpcmp(min_degree, gens_get_embedding(curve->field, G->order)) >= 0) {
+ avma = ltop;
+ return -5;
+ }
+ avma = ltop;
+ return 1;
+}
+
+CHECK(brainpool_check_order) {
+ if (mpcmp(curve->order, curve->field) < 0) {
+ return 1;
+ } else {
+ return -4;
+ }
} \ No newline at end of file
diff --git a/src/exhaustive/brainpool.h b/src/exhaustive/brainpool.h
index 741bf2f..0b19fa3 100644
--- a/src/exhaustive/brainpool.h
+++ b/src/exhaustive/brainpool.h
@@ -58,7 +58,7 @@ GENERATOR(brainpool_gen_seed_argument);
GENERATOR(brainpool_gen_seed_input);
/**
- *
+ * @brief
* @param curve
* @param args
* @param state
@@ -75,4 +75,31 @@ GENERATOR(brainpool_gen_field);
*/
GENERATOR(brainpool_gen_equation);
+/**
+ * @brief
+ * @param curve
+ * @param args
+ * @param state
+ * @return
+ */
+GENERATOR(brainpool_gen_gens);
+
+/**
+ * @brief
+ * @param curve
+ * @param args
+ * @param state
+ * @return
+ */
+CHECK(brainpool_check_gens);
+
+/**
+ * @brief
+ * @param curve
+ * @param args
+ * @param state
+ * @return
+ */
+CHECK(brainpool_check_order);
+
#endif // ECGEN_BRAINPOOL_H
diff --git a/src/exhaustive/brainpool_rfc.c b/src/exhaustive/brainpool_rfc.c
index 1a9fea9..921dff3 100644
--- a/src/exhaustive/brainpool_rfc.c
+++ b/src/exhaustive/brainpool_rfc.c
@@ -33,34 +33,46 @@ GENERATOR(brainpool_rfc_gen_equation) {
// field is definitely prime
pari_sp btop = avma;
seed_t *seed = curve->seed;
+ pari_printf("seed before %P#x\n", bits_to_i(seed->seed));
do {
if (seed->brainpool.update_seed) {
+ printf("updating seed\n");
brainpool_update_seed(seed->seed);
+ pari_printf("seed after %P#x\n", bits_to_i(seed->seed));
seed->brainpool.update_seed = false;
}
- GEN z;
bits_t *a_bits =
brainpool_hash(seed->seed, seed->brainpool.w, seed->brainpool.v);
GEN a = bits_to_i(a_bits);
+ pari_printf("trying a = '%P#x'\n", a);
bits_free(&a_bits);
GEN am = Fp_invsafe(a, curve->field);
if (am == NULL) {
brainpool_update_seed(seed->seed);
+ pari_printf("a, update seed(noinv) %P#x\n", bits_to_i(seed->seed));
avma = btop;
continue;
}
- z = Fp_sqrtn(Fp_muls(am, -1, curve->field), stoi(4), curve->field, NULL);
+ GEN z;
+ z = Fp_sqrtn(Fp_muls(am, -3, curve->field), stoi(4), curve->field,
+ NULL);
if (z == NULL) {
brainpool_update_seed(seed->seed);
+ pari_printf("a, update seed(sqrtn) %P#x\n", bits_to_i(seed->seed));
avma = btop;
continue;
}
seed->brainpool.seed_a = bits_copy(seed->seed);
- GEN b;
+ GEN b = NULL;
+ pari_sp bbtop = avma;
do {
+ if (b != NULL) {
+ avma = bbtop;
+ }
brainpool_update_seed(seed->seed);
+ pari_printf("b, update seed %P#x\n", bits_to_i(seed->seed));
bits_t *b_bits = brainpool_hash(seed->seed, seed->brainpool.w,
seed->brainpool.v);
b = bits_to_i(b_bits);
@@ -75,19 +87,13 @@ GENERATOR(brainpool_rfc_gen_equation) {
if (gequal0(gmulsg(-16, gadd(gmulsg(4, gpowgs(mod_a, 3)),
gmulsg(27, gsqr(mod_b)))))) {
brainpool_update_seed(seed->seed);
+ pari_printf("curve, update seed %P#x\n", bits_to_i(seed->seed));
bits_free(&seed->brainpool.seed_a);
bits_free(&seed->brainpool.seed_b);
avma = btop;
continue;
}
- brainpool_update_seed(seed->seed);
- seed->brainpool.seed_bp = bits_copy(seed->seed);
-
- bits_t *mult_bits =
- brainpool_hash(seed->seed, seed->brainpool.w, seed->brainpool.v);
- seed->brainpool.mult = bits_to_i(mult_bits);
-
curve->a = mod_a;
curve->b = mod_b;
gerepileall(btop, 2, &curve->a, &curve->b);
@@ -96,4 +102,4 @@ GENERATOR(brainpool_rfc_gen_equation) {
seed->brainpool.update_seed = true;
return 1;
-} \ No newline at end of file
+}
diff --git a/src/exhaustive/brainpool_rfc.h b/src/exhaustive/brainpool_rfc.h
index c838419..8a27410 100644
--- a/src/exhaustive/brainpool_rfc.h
+++ b/src/exhaustive/brainpool_rfc.h
@@ -9,7 +9,7 @@
#include "misc/types.h"
/**
- *
+ * @brief
* @param curve
* @param args
* @param state
@@ -18,7 +18,7 @@
GENERATOR(brainpool_rfc_gen_seed_argument);
/**
- *
+ * @brief
* @param curve
* @param args
* @param state
@@ -27,7 +27,7 @@ GENERATOR(brainpool_rfc_gen_seed_argument);
GENERATOR(brainpool_rfc_gen_seed_random);
/**
- *
+ * @brief
* @param curve
* @param args
* @param state
diff --git a/src/exhaustive/exhaustive.c b/src/exhaustive/exhaustive.c
index ee475ff..71d5442 100644
--- a/src/exhaustive/exhaustive.c
+++ b/src/exhaustive/exhaustive.c
@@ -40,6 +40,14 @@ void exhaustive_clear(exhaustive_t *setup) {
static void exhaustive_ginit(gen_f *generators) {
if (cfg->seed_algo) {
+ if (cfg->prime) {
+ generators[OFFSET_ORDER] = &order_gen_prime;
+ } else if (cfg->cofactor) {
+ generators[OFFSET_ORDER] = &order_gen_smallfact;
+ } else {
+ generators[OFFSET_ORDER] = &order_gen_any;
+ }
+
switch (cfg->seed_algo) {
case SEED_ANSI: {
// setup ANSI X9.62 generators
@@ -52,13 +60,13 @@ static void exhaustive_ginit(gen_f *generators) {
generators[OFFSET_SEED] = &ansi_gen_seed_input;
}
}
- generators[OFFSET_A] = &gen_skip;
- generators[OFFSET_B] = &ansi_gen_equation;
if (cfg->random) {
generators[OFFSET_FIELD] = &field_gen_random;
} else {
generators[OFFSET_FIELD] = &field_gen_input;
}
+ generators[OFFSET_A] = &gen_skip;
+ generators[OFFSET_B] = &ansi_gen_equation;
} break;
case SEED_BRAINPOOL: {
if (cfg->seed) {
@@ -73,6 +81,8 @@ static void exhaustive_ginit(gen_f *generators) {
generators[OFFSET_FIELD] = &brainpool_gen_field;
generators[OFFSET_A] = &gen_skip;
generators[OFFSET_B] = &brainpool_gen_equation;
+ generators[OFFSET_ORDER] = &order_gen_prime;
+ generators[OFFSET_GENERATORS] = &brainpool_gen_gens;
} break;
case SEED_BRAINPOOL_RFC: {
if (cfg->seed) {
@@ -88,20 +98,14 @@ static void exhaustive_ginit(gen_f *generators) {
generators[OFFSET_FIELD] = &brainpool_gen_field;
generators[OFFSET_A] = &gen_skip;
generators[OFFSET_B] = &brainpool_rfc_gen_equation;
+ generators[OFFSET_ORDER] = &order_gen_prime;
+ generators[OFFSET_GENERATORS] = &brainpool_gen_gens;
} break;
case SEED_FIPS:
break;
default:
break;
}
-
- if (cfg->prime) {
- generators[OFFSET_ORDER] = &order_gen_prime;
- } else if (cfg->cofactor) {
- generators[OFFSET_ORDER] = &order_gen_smallfact;
- } else {
- generators[OFFSET_ORDER] = &order_gen_any;
- }
} else {
// setup normal generators
generators[OFFSET_SEED] = &gen_skip;
@@ -148,16 +152,16 @@ static void exhaustive_ginit(gen_f *generators) {
} else {
generators[OFFSET_FIELD] = &field_gen_input;
}
+
+ if (cfg->unique) {
+ generators[OFFSET_GENERATORS] = &gens_gen_one;
+ } else {
+ generators[OFFSET_GENERATORS] = &gens_gen_any;
+ }
}
// setup common generators
generators[OFFSET_CURVE] = &curve_gen_any;
- if (cfg->unique) {
- generators[OFFSET_GENERATORS] = &gens_gen_one;
- } else {
- generators[OFFSET_GENERATORS] = &gens_gen_any;
- }
-
switch (cfg->points.type) {
case POINTS_RANDOM:
if (cfg->points.amount) {
@@ -189,6 +193,25 @@ static void exhaustive_cinit(check_t **validators) {
check_t *hex_check = check_new(hex_check_param, NULL);
validators[OFFSET_POINTS] = hex_check;
}
+
+ if (cfg->method == METHOD_SEED) {
+ switch (cfg->seed_algo) {
+ case SEED_ANSI:
+ break;
+ case SEED_BRAINPOOL:
+ case SEED_BRAINPOOL_RFC: {
+ check_t *order_check = check_new(brainpool_check_order, NULL);
+ validators[OFFSET_ORDER] = order_check;
+ check_t *gens_check =
+ check_new(gens_check_anomalous, brainpool_check_gens, NULL);
+ validators[OFFSET_GENERATORS] = gens_check;
+ } break;
+ case SEED_FIPS:
+ break;
+ default:
+ break;
+ }
+ }
}
static void exhaustive_ainit(arg_t **gen_argss, arg_t **check_argss) {
@@ -205,12 +228,14 @@ static void exhaustive_ainit(arg_t **gen_argss, arg_t **check_argss) {
gen_argss[OFFSET_FIELD] = field_arg;
gen_argss[OFFSET_B] = eq_arg;
}
+
if (cfg->points.type == POINTS_RANDOM) {
arg_t *points_arg = arg_new();
points_arg->args = &cfg->points.amount;
points_arg->nargs = 1;
gen_argss[OFFSET_POINTS] = points_arg;
}
+
if (cfg->cofactor) {
arg_t *order_arg = arg_new();
arg_t *gens_arg = arg_new();
@@ -278,6 +303,7 @@ int exhaustive_gen_retry(curve_t *curve, const exhaustive_t *setup,
}
timeout_stop();
if (diff > 0 && setup->validators && setup->validators[state]) {
+ pari_sp ctop = avma;
check_t *validator = setup->validators[state];
for (size_t i = 0; i < validator->nchecks; ++i) {
int new_diff =
@@ -287,6 +313,7 @@ int exhaustive_gen_retry(curve_t *curve, const exhaustive_t *setup,
break;
}
}
+ avma = ctop;
}
int new_state = state + diff;
diff --git a/src/gen/gens.c b/src/gen/gens.c
index 2cffbc4..e2c624e 100644
--- a/src/gen/gens.c
+++ b/src/gen/gens.c
@@ -40,16 +40,25 @@ GENERATOR(gens_gen_one) {
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;
}
+GEN gens_get_embedding(GEN prime, GEN order) {
+ pari_sp ltop = avma;
+ GEN power = gen_1;
+ GEN pm;
+ do {
+ power = mulii(power, prime);
+ pm = subii(power, gen_1);
+ } while (!dvdii(pm, order));
+ return gerepilecopy(ltop, power);
+}
+
CHECK(gens_check_embedding) {
HAS_ARG(args);
if (cfg->field == FIELD_BINARY) return 1;
@@ -59,13 +68,8 @@ CHECK(gens_check_embedding) {
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));
+ GEN power =
+ gens_get_embedding(curve->field, curve->generators[i]->order);
if (mpcmp(power, mind) <= 0) {
avma = ltop;
diff --git a/src/gen/gens.h b/src/gen/gens.h
index 18c9815..11b349b 100644
--- a/src/gen/gens.h
+++ b/src/gen/gens.h
@@ -30,6 +30,7 @@ GENERATOR(gens_gen_any);
GENERATOR(gens_gen_one);
/**
+ * CHECK(check_f)
*
* @param curve
* @param args
@@ -39,6 +40,18 @@ GENERATOR(gens_gen_one);
CHECK(gens_check_anomalous);
/**
+ * @brief Get the embedding degree of a subgroup of <code>order</code> in a
+ * power of F_prime.
+ *
+ * @param prime The order of the base field.
+ * @param order The order of the subgroup generator (in the curve group).
+ * @return The embedding degree 't' such that <code>order</code> divides
+ * 'prime^t - 1'.
+ */
+GEN gens_get_embedding(GEN prime, GEN order);
+
+/**
+ * CHECK(check_f)
*
* @param curve
* @param args
diff --git a/src/misc/types.h b/src/misc/types.h
index 960745c..76f8510 100644
--- a/src/misc/types.h
+++ b/src/misc/types.h
@@ -49,8 +49,6 @@ typedef struct {
long v;
bits_t *seed_a;
bits_t *seed_b;
- bits_t *seed_bp;
- GEN mult;
} brainpool;
};
} seed_t;
generated by cgit v1.2.3-70-g09d2 (git 2.51.2) at 2025-11-08 18:30:33 +0000