aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/exhaustive/exhaustive.c4
-rw-r--r--src/gen/order.c33
-rw-r--r--src/gen/order.h17
-rw-r--r--src/gen/point.c158
-rw-r--r--src/gen/point.h12
-rw-r--r--src/io/cli.c12
-rw-r--r--src/io/config.h2
-rw-r--r--src/math/subgroups.c60
-rw-r--r--src/math/subgroups.h39
9 files changed, 173 insertions, 164 deletions
diff --git a/src/exhaustive/exhaustive.c b/src/exhaustive/exhaustive.c
index f2c555b..5c50a71 100644
--- a/src/exhaustive/exhaustive.c
+++ b/src/exhaustive/exhaustive.c
@@ -87,12 +87,16 @@ static void exhaustive_ginit(gen_t *generators, const config_t *cfg) {
case POINTS_PRIME:
generators[OFFSET_POINTS] = &points_gen_prime;
break;
+ case POINTS_NONPRIME:
+ generators[OFFSET_POINTS] = &points_gen_nonprime;
+ break;
case POINTS_ALL:
generators[OFFSET_POINTS] = &points_gen_allgroups;
break;
case POINTS_NONE:
generators[OFFSET_POINTS] = &gen_skip;
break;
+
}
}
diff --git a/src/gen/order.c b/src/gen/order.c
index 2c963f6..6ecd7d6 100644
--- a/src/gen/order.c
+++ b/src/gen/order.c
@@ -5,39 +5,6 @@
#include "order.h"
#include "io/input.h"
-GEN order_factors(curve_t *curve, const config_t *cfg) {
- if (cfg->prime) {
- return gtovec(curve->order);
- } else {
- GEN factors = Z_factor(curve->order);
- return gel(factors, 1);
- }
-}
-
-GEN order_groups(curve_t *curve, const config_t *cfg, GEN factors) {
- long nprimes = glength(factors);
- if (cfg->prime) {
- return gtovec(curve->order);
- } else {
- GEN amount = int2n(nprimes);
- GEN groups = gtovec0(gen_0, itos(amount) - 1);
-
- for (size_t count = 1; count < (size_t)(1 << nprimes); ++count) {
- GEN result = gen_1;
- for (long bit = 0; bit < nprimes; ++bit) {
- size_t mask = (size_t)(1 << bit);
- if (count & mask) {
- result = mulii(result, gel(factors, bit + 1));
- }
- }
- gel(groups, count) = result;
- }
- // TODO: sort this, as it is not necessarily sorted, in fact most likely
- // not
- return groups;
- }
-}
-
GENERATOR(order_gen_input) {
pari_sp ltop = avma;
GEN ord = input_int("order", cfg->bits);
diff --git a/src/gen/order.h b/src/gen/order.h
index bdb6ec0..da62c4d 100644
--- a/src/gen/order.h
+++ b/src/gen/order.h
@@ -11,23 +11,6 @@
#include "types.h"
/**
- * @brief Factors curve order.
- * @param curve
- * @param cfg
- * @return
- */
-GEN order_factors(curve_t *curve, const config_t *cfg);
-
-/**
- * @brief Enumerates all subgroup orders of a curve given prime order factors.
- * @param curve
- * @param cfg
- * @param factors
- * @return
- */
-GEN order_groups(curve_t *curve, const config_t *cfg, GEN factors);
-
-/**
* GENERATOR(gen_t)
* Reads the curve order from input, does not verify it.
*
diff --git a/src/gen/point.c b/src/gen/point.c
index 4251913..66a77d4 100644
--- a/src/gen/point.c
+++ b/src/gen/point.c
@@ -5,6 +5,8 @@
#include "point.h"
#include "order.h"
#include "util/memory.h"
+#include "math/subgroups.h"
+#include "types.h"
point_t *point_new(void) { return try_calloc(sizeof(point_t)); }
@@ -120,53 +122,35 @@ GENERATOR(points_gen_random) {
return 1;
}
-/*
- GEN o = utoi(dprimes[i]);
- GEN mul = ellmul(curve->curve, rand, o);
-
- if (gequal0(mul)) {
- printf("Success! %lu\n", npoints);
- curve->points[i] = point_new();
-
- gerepileall(btop, 2, &rand, &o);
- curve->points[i]->point = rand;
- curve->points[i]->order = o;
- npoints++;
- break;
- }
- */
-
-GENERATOR(points_gen_trial) {
- // TODO stack code!!!
- if (!args) {
- fprintf(stderr, "No args to an arged function. points_gen_trial\n");
- return INT_MIN;
- }
-
- pari_ulong *primes = (pari_ulong *)args->args;
- size_t nprimes = args->nargs;
+static int points_from_orders(curve_t *curve, const config_t *cfg, GEN orders) {
+ // TODO better stack code
+ size_t norders = (size_t)glength(orders);
- curve->points = points_new(nprimes);
- curve->npoints = nprimes;
+ curve->points = points_new(norders);
+ curve->npoints = norders;
- size_t npoints = 0;
- while (npoints < nprimes) {
- GEN rand = genrand(curve->curve);
- GEN ord = ellorder(curve->curve, rand, NULL);
+ for (size_t ngen = 0; ngen <= curve->ngens; ++ngen) {
+ point_t *gen = curve->generators[ngen];
- for (long i = 0; i < nprimes; ++i) {
- if (curve->points[i] == NULL && dvdis(ord, primes[i])) {
+ for (long i = 0; i < norders; ++i) {
+ GEN num = gel(orders, i + 1);
+ if (curve->points[i] == NULL) {
pari_sp ftop = avma;
- GEN p = stoi(primes[i]);
- GEN mul = divii(ord, p);
- GEN point = ellmul(curve->curve, rand, mul);
+ GEN point = NULL;
+ if (equalii(gen->order, num)) {
+ point = gcopy(gen->point);
+ } else if (dvdii(gen->order, num)) {
+ GEN mul = divii(gen->order, num);
+ point = ellmul(curve->curve, gen->point, mul);
+ }
- curve->points[i] = point_new();
- gerepileall(ftop, 2, &point, &p);
- curve->points[i]->point = point;
- curve->points[i]->order = p;
- npoints++;
+ if (point) {
+ curve->points[i] = point_new();
+ gerepileall(ftop, 1, &point);
+ curve->points[i]->point = point;
+ curve->points[i]->order = gcopy(num);
+ }
}
}
}
@@ -174,83 +158,41 @@ GENERATOR(points_gen_trial) {
return 1;
}
-GENERATOR(points_gen_prime) {
- // TODO stack code!!!
-
- GEN primes = order_factors(curve, cfg);
- long nprimes = glength(primes);
- curve->points = points_new((size_t)nprimes);
- curve->npoints = (size_t)nprimes;
-
- long npoints = 0;
- while (npoints < nprimes) {
- GEN rand = genrand(curve->curve);
- GEN ord = ellorder(curve->curve, rand, NULL);
- // ord(rand) = ord
-
- for (long i = 1; i <= nprimes; ++i) {
- if (curve->points[i - 1] == NULL && dvdii(ord, gel(primes, i))) {
- pari_sp ftop = avma;
+GENERATOR(points_gen_trial) {
+ if (!args) {
+ fprintf(stderr, "No args to an arged function. points_gen_trial\n");
+ return INT_MIN;
+ }
- // primes[i] divides ord
- // mul = ord/primes[i]
- GEN mul = divii(ord, gel(primes, i));
- GEN point = ellmul(curve->curve, rand, mul);
+ pari_ulong *primes = (pari_ulong *)args->args;
+ size_t nprimes = args->nargs;
- curve->points[i - 1] = point_new();
- gerepileall(ftop, 1, &point);
- curve->points[i - 1]->point = point;
- curve->points[i - 1]->order = gcopy(gel(primes, i));
- npoints++;
- }
- }
+ GEN orders = gtovec0(gen_0, nprimes);
+ for (size_t i = 1; i <= nprimes; ++i) {
+ gel(orders, i) = utoi(primes[i - 1]);
}
- return 1;
+ return points_from_orders(curve, cfg, orders);
}
-GENERATOR(points_gen_allgroups) {
- // TODO stack code!!!
-
- GEN primes = order_factors(curve, cfg);
-
- GEN groups = order_groups(curve, cfg, primes);
- long ngroups = glength(groups);
-
- curve->points = points_new((size_t)ngroups);
- curve->npoints = (size_t)ngroups;
-
- long npoints = 0;
- while (npoints < ngroups) {
- GEN rand = genrand(curve->curve);
- GEN ord = ellorder(curve->curve, rand, NULL);
-
- for (long i = 1; i <= ngroups; ++i) {
- pari_sp ftop = avma;
- GEN num = gel(groups, i);
+GENERATOR(points_gen_prime) {
+ GEN primes = subgroups_prime(curve->order, cfg);
+ return points_from_orders(curve, cfg, primes);
+}
- if (curve->points[i - 1] == NULL) {
- GEN point = NULL;
- if (equalii(ord, num)) {
- point = gcopy(rand);
- } else if (dvdii(ord, num)) {
- GEN mul = divii(ord, num);
- point = ellmul(curve->curve, rand, mul);
- }
+GENERATOR(points_gen_allgroups) {
+ GEN groups = subgroups_all(curve->order, cfg);
+ return points_from_orders(curve, cfg, groups);
+}
- if (point) {
- curve->points[i - 1] = point_new();
- gerepileall(ftop, 1, &point);
- curve->points[i - 1]->point = point;
- curve->points[i - 1]->order = gcopy(num);
- ++npoints;
- }
- }
- }
+GENERATOR(points_gen_nonprime) {
+ GEN groups = subgroups_nonprime(curve->order, cfg);
+ if (!groups) {
+ return -6;
+ } else {
+ return points_from_orders(curve, cfg, groups);
}
-
- return 1;
}
UNROLL(points_unroll) {
diff --git a/src/gen/point.h b/src/gen/point.h
index 1a0b348..c8cae17 100644
--- a/src/gen/point.h
+++ b/src/gen/point.h
@@ -167,6 +167,18 @@ GENERATOR(points_gen_prime);
GENERATOR(points_gen_allgroups);
/**
+ * GENERATOR(gen_t)
+ *
+ * Generates points on non-prime order of the curve.
+ *
+ * @param curve A curve_t being generated
+ * @param cfg An application config
+ * @param args unused
+ * @return state diff
+ */
+GENERATOR(points_gen_nonprime);
+
+/**
* UNROLL(unroll_t)
*
* @param curve
diff --git a/src/io/cli.c b/src/io/cli.c
index f074c3f..db76b5b 100644
--- a/src/io/cli.c
+++ b/src/io/cli.c
@@ -50,7 +50,7 @@ struct argp_option cli_options[] = {
{"koblitz", OPT_KOBLITZ, 0, 0, "Generate a Koblitz curve (a = 0).", 2},
{"unique", OPT_UNIQUE, 0, 0, "Generate a curve with only one generator.", 2},
{"anomalous", OPT_ANOMALOUS, 0, 0, "Generate an anomalous curve (of trace one, with field order equal to curve order).", 2},
- {"points", OPT_POINTS, "TYPE", 0, "Generate points of given type (random/prime/all/none).", 2},
+ {"points", OPT_POINTS, "TYPE", 0, "Generate points of given type (random/prime/all/nonprime/none).", 2},
{"seed", OPT_SEED, "SEED", OPTION_ARG_OPTIONAL, "Generate a curve from SEED (ANSI X9.62 verifiable procedure). **NOT IMPLEMENTED**", 2},
{"invalid", OPT_INVALID, 0, 0, "Generate a set of invalid curves, for a given curve (using Invalid curve algorithm).", 2},
{"order", OPT_ORDER, "ORDER", 0, "Generate a curve with given order (using Complex Multiplication). **NOT IMPLEMENTED**", 2},
@@ -175,13 +175,15 @@ error_t cli_parse(int key, char *arg, struct argp_state *state) {
char *num_end;
long amount = strtol(arg, &num_end, 10);
cfg->points.amount = (size_t)amount;
- if (strstr(num_end, "random")) {
+ if (strstr(num_end, "random") == num_end) {
cfg->points.type = POINTS_RANDOM;
- } else if (strstr(num_end, "prime")) {
+ } else if (strstr(num_end, "prime") == num_end) {
cfg->points.type = POINTS_PRIME;
- } else if (strstr(num_end, "all")) {
+ } else if (strstr(num_end, "all") == num_end) {
cfg->points.type = POINTS_ALL;
- } else if (strstr(num_end, "none")) {
+ } else if (strstr(num_end, "nonprime") == num_end) {
+ cfg->points.type = POINTS_NONPRIME;
+ } else if (strstr(num_end, "none") == num_end) {
cfg->points.type = POINTS_NONE;
} else {
argp_failure(state, 1, 0, "Unknown point type. %s", num_end);
diff --git a/src/io/config.h b/src/io/config.h
index 5186c67..b365987 100644
--- a/src/io/config.h
+++ b/src/io/config.h
@@ -13,7 +13,7 @@
enum field_e { FIELD_PRIME, FIELD_BINARY };
enum format_e { FORMAT_JSON, FORMAT_CSV };
-enum points_e { POINTS_PRIME, POINTS_RANDOM, POINTS_ALL, POINTS_NONE };
+enum points_e { POINTS_PRIME, POINTS_RANDOM, POINTS_ALL, POINTS_NONPRIME, POINTS_NONE };
struct points_s {
enum points_e type;
size_t amount;
diff --git a/src/math/subgroups.c b/src/math/subgroups.c
new file mode 100644
index 0000000..304d43e
--- /dev/null
+++ b/src/math/subgroups.c
@@ -0,0 +1,60 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+#include "subgroups.h"
+
+GEN subgroups_prime(GEN order, const config_t *cfg) {
+ if (cfg->prime || isprime(order)) {
+ return gtovec(order);
+ } else {
+ GEN factors = Z_factor(order);
+ return gel(factors, 1);
+ }
+}
+
+// TODO: what if some factor multiple times? Prove this works..
+static GEN subgroups_2n(GEN factors, size_t min_bits) {
+ long nprimes = glength(factors);
+ GEN amount = int2n(nprimes);
+ GEN groups = gtovec0(gen_0, itos(amount) - (min_bits * nprimes) - 1);
+
+ size_t i = 0;
+ for (size_t count = 1; count < (size_t)(1 << nprimes); ++count) {
+ pari_sp btop = avma;
+ GEN result = gen_1;
+ size_t bits = 0;
+ for (long bit = 0; bit < nprimes; ++bit) {
+ size_t mask = (size_t)(1 << bit);
+ if (count & mask) {
+ result = mulii(result, gel(factors, bit + 1));
+ bits++;
+ }
+ }
+ if (bits > min_bits) {
+ gel(groups, ++i) = result;
+ } else {
+ avma = btop;
+ }
+ }
+ // TODO: sort this, as it is not sorted
+ return groups;
+}
+
+GEN subgroups_nonprime(GEN order, const config_t *cfg) {
+ if (cfg->prime || isprime(order)) {
+ return NULL;
+ } else {
+ GEN factors = subgroups_prime(order, cfg);
+ return subgroups_2n(factors, 1);
+ }
+}
+
+GEN subgroups_all(GEN order, const config_t *cfg) {
+ if (cfg->prime || isprime(order)) {
+ return gtovec(order);
+ } else {
+ GEN factors = subgroups_prime(order, cfg);
+ return subgroups_2n(factors, 0);
+ }
+} \ No newline at end of file
diff --git a/src/math/subgroups.h b/src/math/subgroups.h
new file mode 100644
index 0000000..bd9b29d
--- /dev/null
+++ b/src/math/subgroups.h
@@ -0,0 +1,39 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+/**
+ * @file subgroups.h
+ */
+#ifndef ECGEN_SUBGROUPS_H
+#define ECGEN_SUBGROUPS_H
+
+#include <pari/pari.h>
+#include "gen/types.h"
+
+/**
+ * @brief Enumerates prime subgroup orders of a given finite group.
+ * @param order group order
+ * @param cfg
+ * @return
+ */
+GEN subgroups_prime(GEN i, const config_t *cfg);
+
+/**
+ * @brief Enumerates nonprime subgroup orders of a given finite group.
+ * @param order group order
+ * @param cfg
+ * @return
+ */
+GEN subgroups_nonprime(GEN order, const config_t *cfg);
+
+/**
+ * @brief Enumerates all subgroup orders of a given finite group.
+ * @param order group order
+ * @param cfg
+ * @return
+ */
+GEN subgroups_all(GEN order, const config_t *cfg);
+
+
+#endif //ECGEN_SUBGROUPS_H
generated by cgit v1.2.3-70-g09d2 (git 2.51.2) at 2025-11-08 15:45:05 +0000