aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--CMakeLists.txt2
-rw-r--r--src/exhaustive/ansi.c27
-rw-r--r--src/exhaustive/brainpool.c151
-rw-r--r--src/exhaustive/brainpool.h35
-rw-r--r--src/gen/seed.c3
-rw-r--r--src/io/cli.c24
-rw-r--r--src/misc/types.h8
-rw-r--r--src/util/bits.c31
-rw-r--r--src/util/bits.h4
-rw-r--r--src/util/str.c16
-rw-r--r--src/util/str.h7
-rw-r--r--test/src/exhaustive/test_ansi.c18
-rw-r--r--test/src/gen/test_field.c2
-rw-r--r--test/src/util/test_bits.c18
14 files changed, 304 insertions, 42 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 5ebb028..fbaa39c 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -7,7 +7,7 @@ file(GLOB SRC "src/math/*.c" "src/gen/*.c" "src/cm/*.c" "src/invalid/*.c" "src/i
set(ECGEN_SRC "src/ecgen.c" ${SRC})
set(ECONVERT_SRC "src/econvert.c")
-set(CMAKE_C_FLAGS_DEBUG "${CMAKE_C_FLAGS_DEBUG} -DDEBUG -g -Wall -Werror -pedantic")
+set(CMAKE_C_FLAGS_DEBUG "${CMAKE_C_FLAGS_DEBUG} -DDEBUG -g -Wall -Werror")
set(CMAKE_C_FLAGS_RELEASE "${CMAKE_C_FLAGS_RELEASE} -DNDEBUG -O3 -Wall")
include_directories(src)
diff --git a/src/exhaustive/ansi.c b/src/exhaustive/ansi.c
index 762ffb7..d870d76 100644
--- a/src/exhaustive/ansi.c
+++ b/src/exhaustive/ansi.c
@@ -9,6 +9,7 @@
#include "io/output.h"
#include "util/bits.h"
#include "util/memory.h"
+#include "util/str.h"
static seed_t *ansi_new() {
seed_t *result = seed_new();
@@ -17,26 +18,8 @@ static seed_t *ansi_new() {
}
bool ansi_seed_valid(const char *hex_str) {
- size_t len = strlen(hex_str);
- if (len < 40) {
- return false;
- }
- const char *str_start = hex_str;
- if (hex_str[0] == '0' && (hex_str[1] == 'x' || hex_str[1] == 'X')) {
- str_start = hex_str + 2;
- }
- while (*str_start != 0) {
- char c = *str_start++;
- if (!isxdigit(c)) return false;
- }
- return true;
-}
-
-static bits_t *seed_stoi(const char *cstr) {
- const char *seed_str = cstr;
- const char *prefix = strstr(cstr, "0x");
- if (prefix != NULL) seed_str = prefix + 2;
- return bits_from_hex(seed_str);
+ const char *seed = str_is_hex(hex_str);
+ return seed && strlen(seed) >= 40;
}
static void seed_hash(seed_t *seed) {
@@ -64,7 +47,7 @@ GENERATOR(ansi_gen_seed_random) {
GENERATOR(ansi_gen_seed_argument) {
seed_t *seed = ansi_new();
- seed->seed = seed_stoi(cfg->seed);
+ seed->seed = bits_from_hex(str_is_hex(cfg->seed));
seed_hash(seed);
seed_tsh(seed);
curve->seed = seed;
@@ -83,7 +66,7 @@ GENERATOR(ansi_gen_seed_input) {
}
seed_t *seed = ansi_new();
- seed->seed = seed_stoi(cstr);
+ seed->seed = bits_from_hex(str_is_hex(cstr));
seed_hash(seed);
seed_tsh(seed);
curve->seed = seed;
diff --git a/src/exhaustive/brainpool.c b/src/exhaustive/brainpool.c
index f8ddb8e..0e3fa83 100644
--- a/src/exhaustive/brainpool.c
+++ b/src/exhaustive/brainpool.c
@@ -4,11 +4,154 @@
*/
#include "brainpool.h"
+#include <misc/types.h>
+#include "gen/seed.h"
+#include "io/output.h"
+#include "util/bits.h"
+#include "util/str.h"
-GENERATOR(brainpool_gen_seed_random) { return INT_MIN; }
+static seed_t *brainpool_new() {
+ seed_t *result = seed_new();
+ result->type = SEED_BRAINPOOL;
+ result->brainpool.first = true;
+ return result;
+}
-GENERATOR(brainpool_gen_seed_argument) { return INT_MIN; }
+static void seed_wv(seed_t *seed) {
+ pari_sp ltop = avma;
+ GEN L = utoi(cfg->bits);
+ seed->brainpool.v = itou(floorr(divis(subis(L, 1), 160)));
+ seed->brainpool.w =
+ itou(floorr(subis(subis(L, 160 * seed->brainpool.v), 1)));
+ avma = ltop;
+}
-GENERATOR(brainpool_gen_seed_input) { return INT_MIN; }
+static void brainpool_update_seed(bits_t *s) {
+ pari_sp ltop = avma;
+ GEN z = bits_to_i(s);
+ GEN t = Fp_add(z, gen_1, int2n(160));
+ bits_t *result = bits_from_i_len(t, 160);
+ avma = ltop;
+ bits_cpy(s, result);
+ bits_free(&result);
+}
-GENERATOR(brainpool_gen_equation) { return INT_MIN; } \ No newline at end of file
+static bits_t *brainpool_hash(const bits_t *s, long w, long v) {
+ pari_sp ltop = avma;
+ unsigned char h0[20];
+ bits_sha1(s, h0);
+ unsigned char hashout[w + 20 * v];
+ memcpy(hashout, h0, (size_t)w);
+
+ GEN z = bits_to_i(s);
+ GEN m = int2n(160);
+ for (long i = 1; i < v; ++i) {
+ bits_t *si = bits_from_i(Fp_add(z, stoi(i), m));
+ bits_sha1(si, hashout + w + 20 * i);
+ bits_free(&si);
+ }
+ bits_t *result = bits_from_raw(hashout, (size_t)(w + (20 * v)));
+ avma = ltop;
+ return result;
+}
+
+bool brainpool_seed_valid(const char *hex_str) {
+ const char *seed = str_is_hex(hex_str);
+ return seed && strlen(seed) == 40;
+}
+
+GENERATOR(brainpool_gen_seed_random) {
+ seed_t *seed = brainpool_new();
+ seed->seed = bits_new_rand(160);
+ seed_wv(seed);
+ curve->seed = seed;
+ return 1;
+}
+
+GENERATOR(brainpool_gen_seed_argument) {
+ seed_t *seed = brainpool_new();
+ seed->seed = bits_from_hex(str_is_hex(cfg->seed));
+ seed_wv(seed);
+ curve->seed = seed;
+ return 1;
+}
+
+GENERATOR(brainpool_gen_seed_input) {
+ pari_sp ltop = avma;
+
+ GEN str = input_string("seed:");
+ const char *cstr = GSTR(str);
+ if (!brainpool_seed_valid(cstr)) {
+ fprintf(err, "SEED must be exactly 160 bits(40 hex characters).\n");
+ avma = ltop;
+ return 0;
+ }
+
+ seed_t *seed = brainpool_new();
+ seed->seed = bits_from_hex(str_is_hex(cstr));
+ seed_wv(seed);
+ curve->seed = seed;
+ return INT_MIN;
+}
+
+GENERATOR(brainpool_gen_equation) {
+ // field is definitely prime
+ pari_sp btop = avma;
+ seed_t *seed = curve->seed;
+ do {
+ if (seed->brainpool.first) {
+ brainpool_update_seed(seed->seed);
+ seed->brainpool.first = false;
+ }
+
+ GEN z;
+ bits_t *a_bits =
+ brainpool_hash(seed->seed, seed->brainpool.w, seed->brainpool.v);
+ GEN a = bits_to_i(a_bits);
+ bits_free(&a_bits);
+ z = Fp_sqrtn(a, stoi(4), curve->field, NULL);
+ if (z == NULL) {
+ brainpool_update_seed(seed->seed);
+ continue;
+ }
+ seed->brainpool.seed_a = bits_copy(seed->seed);
+
+ brainpool_update_seed(seed->seed);
+
+ bits_t *b_bits =
+ brainpool_hash(seed->seed, seed->brainpool.w, seed->brainpool.v);
+ GEN b = bits_to_i(b_bits);
+ bits_free(&b_bits);
+ if (!Fp_issquare(b, curve->field)) {
+ brainpool_update_seed(seed->seed);
+ bits_free(&seed->brainpool.seed_a);
+ continue;
+ }
+ seed->brainpool.seed_b = bits_copy(seed->seed);
+
+ GEN mod_a = gmodulo(a, curve->field);
+ GEN mod_b = gmodulo(b, curve->field);
+
+ if (gequal0(gmulsg(-16, gadd(gmulsg(4, gpowgs(mod_a, 3)),
+ gmulsg(27, gsqr(mod_b)))))) {
+ brainpool_update_seed(seed->seed);
+ bits_free(&seed->brainpool.seed_a);
+ bits_free(&seed->brainpool.seed_b);
+ 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);
+ break;
+ } while (true);
+
+ return 1;
+} \ No newline at end of file
diff --git a/src/exhaustive/brainpool.h b/src/exhaustive/brainpool.h
index cf212b1..cb79e89 100644
--- a/src/exhaustive/brainpool.h
+++ b/src/exhaustive/brainpool.h
@@ -8,12 +8,47 @@
#include "misc/types.h"
+/**
+ * @brief
+ * @param hex_str
+ * @return
+ */
+bool brainpool_seed_valid(const char *hex_str);
+
+/**
+ * @brief
+ * @param curve
+ * @param args
+ * @param state
+ * @return
+ */
GENERATOR(brainpool_gen_seed_random);
+/**
+ * @brief
+ * @param curve
+ * @param args
+ * @param state
+ * @return
+ */
GENERATOR(brainpool_gen_seed_argument);
+/**
+ * @brief
+ * @param curve
+ * @param args
+ * @param state
+ * @return
+ */
GENERATOR(brainpool_gen_seed_input);
+/**
+ * @brief
+ * @param curve
+ * @param args
+ * @param state
+ * @return
+ */
GENERATOR(brainpool_gen_equation);
#endif // ECGEN_BRAINPOOL_H
diff --git a/src/gen/seed.c b/src/gen/seed.c
index f349982..2e3f9e3 100644
--- a/src/gen/seed.c
+++ b/src/gen/seed.c
@@ -46,6 +46,9 @@ void seed_free(seed_t **seed) {
case SEED_ANSI:
break;
case SEED_BRAINPOOL:
+ bits_free(&(*seed)->brainpool.seed_a);
+ bits_free(&(*seed)->brainpool.seed_b);
+ bits_free(&(*seed)->brainpool.seed_bp);
break;
case SEED_BRAINPOOL_RFC:
break;
diff --git a/src/io/cli.c b/src/io/cli.c
index a3fef1f..63a69be 100644
--- a/src/io/cli.c
+++ b/src/io/cli.c
@@ -6,6 +6,7 @@
#include <misc/config.h>
#include <string.h>
#include "exhaustive/ansi.h"
+#include "exhaustive/brainpool.h"
char cli_doc[] =
"ecgen, tool for generating Elliptic curve domain parameters.\v(C) 2017 "
@@ -19,6 +20,7 @@ enum opt_keys {
OPT_COFACTOR = 'k',
OPT_RANDOM = 'r',
OPT_ANSI = 's',
+ OPT_BRAINPOOL = 'b',
OPT_INVALID = 'i',
OPT_ORDER = 'n',
OPT_KOBLITZ = 'K',
@@ -51,6 +53,7 @@ struct argp_option cli_options[] = {
{"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},
{"invalid", OPT_INVALID, 0, 0, "Generate a set of invalid curves, for a given curve (using Invalid curve algorithm).", 2},
{0, 0, 0, 0, "Generation options:", 3},
@@ -130,13 +133,9 @@ static void cli_end(struct argp_state *state) {
// Only one gen method
switch (cfg->method) {
case METHOD_DEFAULT:
- break;
case METHOD_CM:
- break;
case METHOD_ANOMALOUS:
- break;
case METHOD_SEED:
- break;
case METHOD_INVALID:
break;
default:
@@ -146,6 +145,11 @@ static void cli_end(struct argp_state *state) {
break;
}
+ if (cfg->method == METHOD_SEED && cfg->seed_algo == SEED_BRAINPOOL &&
+ cfg->field == FIELD_BINARY) {
+ argp_failure(state, 1, 0,
+ "Brainpool algorithm only creates prime field curves.");
+ }
/*
// Invalid is not prime or seed by definition.
if (cfg->invalid &&
@@ -227,6 +231,18 @@ error_t cli_parse(int key, char *arg, struct argp_state *state) {
cfg->seed = arg;
}
break;
+ case OPT_BRAINPOOL:
+ cfg->method |= METHOD_SEED;
+ cfg->seed_algo = SEED_BRAINPOOL;
+ if (arg) {
+ if (!brainpool_seed_valid(arg)) {
+ argp_failure(
+ state, 1, 0,
+ "SEED must be exactly 160 bits (40 hex characters).");
+ }
+ cfg->seed = arg;
+ }
+ break;
/* Generation options */
case OPT_COUNT:
diff --git a/src/misc/types.h b/src/misc/types.h
index aecf207..9c1cff6 100644
--- a/src/misc/types.h
+++ b/src/misc/types.h
@@ -44,7 +44,13 @@ typedef struct {
GEN r;
} ansi;
struct {
- bits_t *f;
+ bool first;
+ long w;
+ long v;
+ bits_t *seed_a;
+ bits_t *seed_b;
+ bits_t *seed_bp;
+ GEN mult;
} brainpool;
};
} seed_t;
diff --git a/src/util/bits.c b/src/util/bits.c
index 6311ba8..5e6a95e 100644
--- a/src/util/bits.c
+++ b/src/util/bits.c
@@ -4,6 +4,7 @@
*/
#include "bits.h"
+#include <misc/types.h>
#include <sha1/sha1.h>
#include "util/memory.h"
@@ -16,6 +17,36 @@ bits_t *bits_new(size_t bit_len) {
return result;
}
+bits_t *bits_new_rand(size_t bit_len) {
+ bits_t *result = bits_new(bit_len);
+ for (size_t i = 0; i < result->allocated; ++i) {
+ if (i == result->allocated - 1) {
+ size_t last_bits = bit_len % 8;
+ result->bits[i] = (unsigned char)random_bits(last_bits)
+ << (8 - last_bits);
+ } else {
+ result->bits[i] = (unsigned char)random_bits(8);
+ }
+ }
+ return result;
+}
+
+void bits_cpy(bits_t *dest, const bits_t *src) {
+ if (src->bitlen == 0) {
+ return;
+ }
+
+ if (src->allocated < dest->allocated) {
+ memset(dest->bits + src->allocated, 0,
+ dest->allocated - src->allocated);
+ } else if (src->allocated > dest->allocated) {
+ dest->bits = try_realloc(dest->bits, src->allocated);
+ }
+ memcpy(dest->bits, src->bits, src->allocated);
+ dest->allocated = src->allocated;
+ dest->bitlen = src->bitlen;
+}
+
bits_t *bits_copy(const bits_t *bits) {
bits_t *result = try_calloc(sizeof(bits_t));
result->bitlen = bits->bitlen;
diff --git a/src/util/bits.h b/src/util/bits.h
index 9b37539..000d64f 100644
--- a/src/util/bits.h
+++ b/src/util/bits.h
@@ -29,6 +29,10 @@
bits_t *bits_new(size_t bit_len);
+bits_t *bits_new_rand(size_t bit_len);
+
+void bits_cpy(bits_t *dest, const bits_t *src);
+
bits_t *bits_copy(const bits_t *bits);
void bits_free(bits_t **bits);
diff --git a/src/util/str.c b/src/util/str.c
index 933eb83..3f9f39c 100644
--- a/src/util/str.c
+++ b/src/util/str.c
@@ -3,9 +3,25 @@
* Copyright (C) 2017 J08nY
*/
#include "str.h"
+#include <ctype.h>
#include <string.h>
#include "util/memory.h"
+const char *str_is_hex(const char *hex_str) {
+ const char *str_start = hex_str;
+ if (strlen(hex_str) > 2) {
+ if (hex_str[0] == '0' && (hex_str[1] == 'x' || hex_str[1] == 'X')) {
+ str_start = hex_str + 2;
+ }
+ }
+ const char *s = str_start;
+ while (*s != 0) {
+ char c = *s++;
+ if (!isxdigit(c)) return NULL;
+ }
+ return str_start;
+}
+
char *str_join(char *strings[], size_t len) {
size_t total = 0;
for (size_t i = 0; i < len; ++i) {
diff --git a/src/util/str.h b/src/util/str.h
index 2e14272..9b5709e 100644
--- a/src/util/str.h
+++ b/src/util/str.h
@@ -12,6 +12,13 @@
/**
* @brief
+ * @param hex_str
+ * @return
+ */
+const char *str_is_hex(const char *hex_str);
+
+/**
+ * @brief
* @param strings
* @param len
* @return
diff --git a/test/src/exhaustive/test_ansi.c b/test/src/exhaustive/test_ansi.c
index f1177c7..5b58102 100644
--- a/test/src/exhaustive/test_ansi.c
+++ b/test/src/exhaustive/test_ansi.c
@@ -17,7 +17,7 @@
TestSuite(ansi, .init = io_setup, .fini = io_teardown);
Test(ansi, test_seed_random) {
- curve_t curve = {};
+ curve_t curve = {0};
cfg->bits = 256;
int ret = ansi_gen_seed_random(&curve, NULL, OFFSET_SEED);
@@ -28,7 +28,7 @@ Test(ansi, test_seed_random) {
}
Test(ansi, test_seed_argument) {
- curve_t curve = {};
+ curve_t curve = {0};
char *seed = "abcdefabcdefabcdefabcdefabcdefabcdefabcd";
cfg->seed = seed;
cfg->bits = 256;
@@ -44,7 +44,7 @@ Test(ansi, test_seed_argument) {
}
Test(ansi, test_seed_argument_hex) {
- curve_t curve = {};
+ curve_t curve = {0};
char *seed = "0xabcdefabcdefabcdefabcdefabcdefabcdefabcd";
cfg->seed = seed;
cfg->bits = 256;
@@ -60,7 +60,7 @@ Test(ansi, test_seed_argument_hex) {
}
Test(ansi, test_seed_input) {
- curve_t curve = {};
+ curve_t curve = {0};
char *seed = "abcdefabcdefabcdefabcdefabcdefabcdefabcd";
cfg->bits = 256;
fprintf(write_in, "%s\n", seed);
@@ -76,7 +76,7 @@ Test(ansi, test_seed_input) {
}
Test(ansi, test_seed_input_short) {
- curve_t curve = {};
+ curve_t curve = {0};
char *seed = "abcdef";
fprintf(write_in, "%s\n", seed);
int ret = ansi_gen_seed_input(&curve, NULL, OFFSET_SEED);
@@ -103,7 +103,7 @@ void prime_params_cleanup(struct criterion_test_params *ctp) {
}
ParameterizedTestParameters(ansi, test_seed_prime_examples) {
- static struct prime_params params[7] = {};
+ static struct prime_params params[7] = {{0}};
// Taken from ANSI X9.62 J.5.1 - J.5.3; p. 115 - 117
// clang-format off
params[0].bits = 192;
@@ -157,7 +157,7 @@ ParameterizedTest(struct prime_params *param, ansi, test_seed_prime_examples) {
cfg->bits = param->bits;
cfg->field = FIELD_PRIME;
cfg->seed = param->seed;
- curve_t curve = {};
+ curve_t curve = {0};
bits_t *p = bits_from_hex(param->p);
curve.field = bits_to_i(p);
@@ -189,7 +189,7 @@ void binary_params_cleanup(struct criterion_test_params *ctp) {
}
ParameterizedTestParameters(ansi, test_seed_binary_examples) {
- static struct binary_params params[10] = {};
+ static struct binary_params params[10] = {{0}};
// Taken from ANSI X9.62 J.4.1, J.4.3, J.4.5 and J.4.8; p. 107 - 113
// clang-format off
polynomial_t p163 = {163, 9, 3, 2};
@@ -257,7 +257,7 @@ ParameterizedTest(struct binary_params *param, ansi,
cfg->bits = param->bits;
cfg->field = FIELD_BINARY;
cfg->seed = param->seed;
- curve_t curve = {};
+ curve_t curve = {0};
curve.field = poly_gen(&param->field);
GEN expected_b = bits_to_i(bits_from_hex(param->b));
diff --git a/test/src/gen/test_field.c b/test/src/gen/test_field.c
index 6ceeca4..03bd626 100644
--- a/test/src/gen/test_field.c
+++ b/test/src/gen/test_field.c
@@ -62,7 +62,7 @@ Test(field, test_field_gen_input_fp) {
ret = field_gen_input(&curve, NULL, OFFSET_FIELD);
cr_assert_eq(ret, 0, );
cr_assert_null(curve.field, );
-};
+}
Test(field, test_field_gen_input_f2m) {
curve_t curve = {0};
diff --git a/test/src/util/test_bits.c b/test/src/util/test_bits.c
index a7b38e3..27da58b 100644
--- a/test/src/util/test_bits.c
+++ b/test/src/util/test_bits.c
@@ -5,10 +5,12 @@
#include <criterion/criterion.h>
#include <criterion/parameterized.h>
+#include <misc/types.h>
#include "test/default.h"
#include "test/memory.h"
#include "util/bits.h"
#include "util/memory.h"
+#include "util/random.h"
TestSuite(bits, .init = default_setup, .fini = default_teardown);
@@ -22,6 +24,22 @@ Test(bits, test_bits_new) {
bits_free(&bits);
}
+Test(bits, test_bits_new_rand) {
+ random_init();
+ GEN seed = getrand();
+ bits_t *bits = bits_new_rand(10);
+ cr_assert_not_null(bits, );
+ cr_assert_eq(bits->bitlen, 10, );
+ cr_assert_eq(bits->allocated, 2, );
+
+ setrand(seed);
+ unsigned char one = (unsigned char)random_bits(8);
+ unsigned char other = (unsigned char)random_bits(2) << 6;
+ cr_assert_eq(bits->bits[0], one, );
+ cr_assert_eq(bits->bits[1], other, );
+ bits_free(&bits);
+}
+
Test(bits, test_bits_copy) {
bits_t *bits = bits_new(10);
bits->bits[0] = 0b10101010;
generated by cgit v1.2.3-70-g09d2 (git 2.51.2) at 2025-11-08 09:16:11 +0000