aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/cm/cm.c1
-rw-r--r--src/exhaustive/exhaustive.c3
-rw-r--r--src/io/cli.c13
-rw-r--r--src/io/config.h2
-rw-r--r--src/math/order.c33
-rw-r--r--src/math/order.h17
-rw-r--r--src/math/point.c54
-rw-r--r--src/math/point.h13
-rw-r--r--src/math/poly.c2
-rw-r--r--src/math/poly.h8
-rw-r--r--src/math/random.c13
-rw-r--r--src/math/random.h19
-rw-r--r--src/util/macro.h14
-rw-r--r--src/util/memory.h7
14 files changed, 173 insertions, 26 deletions
diff --git a/src/cm/cm.c b/src/cm/cm.c
index f91cddf..027f761 100644
--- a/src/cm/cm.c
+++ b/src/cm/cm.c
@@ -3,7 +3,6 @@
* Copyright (C) 2017 J08nY
*/
#include "cm.h"
-#include "exhaustive/anomalous.h"
#include "io/output.h"
#include "p1363.h"
diff --git a/src/exhaustive/exhaustive.c b/src/exhaustive/exhaustive.c
index b4fbbd9..eb2c69e 100644
--- a/src/exhaustive/exhaustive.c
+++ b/src/exhaustive/exhaustive.c
@@ -87,6 +87,9 @@ static void exhaustive_ginit(gen_t *generators, const config_t *cfg) {
case POINTS_PRIME:
generators[OFFSET_POINTS] = &points_gen_prime;
break;
+ case POINTS_ALL:
+ generators[OFFSET_POINTS] = &points_gen_allgroups;
+ break;
case POINTS_NONE:
generators[OFFSET_POINTS] = &gen_skip;
break;
diff --git a/src/io/cli.c b/src/io/cli.c
index dadb65e..d4114c4 100644
--- a/src/io/cli.c
+++ b/src/io/cli.c
@@ -42,6 +42,7 @@ 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, "Generation options:", 2},
{"random", OPT_RANDOM, 0, 0, "Generate a random curve (using Random approach).", 2},
{"prime", OPT_PRIME, 0, 0, "Generate a curve with prime order.", 2},
@@ -49,17 +50,19 @@ 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/none).", 2},
+ {"points", OPT_POINTS, "TYPE", 0, "Generate points of given type (random/prime/all/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},
{"count", OPT_COUNT, "COUNT", 0, "Generate multiple curves.", 2},
+
{0, 0, 0, 0, "Input/Output options:", 3},
{"format", OPT_FORMAT, "FORMAT", 0, "Format to output in. One of [csv,json], default is json.", 3},
{"input", OPT_INPUT, "FILE", 0, "Input from file.", 3},
{"output", OPT_OUTPUT, "FILE", 0, "Output into file. Overwrites any existing file!", 3},
{"append", OPT_APPEND, 0, 0, "Append to output file (don't overwrite).", 3},
{"verbose", OPT_VERBOSE, "FILE", OPTION_ARG_OPTIONAL, "Verbose logging (to stdout or file).", 3},
+
{0, 0, 0, 0, "Other:", 4},
{"data-dir", OPT_DATADIR, "DIR", 0, "Set PARI/GP data directory (containing seadata package).", 4},
{"memory", OPT_MEMORY, "SIZE", 0, "Use PARI stack of SIZE (can have suffix k/m/g).", 4},
@@ -186,16 +189,18 @@ error_t cli_parse(int key, char *arg, struct argp_state *state) {
break;
case OPT_POINTS:
if (arg) {
+ long pts = strtol(arg, NULL, 10);
+ cfg->points.amount = (size_t)pts;
if (strstr(arg, "random")) {
- long pts = strtol(arg, NULL, 10);
cfg->points.type = POINTS_RANDOM;
- cfg->points.amount = (size_t)pts;
} else if (strstr(arg, "prime")) {
cfg->points.type = POINTS_PRIME;
+ } else if (strstr(arg, "all")) {
+ cfg->points.type = POINTS_ALL;
} else if (strstr(arg, "none")) {
cfg->points.type = POINTS_NONE;
} else {
- argp_failure(state, 1, 0, "Unknow point type");
+ argp_failure(state, 1, 0, "Unknown point type.");
}
} else {
argp_failure(state, 1, 0,
diff --git a/src/io/config.h b/src/io/config.h
index 42a48be..5186c67 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_NONE };
+enum points_e { POINTS_PRIME, POINTS_RANDOM, POINTS_ALL, POINTS_NONE };
struct points_s {
enum points_e type;
size_t amount;
diff --git a/src/math/order.c b/src/math/order.c
index 4c8c728..347015c 100644
--- a/src/math/order.c
+++ b/src/math/order.c
@@ -4,6 +4,39 @@
*/
#include "order.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_any) {
GEN ord = ellff_get_card(curve->curve);
if (isclone(ord)) {
diff --git a/src/math/order.h b/src/math/order.h
index 8a56b94..ce3cd0b 100644
--- a/src/math/order.h
+++ b/src/math/order.h
@@ -11,6 +11,23 @@
#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)
* Calculates the curve order, using a general algorithm.
* Always succeeds.
diff --git a/src/math/point.c b/src/math/point.c
index f590ca2..4251913 100644
--- a/src/math/point.c
+++ b/src/math/point.c
@@ -3,6 +3,7 @@
* Copyright (C) 2017 J08nY
*/
#include "point.h"
+#include "order.h"
#include "util/memory.h"
point_t *point_new(void) { return try_calloc(sizeof(point_t)); }
@@ -176,8 +177,7 @@ GENERATOR(points_gen_trial) {
GENERATOR(points_gen_prime) {
// TODO stack code!!!
- GEN factors = Z_factor(curve->order);
- GEN primes = gel(factors, 1);
+ GEN primes = order_factors(curve, cfg);
long nprimes = glength(primes);
curve->points = points_new((size_t)nprimes);
@@ -195,14 +195,13 @@ GENERATOR(points_gen_prime) {
// primes[i] divides ord
// mul = ord/primes[i]
- GEN p = gcopy(gel(primes, i));
- GEN mul = divii(ord, p);
+ GEN mul = divii(ord, gel(primes, i));
GEN point = ellmul(curve->curve, rand, mul);
curve->points[i - 1] = point_new();
- gerepileall(ftop, 2, &point, &p);
+ gerepileall(ftop, 1, &point);
curve->points[i - 1]->point = point;
- curve->points[i - 1]->order = p;
+ curve->points[i - 1]->order = gcopy(gel(primes, i));
npoints++;
}
}
@@ -211,6 +210,49 @@ GENERATOR(points_gen_prime) {
return 1;
}
+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);
+
+ 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);
+ }
+
+ 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;
+ }
+ }
+ }
+ }
+
+ return 1;
+}
+
UNROLL(points_unroll) {
if (curve->points) {
points_free_deep(&curve->points, curve->npoints);
diff --git a/src/math/point.h b/src/math/point.h
index 49c37c6..a25ec2c 100644
--- a/src/math/point.h
+++ b/src/math/point.h
@@ -159,6 +159,19 @@ GENERATOR(points_gen_trial);
GENERATOR(points_gen_prime);
/**
+ * GENERATOR(gen_t)
+ *
+ * Generates points on all subgroups of the curve. Prime and non-prime order.
+ *
+ * @param curve
+ * @param cfg
+ * @param args
+ * @return
+ */
+GENERATOR(points_gen_allgroups);
+
+/**
+ * UNROLL(unroll_t)
*
* @param curve
* @param cfg
diff --git a/src/math/poly.c b/src/math/poly.c
index 50d0da0..2b655da 100644
--- a/src/math/poly.c
+++ b/src/math/poly.c
@@ -2729,7 +2729,7 @@ polynomial_t *poly_find(unsigned long m) {
len_penta = sizeof(hp_pentanomials) / sizeof(polynomial_t);
}
- polynomial_t searched = {(int)m};
+ polynomial_t searched = {(unsigned int)m};
polynomial_t *tri = (polynomial_t *)bsearch(
&searched, search_tri, len_tri, sizeof(polynomial_t), &compare_poly);
if (tri) {
diff --git a/src/math/poly.h b/src/math/poly.h
index 664ca6b..83b909a 100644
--- a/src/math/poly.h
+++ b/src/math/poly.h
@@ -12,10 +12,10 @@
#include <stdbool.h>
typedef struct {
- int m;
- int e1;
- int e2;
- int e3;
+ unsigned int m;
+ unsigned int e1;
+ unsigned int e2;
+ unsigned int e3;
} polynomial_t;
/**
diff --git a/src/math/random.c b/src/math/random.c
index da4bc2c..519ce6b 100644
--- a/src/math/random.c
+++ b/src/math/random.c
@@ -3,6 +3,7 @@
* Copyright (C) 2017 J08nY
*/
#define _POSIX_C_SOURCE 200809L
+
#include "random.h"
#include <time.h>
@@ -43,13 +44,11 @@ GEN random_prime(unsigned long bits) {
gel(range, 2) = powis(gen_2, bits);
GEN p;
- {
- pari_sp btop = avma;
- do {
- p = randomprime(range);
- p = gerepileupto(btop, p);
- } while (!isprime(p));
- }
+ pari_sp btop = avma;
+ do {
+ p = randomprime(range);
+ p = gerepileupto(btop, p);
+ } while (!isprime(p));
return gerepilecopy(ltop, p);
}
diff --git a/src/math/random.h b/src/math/random.h
index de03abb..1152bb5 100644
--- a/src/math/random.h
+++ b/src/math/random.h
@@ -11,10 +11,29 @@
#include <pari/pari.h>
#include <stdbool.h>
+/**
+ * @brief Init the PARI-GP random generator.
+ *
+ * Initializes the PARI-GP random generator, tries to do so from
+ * cryptographically strong sources(/dev/urandom) at first but falls back on
+ * clock_gettime and {@link time(NULL)}.
+ *
+ * @return Whether the initialization was successful.
+ */
bool random_init(void);
+/**
+ * @brief Generate random <code>bits</code> sized prime.
+ * @param bits the size of the prime to generate
+ * @return a random prime in range [2^(bits - 1), 2^bits]
+ */
GEN random_prime(unsigned long bits);
+/**
+ * @brief Generate random <code>bits</code> sized integer.
+ * @param bits the size of the integer to generate
+ * @return a random integer in range [2^(bits - 1), 2^bits]
+ */
GEN random_int(unsigned long bits);
#endif // ECGEN_RANDOM_H
diff --git a/src/util/macro.h b/src/util/macro.h
new file mode 100644
index 0000000..abe2c5f
--- /dev/null
+++ b/src/util/macro.h
@@ -0,0 +1,14 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+/**
+ * @file macro.h
+ */
+#ifndef ECGEN_MACRO_H
+#define ECGEN_MACRO_H
+
+#define VA_NARGS_IMPL(_1, _2, _3, _4, _5, _6, _7, _8, _9, _10, N, ...) N
+#define VA_NARGS(...) VA_NARGS_IMPL(__VA_ARGS__, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1)
+
+#endif // ECGEN_MACRO_H
diff --git a/src/util/memory.h b/src/util/memory.h
index fef237e..8b85a3d 100644
--- a/src/util/memory.h
+++ b/src/util/memory.h
@@ -2,11 +2,14 @@
* ecgen, tool for generating Elliptic curve domain parameters
* Copyright (C) 2017 J08nY
*/
-#include <stddef.h>
-
+/**
+ * @file memory.h
+ */
#ifndef ECGEN_MEMORY_H
#define ECGEN_MEMORY_H
+#include <stddef.h>
+
/**
* @brief
* @param size
generated by cgit v1.2.3-70-g09d2 (git 2.51.2) at 2025-11-08 18:41:46 +0000