diff options
Diffstat (limited to 'src')
35 files changed, 938 insertions, 254 deletions
diff --git a/src/cm/cm.h b/src/cm/cm.h index 546c0d5..d59db87 100644 --- a/src/cm/cm.h +++ b/src/cm/cm.h @@ -9,7 +9,7 @@ #define ECGEN_CM_H #include "io/cli.h" -#include "io/config.h" +#include "misc/config.h" /** * diff --git a/src/exhaustive/anomalous.h b/src/exhaustive/anomalous.h index ff6c053..cf8c208 100644 --- a/src/exhaustive/anomalous.h +++ b/src/exhaustive/anomalous.h @@ -10,7 +10,7 @@ #include <pari/pari.h> #include "arg.h" -#include "gen/types.h" +#include "misc/types.h" #include "io/cli.h" typedef struct disc_t { diff --git a/src/exhaustive/ansi.c b/src/exhaustive/ansi.c new file mode 100644 index 0000000..40fbf41 --- /dev/null +++ b/src/exhaustive/ansi.c @@ -0,0 +1,188 @@ + +#include <misc/config.h> +#include <misc/types.h> +#include "ansi.h" +#include "gen/seed.h" +#include "gen/field.h" +#include "util/bits.h" +#include "util/memory.h" +#include "io/output.h" + + +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); +} + +static void seed_hash(seed_t *seed) { + seed->hash20 = try_malloc(20); + bits_sha1(seed->seed, seed->hash20); +} + +static void seed_tsh(seed_t *seed, const config_t *cfg) { + pari_sp ltop = avma; + seed->ansi.t = utoi(cfg->bits); + seed->ansi.s = floorr( + rdivii(subis(seed->ansi.t, 1), stoi(160), DEFAULTPREC)); + seed->ansi.h = subii(seed->ansi.t, mulis(seed->ansi.s, 160)); + gerepileall(ltop, 3, &seed->ansi.t, &seed->ansi.s, &seed->ansi.h); +} + +GENERATOR(ansi_gen_seed_random) { + seed_t *seed = seed_new(); + seed->seed = bits_from_i(random_int(160)); + seed_hash(seed); + seed_tsh(seed, cfg); + curve->seed = seed; + return 1; +} + +GENERATOR(ansi_gen_seed_argument) { + seed_t *seed = seed_new(); + seed->seed = seed_stoi(cfg->seed); + seed_hash(seed); + seed_tsh(seed, cfg); + curve->seed = seed; + return 1; +} + +GENERATOR(ansi_gen_seed_input) { + pari_sp ltop = avma; + + GEN str = input_string("seed:"); + const char *cstr = GSTR(str); + if (!ansi_seed_valid(cstr)) { + fprintf(err, "SEED must be at least 160 bits(40 hex characters).\n"); + avma = ltop; + return 0; + } + + seed_t *seed = seed_new(); + seed->seed = seed_stoi(cstr); + seed_hash(seed); + seed_tsh(seed, cfg); + curve->seed = seed; + return 1; +} + +static bits_t *seed_process(seed_t *seed, const bits_t *first) { + pari_sp ltop = avma; + + bits_t *result = bits_copy(first); + + long is = itos(seed->ansi.s); + GEN seedi = bits_to_i(seed->seed); + GEN two_g = int2n(seed->seed->bitlen); + + for (long i = 1; i <= is; ++i) { + pari_sp btop = avma; + GEN inner = addis(seedi, i); + inner = modii(inner, two_g); + + bits_t *to_hash = bits_from_i(inner); + if (to_hash->bitlen < seed->seed->bitlen) { + bits_lengthenz(to_hash, seed->seed->bitlen - to_hash->bitlen); + } + unsigned char hashout[20]; + bits_sha1(to_hash, hashout); + bits_t *Wi = bits_from_raw(hashout, 160); + bits_concatz(result, Wi, NULL); + + bits_free(&to_hash); + bits_free(&Wi); + avma = btop; + } + + avma = ltop; + return result; +} + +UNROLL(ansi_unroll_seed) { + seed_free(&curve->seed); + return -1; +} + +static GENERATOR(ansi_gen_equation_fp) { + pari_sp ltop = avma; + bits_t *c0 = bits_from_raw(curve->seed->hash20, 160); + bits_shortenz(c0, 160 - itos(curve->seed->ansi.h)); + + bits_t *W0 = bits_copy(c0); + SET_BIT(W0->bits, 0, 0); + + bits_t *W = seed_process(curve->seed, W0); + + long ti = itos(curve->seed->ansi.t); + GEN r = gen_0; + for (long i = 1; i <= ti; ++i) { + GEN Wi = stoi(GET_BIT(W->bits, i - 1)); + r = addii(r, mulii(Wi, int2n(ti - i))); + } + curve->seed->ansi.r = r; + + GEN r_inv = Fp_invsafe(r, curve->field); + GEN a; + GEN b2; + do { + a = random_int(cfg->bits); + b2 = mulii(powis(a, 3), r_inv); + }while (!Fp_issquare(b2, curve->field)); + GEN b = Fp_sqrt(b2, curve->field); + + curve->a = a; + curve->b = b; + + gerepileall(ltop, 3, &curve->seed->ansi.r, &curve->a, &curve->b); + bits_free(&c0); + bits_free(&W0); + bits_free(&W); + return 1; +} + +static GENERATOR(ansi_gen_equation_f2m) { + pari_sp ltop = avma; + bits_t *b0 = bits_from_raw(curve->seed->hash20, 160); + bits_shortenz(b0, 160 - itos(curve->seed->ansi.h)); + + bits_t *b = seed_process(curve->seed, b0); + GEN ib = bits_to_i(b); + if (gequal0(ib)) { + avma = ltop; + return -3; + } + GEN a = random_int(cfg->bits); + curve->a = field_ielement(curve->field, a); + curve->b = field_ielement(curve->field, ib); + + gerepileall(ltop, 2, &curve->a, &curve->b); + bits_free(&b0); + bits_free(&b); + return 1; +} + +GENERATOR(ansi_gen_equation) { + switch (cfg->field) { + case FIELD_PRIME: return ansi_gen_equation_fp(curve, cfg, args); + case FIELD_BINARY: return ansi_gen_equation_f2m(curve, cfg, args); + default: pari_err_BUG("Field not prime or binary?"); + return INT_MIN; /* NOT REACHABLE */ + } +} diff --git a/src/exhaustive/ansi.h b/src/exhaustive/ansi.h new file mode 100644 index 0000000..74e787e --- /dev/null +++ b/src/exhaustive/ansi.h @@ -0,0 +1,55 @@ + +#ifndef ECGEN_ANSI_H +#define ECGEN_ANSI_H + +#include "misc/types.h" + +bool ansi_seed_valid(const char *hex_str); + +/** + * @brief + * @param curve A curve_t being generated + * @param cfg An application config + * @param args unused + * @return state diff + */ +GENERATOR(ansi_gen_seed_random); + +/** + * @brief + * @param curve A curve_t being generated + * @param cfg An application config + * @param args unused + * @return state diff + */ +GENERATOR(ansi_gen_seed_argument); + +/** + * @brief + * @param curve A curve_t being generated + * @param cfg An application config + * @param args unused + * @return state diff + */ +GENERATOR(ansi_gen_seed_input); + +/** + * @brief + * @param curve + * @param cfg + * @param from + * @param to + * @return + */ +UNROLL(ansi_unroll_seed); + +/** + * @brief + * @param curve A curve_t being generated + * @param cfg An application config + * @param args unused + * @return state diff + */ +GENERATOR(ansi_gen_equation); + +#endif //ECGEN_ANSI_H diff --git a/src/exhaustive/arg.h b/src/exhaustive/arg.h index 1a4d0ed..415008c 100644 --- a/src/exhaustive/arg.h +++ b/src/exhaustive/arg.h @@ -8,7 +8,7 @@ #ifndef ECGEN_ARG_H #define ECGEN_ARG_H -#include "gen/types.h" +#include "misc/types.h" /** * @brief diff --git a/src/exhaustive/exhaustive.c b/src/exhaustive/exhaustive.c index 6b77f3a..0506409 100644 --- a/src/exhaustive/exhaustive.c +++ b/src/exhaustive/exhaustive.c @@ -2,33 +2,35 @@ * ecgen, tool for generating Elliptic curve domain parameters * Copyright (C) 2017 J08nY */ +#include <misc/config.h> #include "exhaustive.h" #include "anomalous.h" +#include "ansi.h" #include "gen/curve.h" #include "gen/equation.h" #include "gen/field.h" #include "gen/gens.h" #include "gen/order.h" #include "gen/point.h" -#include "gen/seed.h" #include "io/output.h" #include "util/memory.h" static void exhaustive_ginit(gen_t *generators, const config_t *cfg) { - if (cfg->from_seed) { + if (cfg->ansi) { // setup ANSI X9.62 generators if (cfg->seed) { - generators[OFFSET_SEED] = &seed_gen_argument; + generators[OFFSET_SEED] = &ansi_gen_seed_argument; } else { if (cfg->random) { - generators[OFFSET_SEED] = &seed_gen_random; + generators[OFFSET_SEED] = &ansi_gen_seed_random; } else { - generators[OFFSET_SEED] = &seed_gen_input; + generators[OFFSET_SEED] = &ansi_gen_seed_input; } } - generators[OFFSET_A] = &a_gen_seed; - generators[OFFSET_B] = &b_gen_seed; - generators[OFFSET_CURVE] = &curve_gen_seed; + generators[OFFSET_A] = &gen_skip; + generators[OFFSET_B] = &ansi_gen_equation; + generators[OFFSET_CURVE] = &curve_gen_nonzero; + generators[OFFSET_ORDER] = &order_gen_any; } else { // setup normal generators generators[OFFSET_SEED] = &gen_skip; @@ -142,7 +144,11 @@ static void exhaustive_ainit(arg_t **argss, const config_t *cfg) { } void exhaustive_uinit(unroll_t *unrolls, const config_t *cfg) { - unrolls[OFFSET_SEED] = &unroll_skip; + if (cfg->ansi) { + unrolls[OFFSET_SEED] = &ansi_unroll_seed; + } else { + unrolls[OFFSET_SEED] = &unroll_skip; + } unrolls[OFFSET_FIELD] = &unroll_skip; unrolls[OFFSET_A] = &unroll_skip; unrolls[OFFSET_B] = &unroll_skip; @@ -176,8 +182,7 @@ int exhaustive_gen_retry(curve_t *curve, const config_t *cfg, if (diff <= 0) { if (diff == INT_MIN || state + diff < 0) { - fprintf(err, "Error generating a curve. state = %i\n", - state); + fprintf(err, "Error generating a curve. state = %i\n", state); return 0; } // record try diff --git a/src/exhaustive/exhaustive.h b/src/exhaustive/exhaustive.h index 3b26d73..446dff2 100644 --- a/src/exhaustive/exhaustive.h +++ b/src/exhaustive/exhaustive.h @@ -8,7 +8,7 @@ #ifndef ECGEN_GENERATORS_H #define ECGEN_GENERATORS_H -#include "gen/types.h" +#include "misc/types.h" /** * diff --git a/src/gen/curve.c b/src/gen/curve.c index ea5ed95..3a8d00d 100644 --- a/src/gen/curve.c +++ b/src/gen/curve.c @@ -2,6 +2,7 @@ * ecgen, tool for generating Elliptic curve domain parameters * Copyright (C) 2017 J08nY */ +#include <misc/config.h> #include "curve.h" #include "point.h" #include "seed.h" @@ -130,29 +131,6 @@ GENERATOR(curve_gen_nonzero) { } } -static int curve_gen_seed_fp(curve_t *curve, const config_t *cfg, arg_t *args) { - // TODO implement - return INT_MIN; -} - -static int curve_gen_seed_f2m(curve_t *curve, const config_t *cfg, - arg_t *args) { - // TODO implement - return INT_MIN; -} - -GENERATOR(curve_gen_seed) { - switch (typ(curve->field)) { - case t_INT: - return curve_gen_seed_fp(curve, cfg, args); - case t_FFELT: - return curve_gen_seed_f2m(curve, cfg, args); - default: - pari_err_TYPE("curve_gen_seed", curve->field); - return INT_MIN; /* NOT REACHABLE */ - } -} - UNROLL(curve_unroll) { if (curve->curve) { obj_free(curve->curve); diff --git a/src/gen/curve.h b/src/gen/curve.h index 2e7651f..f5e6553 100644 --- a/src/gen/curve.h +++ b/src/gen/curve.h @@ -9,7 +9,7 @@ #define ECGEN_CURVE_H #include <pari/pari.h> -#include "types.h" +#include "misc/types.h" /** * GENERATOR(gen_t) @@ -35,18 +35,6 @@ GENERATOR(curve_gen_any); */ GENERATOR(curve_gen_nonzero); -/** - * GENERATOR(gen_t) - * Creates a curve GEN in curve_t curve from field, a and b. Using the ANSI - * X9.62 verifiably random algorithm. - * Succeeds if a curve exists(non-zero discriminant). - * - * @param curve A curve_t being generated - * @param cfg An application config - * @param args unused - * @return state diff - */ -GENERATOR(curve_gen_seed); /** * diff --git a/src/gen/equation.c b/src/gen/equation.c index 9524df7..33d41a9 100644 --- a/src/gen/equation.c +++ b/src/gen/equation.c @@ -56,10 +56,6 @@ GENERATOR(a_gen_one) { return 1; } -GENERATOR(a_gen_seed) { - // TODO implement - return INT_MIN; -} GENERATOR(b_gen_random) { curve->b = genrand(curve->field); @@ -111,11 +107,6 @@ GENERATOR(b_gen_one) { return 1; } -GENERATOR(b_gen_seed) { - // TODO implement - return INT_MIN; -} - void equation_quit(void) { if (a && isclone(a)) { gunclone(a); diff --git a/src/gen/equation.h b/src/gen/equation.h index 58e2e6e..665c153 100644 --- a/src/gen/equation.h +++ b/src/gen/equation.h @@ -8,7 +8,7 @@ #ifndef ECGEN_EQUATION_H #define ECGEN_EQUATION_H -#include "types.h" +#include "misc/types.h" /** * GENERATOR(gen_t) diff --git a/src/gen/field.c b/src/gen/field.c index 482bcc5..9a908cc 100644 --- a/src/gen/field.c +++ b/src/gen/field.c @@ -13,7 +13,8 @@ static GEN field_binaryr(unsigned long bits) { if (poly_exists(bits)) { return poly_find_gen(bits); } else { - fprintf(err, "Unable to find a suitable binary field. Use an explicit one."); + fprintf(err, + "Unable to find a suitable binary field. Use an explicit one."); exit(1); } } diff --git a/src/gen/field.h b/src/gen/field.h index 04af2c6..da31298 100644 --- a/src/gen/field.h +++ b/src/gen/field.h @@ -8,7 +8,7 @@ #ifndef ECGEN_FIELD_H #define ECGEN_FIELD_H -#include "types.h" +#include "misc/types.h" /** * GENERATOR(gen_t) diff --git a/src/gen/gens.h b/src/gen/gens.h index f46efbf..c9e8169 100644 --- a/src/gen/gens.h +++ b/src/gen/gens.h @@ -9,7 +9,7 @@ #ifndef ECGEN_GENS_H #define ECGEN_GENS_H -#include "types.h" +#include "misc/types.h" /** * GENERATOR(gen_t) diff --git a/src/gen/order.h b/src/gen/order.h index da62c4d..e798012 100644 --- a/src/gen/order.h +++ b/src/gen/order.h @@ -8,7 +8,7 @@ #ifndef ECGEN_ORDER_H #define ECGEN_ORDER_H -#include "types.h" +#include "misc/types.h" /** * GENERATOR(gen_t) diff --git a/src/gen/point.h b/src/gen/point.h index c8cae17..fdca6f7 100644 --- a/src/gen/point.h +++ b/src/gen/point.h @@ -8,7 +8,7 @@ #ifndef ECGEN_POINT_H #define ECGEN_POINT_H -#include "types.h" +#include "misc/types.h" /** * diff --git a/src/gen/seed.c b/src/gen/seed.c index 505493a..1653a50 100644 --- a/src/gen/seed.c +++ b/src/gen/seed.c @@ -4,13 +4,21 @@ */ #include "seed.h" +#include <misc/config.h> #include "io/output.h" +#include "misc/types.h" +#include "util/bits.h" #include "util/memory.h" seed_t *seed_new(void) { return try_calloc(sizeof(seed_t)); } seed_t *seed_copy(const seed_t *src, seed_t *dest) { - if (src->seed) dest->seed = gcopy(src->seed); + if (src->seed) { + dest->seed = bits_copy(src->seed); + } + if (src->hash20) { + dest->hash20 = try_memdup(src->hash20, 20); + } return dest; } @@ -20,8 +28,7 @@ seed_t *seed_new_copy(const seed_t *src) { } seed_t *seed_clone(const seed_t *src, seed_t *dest) { - if (src->seed) dest->seed = gclone(src->seed); - return dest; + return seed_copy(src, dest); } seed_t *seed_new_clone(const seed_t *src) { @@ -31,75 +38,14 @@ seed_t *seed_new_clone(const seed_t *src) { void seed_free(seed_t **seed) { if (*seed) { - if ((*seed)->seed && isclone((*seed)->seed)) { - gunclone((*seed)->seed); + if ((*seed)->seed) { + bits_free(&(*seed)->seed); + } + if ((*seed)->hash20) { + try_free((*seed)->hash20); } try_free(*seed); *seed = NULL; } } -static GEN seed_stoi(const char *cstr) { - pari_sp ltop = avma; - GEN seed = gen_0; - - size_t len = strlen(cstr); - for (size_t i = 0; i < len; ++i) { - pari_sp btop = avma; - GEN s = stoi(cstr[i]); - s = shifti(s, (len - i - 1) * 8); - seed = addii(seed, s); - gerepileall(btop, 1, &seed); - } - - return gerepilecopy(ltop, seed); -} - -static char *seed_itos(GEN seed) { - pari_sp ltop = avma; - GEN bits = binary_zv(seed); - - long len = glength(bits); - long bytes = (len / 8) + (len % 8 == 0 ? 0 : 1); - char *result = try_malloc((size_t)bytes); - - for (long i = 0; i < len; ++i) { - // TODO - } - avma = ltop; - return result; -} - -GENERATOR(seed_gen_random) { - curve->seed = seed_new(); - curve->seed->seed = random_int(160); - curve->seed->raw = seed_itos(curve->seed->seed); - curve->seed->raw_len = strlen(curve->seed->raw); - return 1; -} - -GENERATOR(seed_gen_argument) { - curve->seed = seed_new(); - curve->seed->seed = seed_stoi(cfg->seed); - curve->seed->raw = cfg->seed; - curve->seed->raw_len = strlen(cfg->seed); - return 1; -} - -GENERATOR(seed_gen_input) { - pari_sp ltop = avma; - - GEN str = input_string("seed:"); - const char *cstr = GSTR(str); - if (strlen(cstr) < 20) { - fprintf(err, "SEED must be at least 160 bits(20 characters).\n"); - avma = ltop; - return 0; - } - - GEN seed = seed_stoi(cstr); - - curve->seed = seed_new(); - curve->seed->seed = gerepilecopy(ltop, seed); - return 1; -} diff --git a/src/gen/seed.h b/src/gen/seed.h index 82eb499..c89fc1d 100644 --- a/src/gen/seed.h +++ b/src/gen/seed.h @@ -9,16 +9,16 @@ #define ECGEN_SEED_H #include "io/input.h" -#include "types.h" +#include "misc/types.h" /** - * + * @brief * @return */ seed_t *seed_new(void); /** - * + * @brief * @param src * @param dest * @return @@ -26,14 +26,14 @@ seed_t *seed_new(void); seed_t *seed_copy(const seed_t *src, seed_t *dest); /** - * + * @brief * @param src * @return */ seed_t *seed_new_copy(const seed_t *src); /** - * + * @brief * @param src * @param dest * @return @@ -41,43 +41,17 @@ seed_t *seed_new_copy(const seed_t *src); seed_t *seed_clone(const seed_t *src, seed_t *dest); /** - * + * @brief * @param src * @return */ seed_t *seed_new_clone(const seed_t *src); /** - * + * @brief * @param seed */ void seed_free(seed_t **seed); -/** - * - * @param curve A curve_t being generated - * @param cfg An application config - * @param args unused - * @return state diff - */ -GENERATOR(seed_gen_random); - -/** - * - * @param curve A curve_t being generated - * @param cfg An application config - * @param args unused - * @return state diff - */ -GENERATOR(seed_gen_argument); - -/** - * - * @param curve A curve_t being generated - * @param cfg An application config - * @param args unused - * @return state diff - */ -GENERATOR(seed_gen_input); #endif // ECGEN_SEED_H diff --git a/src/invalid/invalid.h b/src/invalid/invalid.h index 035692c..a08c5d8 100644 --- a/src/invalid/invalid.h +++ b/src/invalid/invalid.h @@ -8,7 +8,7 @@ #ifndef ECGEN_INVALID_H #define ECGEN_INVALID_H -#include "io/config.h" +#include "misc/config.h" /** * diff --git a/src/invalid/invalid_thread.h b/src/invalid/invalid_thread.h index bedaf60..0f1b4d0 100644 --- a/src/invalid/invalid_thread.h +++ b/src/invalid/invalid_thread.h @@ -9,7 +9,7 @@ #define ECGEN_INVALID_THREAD_H #include <pthread.h> -#include "gen/types.h" +#include "misc/types.h" typedef enum { STATE_FREE, STATE_GENERATING, STATE_GENERATED } state_e; diff --git a/src/io/cli.c b/src/io/cli.c index 1cbf3b9..4545e7f 100644 --- a/src/io/cli.c +++ b/src/io/cli.c @@ -5,7 +5,8 @@ #include "cli.h" #include <string.h> #include <unistd.h> -#include "config.h" +#include "misc/config.h" +#include "exhaustive/ansi.h" char cli_doc[] = "ecgen, tool for generating Elliptic curve domain parameters.\v(C) 2017 " @@ -18,7 +19,7 @@ enum opt_keys { OPT_PRIME = 'p', OPT_COFACTOR = 'k', OPT_RANDOM = 'r', - OPT_SEED = 's', + OPT_ANSI = 's', OPT_INVALID = 'i', OPT_ORDER = 'n', OPT_KOBLITZ = 'K', @@ -51,7 +52,7 @@ struct argp_option cli_options[] = { {"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/nonprime/none).", 2}, - {"seed", OPT_SEED, "SEED", OPTION_ARG_OPTIONAL, "Generate a curve from SEED (ANSI X9.62 verifiable procedure). **NOT IMPLEMENTED**", 2}, + {"ansi", OPT_ANSI, "SEED", OPTION_ARG_OPTIONAL, "Generate a curve from SEED (ANSI X9.62 verifiable procedure).", 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}, @@ -197,14 +198,13 @@ error_t cli_parse(int key, char *arg, struct argp_state *state) { } break; } - case OPT_SEED: - cfg->from_seed = true; + case OPT_ANSI: + cfg->ansi = true; if (arg) { - // ANSI X9.62 specifies seed as at least 160 bits in length. - if (strlen(arg) < 20) { + if (!ansi_seed_valid(arg)) { argp_failure( state, 1, 0, - "SEED must be at least 160 bits (20 characters)."); + "SEED must be at least 160 bits (40 characters)."); } cfg->seed = arg; } @@ -236,13 +236,13 @@ error_t cli_parse(int key, char *arg, struct argp_state *state) { } // Invalid is not prime or seed by definition. if (cfg->invalid && - (cfg->prime || cfg->from_seed || cfg->cofactor)) { + (cfg->prime || cfg->ansi || cfg->cofactor)) { // not seed, not prime argp_failure(state, 1, 0, "Invalid curve generation can not generate curves " "from seed, exhaustive or prime order."); } - if (cfg->cm && (cfg->prime || cfg->from_seed || cfg->invalid || + if (cfg->cm && (cfg->prime || cfg->ansi || cfg->invalid || cfg->cofactor || cfg->anomalous)) { argp_failure(state, 1, 0, "Fixed order curve generation can not generate " @@ -251,7 +251,7 @@ error_t cli_parse(int key, char *arg, struct argp_state *state) { "prime."); } if (cfg->anomalous && - (cfg->binary_field || cfg->cofactor || cfg->from_seed || + (cfg->binary_field || cfg->cofactor || cfg->ansi || cfg->cm || cfg->invalid || cfg->koblitz)) { argp_failure( state, 1, 0, diff --git a/src/io/input.c b/src/io/input.c index 2c0398a..f86afe4 100644 --- a/src/io/input.c +++ b/src/io/input.c @@ -26,20 +26,8 @@ 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++])); - -/* if (len <= 3 || !(line[0] == '0' && (line[1] == 'x' || line[1] == 'X'))) { - char *new_line = try_realloc(line, (size_t)(len + 2)); - memmove(new_line + 2, new_line, (size_t)len); - new_line[0] = '0'; - new_line[1] = 'x'; - if (!feof(in)) { - new_line[len + 1] = 0; - } else { - new_line[len + 2] = 0; - } - line = new_line; - }*/ + for (size_t i = 0, j = 0; (line[j] = line[i]); j += !isspace(line[i++])) + ; pari_sp ltop = avma; GEN in = strtoi(line); diff --git a/src/io/input.h b/src/io/input.h index 2759973..eb836e2 100644 --- a/src/io/input.h +++ b/src/io/input.h @@ -8,7 +8,7 @@ #ifndef ECGEN_INPUT_H #define ECGEN_INPUT_H -#include "gen/types.h" +#include "misc/types.h" #include "util/random.h" /** diff --git a/src/io/output.c b/src/io/output.c index 2d05bec..4e951a2 100644 --- a/src/io/output.c +++ b/src/io/output.c @@ -5,6 +5,7 @@ #include "output.h" #include <parson/parson.h> +#include "util/bits.h" #include "gen/field.h" #include "util/memory.h" @@ -29,23 +30,23 @@ char *output_scsv(curve_t *curve, const config_t *cfg) { switch (cfg->field) { case FIELD_PRIME: params[OFFSET_FIELD] = - pari_sprintf("%P0#*x", cfg->hex_digits, curve->field); + pari_sprintf("%P0#*x", cfg->hex_digits, curve->field); break; case FIELD_BINARY: { GEN field = field_params(curve->field); params[OFFSET_FIELD] = - pari_sprintf("%P#x,%P#x,%P#x,%P#x", gel(field, 1), - gel(field, 2), gel(field, 3), gel(field, 4)); + pari_sprintf("%P#x,%P#x,%P#x,%P#x", gel(field, 1), + gel(field, 2), gel(field, 3), gel(field, 4)); break; } } if (curve->a) params[OFFSET_A] = - pari_sprintf("%P0#*x", cfg->hex_digits, field_elementi(curve->a)); + pari_sprintf("%P0#*x", cfg->hex_digits, field_elementi(curve->a)); if (curve->b) params[OFFSET_B] = - pari_sprintf("%P0#*x", cfg->hex_digits, field_elementi(curve->b)); + pari_sprintf("%P0#*x", cfg->hex_digits, field_elementi(curve->b)); if (curve->generators) { char *gens[curve->ngens]; @@ -55,8 +56,8 @@ char *output_scsv(curve_t *curve, const config_t *cfg) { GEN x = field_elementi(gel(generator->point, 1)); GEN y = field_elementi(gel(generator->point, 2)); gens[i] = pari_sprintf("%P0#*x,%P0#*x,%P#x,%P#x", cfg->hex_digits, - x, cfg->hex_digits, y, generator->order, - generator->cofactor); + x, cfg->hex_digits, y, generator->order, + generator->cofactor); len += strlen(gens[i]); } size_t lenn = sizeof(char) * (len + curve->ngens); @@ -70,7 +71,7 @@ char *output_scsv(curve_t *curve, const config_t *cfg) { if (curve->order) params[OFFSET_ORDER] = - pari_sprintf("%P0#*x", cfg->hex_digits, curve->order); + pari_sprintf("%P0#*x", cfg->hex_digits, curve->order); if (curve->points) { char *points[curve->npoints]; @@ -80,7 +81,7 @@ char *output_scsv(curve_t *curve, const config_t *cfg) { GEN x = field_elementi(gel(point->point, 1)); GEN y = field_elementi(gel(point->point, 2)); points[i] = pari_sprintf("%P0#*x,%P0#*x,%P#x", cfg->hex_digits, x, - cfg->hex_digits, y, point->order); + cfg->hex_digits, y, point->order); len += strlen(points[i]); } size_t lenn = sizeof(char) * (len + curve->npoints); @@ -150,9 +151,20 @@ static JSON_Value *output_jjson(curve_t *curve, const config_t *cfg) { pari_free(e3); break; } - default: fprintf(err, "Error, field has unknown amount of elements.\n"); + default: + fprintf(err, "Error, field has unknown amount of elements.\n"); exit(1); } + if (curve->seed) { + char *hex_str = bits_to_hex(curve->seed->seed); + char *hex = try_calloc(strlen(hex_str) + 3); + hex[0] = '0'; + hex[1] = 'x'; + strcat(hex, hex_str); + json_object_set_string(root_object, "seed", hex); + try_free(hex_str); + try_free(hex); + } char *a = pari_sprintf("%P0#*x", cfg->hex_digits, field_elementi(curve->a)); json_object_set_string(root_object, "a", a); @@ -172,13 +184,13 @@ static JSON_Value *output_jjson(curve_t *curve, const config_t *cfg) { JSON_Object *point_object = json_value_get_object(point_value); char *x = pari_sprintf( - "%P0#*x", cfg->hex_digits, - field_elementi(gel(curve->generators[i]->point, 1))); + "%P0#*x", cfg->hex_digits, + field_elementi(gel(curve->generators[i]->point, 1))); json_object_set_string(point_object, "x", x); pari_free(x); char *y = pari_sprintf( - "%P0#*x", cfg->hex_digits, - field_elementi(gel(curve->generators[i]->point, 2))); + "%P0#*x", cfg->hex_digits, + field_elementi(gel(curve->generators[i]->point, 2))); json_object_set_string(point_object, "y", y); pari_free(y); char *p_order = pari_sprintf("%P#x", curve->generators[i]->order); @@ -186,7 +198,7 @@ static JSON_Value *output_jjson(curve_t *curve, const config_t *cfg) { pari_free(p_order); if (curve->generators[i]->cofactor) { char *cofactor = - pari_sprintf("%P#x", curve->generators[i]->cofactor); + pari_sprintf("%P#x", curve->generators[i]->cofactor); json_object_set_string(point_object, "cofactor", cofactor); pari_free(cofactor); } @@ -206,13 +218,13 @@ static JSON_Value *output_jjson(curve_t *curve, const config_t *cfg) { JSON_Object *point_object = json_value_get_object(point_value); char *x = - pari_sprintf("%P0#*x", cfg->hex_digits, - field_elementi(gel(curve->points[i]->point, 1))); + pari_sprintf("%P0#*x", cfg->hex_digits, + field_elementi(gel(curve->points[i]->point, 1))); json_object_set_string(point_object, "x", x); pari_free(x); char *y = - pari_sprintf("%P0#*x", cfg->hex_digits, - field_elementi(gel(curve->points[i]->point, 2))); + pari_sprintf("%P0#*x", cfg->hex_digits, + field_elementi(gel(curve->points[i]->point, 2))); json_object_set_string(point_object, "y", y); pari_free(y); char *p_order = pari_sprintf("%P#x", curve->points[i]->order); @@ -220,7 +232,7 @@ static JSON_Value *output_jjson(curve_t *curve, const config_t *cfg) { pari_free(p_order); if (curve->points[i]->cofactor) { char *cofactor = - pari_sprintf("%P#x", curve->points[i]->cofactor); + pari_sprintf("%P#x", curve->points[i]->cofactor); json_object_set_string(point_object, "cofactor", cofactor); pari_free(cofactor); } diff --git a/src/io/output.h b/src/io/output.h index 586f4e8..6c241d5 100644 --- a/src/io/output.h +++ b/src/io/output.h @@ -10,7 +10,7 @@ #include <pari/pari.h> #include <stdbool.h> -#include "gen/types.h" +#include "misc/types.h" #ifdef DEBUG diff --git a/src/math/subgroups.c b/src/math/subgroups.c index 93526ae..45523ad 100644 --- a/src/math/subgroups.c +++ b/src/math/subgroups.c @@ -54,6 +54,7 @@ static GEN subgroups_divisors(GEN order) { * @return a t_VEC of factors */ static GEN subgroups_2n_factors(GEN factors, size_t min_bits) { + pari_sp ltop = avma; long nprimes = glength(factors); if (nprimes == min_bits) return NULL; GEN amount = int2n(nprimes); @@ -77,17 +78,8 @@ static GEN subgroups_2n_factors(GEN factors, size_t min_bits) { avma = btop; } } - GEN sorted = sort(groups); - size_t k = 1; - for (size_t j = 1; j <= i; j++) { - GEN k_value = gel(sorted, k); - GEN j_value = gel(sorted, j); - if (!gequal(k_value, j_value)) { - gel(sorted, ++k) = j_value; - } - } - sorted = vec_shorten(sorted, k); - return sorted; + GEN ret = gtoset(groups); + return gerepilecopy(ltop, ret); } /** diff --git a/src/math/subgroups.h b/src/math/subgroups.h index fee095b..1c11d4c 100644 --- a/src/math/subgroups.h +++ b/src/math/subgroups.h @@ -9,7 +9,7 @@ #define ECGEN_SUBGROUPS_H #include <pari/pari.h> -#include "gen/types.h" +#include "misc/types.h" /** * @brief Enumerates prime subgroup orders of a given curve. diff --git a/src/io/config.h b/src/misc/config.h index 0894b5e..7b9a9dc 100644 --- a/src/io/config.h +++ b/src/misc/config.h @@ -41,7 +41,7 @@ typedef struct { long koblitz_value; bool cofactor; long cofactor_bound; - bool from_seed; + bool ansi; char *seed; bool unique; struct points_s points; diff --git a/src/gen/types.c b/src/misc/types.c index 63d5401..63d5401 100644 --- a/src/gen/types.c +++ b/src/misc/types.c diff --git a/src/gen/types.h b/src/misc/types.h index 5500e85..b75394c 100644 --- a/src/gen/types.h +++ b/src/misc/types.h @@ -10,15 +10,37 @@ #include <limits.h> #include <pari/pari.h> -#include "io/config.h" +#include "misc/config.h" + +/** + * @brief + * @param bits + * @param bitlen + * @param allocated + */ +typedef struct { + unsigned char *bits; + size_t bitlen; + size_t allocated; +} bits_t; /** * @brief */ typedef struct seed_t { - char *raw; - size_t raw_len; - GEN seed; + bits_t *seed; + unsigned char *hash20; + union { + struct { + GEN t; + GEN s; + GEN h; + GEN r; + } ansi; + struct { + bits_t *f; + } brainpool; + }; } seed_t; /** @@ -91,7 +113,8 @@ typedef struct { * @return state diff */ #define GENERATOR(gen_name) \ - int gen_name(curve_t *curve, const config_t *cfg, arg_t *args) + int gen_name(curve_t *curve, const config_t *cfg, arg_t *args) + typedef GENERATOR((*gen_t)); /** @@ -103,8 +126,9 @@ typedef GENERATOR((*gen_t)); * @return */ #define UNROLL(unroll_name) \ - int unroll_name(curve_t *curve, const config_t *cfg, pari_sp from, \ - pari_sp to) + int unroll_name(curve_t *curve, const config_t *cfg, pari_sp from, \ + pari_sp to) + typedef UNROLL((*unroll_t)); /** diff --git a/src/util/bits.c b/src/util/bits.c new file mode 100644 index 0000000..55d5bf3 --- /dev/null +++ b/src/util/bits.c @@ -0,0 +1,430 @@ +/* + * ecgen, tool for generating Elliptic curve domain parameters + * Copyright (C) 2017 J08nY + */ + +#include "bits.h" +#include <sha1/sha1.h> +#include "util/memory.h" + +bits_t *bits_new(size_t bit_len) { + bits_t *result = try_calloc(sizeof(bits_t)); + size_t byte_len = BYTE_LEN(bit_len); + if (byte_len > 0) result->bits = try_calloc(byte_len); + result->allocated = byte_len; + result->bitlen = bit_len; + return result; +} + +bits_t *bits_copy(const bits_t *bits) { + bits_t *result = try_calloc(sizeof(bits_t)); + result->bitlen = bits->bitlen; + result->allocated = bits->allocated; + if (bits->allocated != 0) + result->bits = try_memdup(bits->bits, result->allocated); + return result; +} + +void bits_free(bits_t **bits) { + if (*bits) { + if ((*bits)->bits) { + try_free((*bits)->bits); + } + try_free(*bits); + *bits = NULL; + } +} + +bits_t *bits_from_i(GEN i) { + pari_sp ltop = avma; + GEN bitvec = binary_zv(i); + size_t bit_len = (size_t)glength(bitvec); + bits_t *result = bits_new(bit_len); + for (size_t j = 0; j < bit_len; ++j) { + if (gel(bitvec, j + 1) == (GEN)1) { + result->bits[j / 8] |= 1 << (7 - (j % 8)); + } + } + avma = ltop; + return result; +} + +bits_t *bits_from_hex(const char *hex_str) { + size_t nibble_len = strlen(hex_str); + bits_t *result = bits_new(nibble_len * 4); + for (size_t i = 0; i < nibble_len; ++i) { + char hex = hex_str[i]; + char nibble = 0; + if ('0' <= hex && hex <= '9') { + nibble = (char)(hex - '0'); + } else if ('a' <= hex && hex <= 'f') { + nibble = (char)(hex - 'a' + 10); + } else if ('A' <= hex && hex <= 'F') { + nibble = (char)(hex - 'A' + 10); + } + result->bits[i / 2] |= (nibble << (1 - (i % 2)) * 4); + } + return result; +} + +bits_t *bits_from_bin(const char *bin_str) { + size_t bit_len = strlen(bin_str); + bits_t *result = bits_new(bit_len); + for (size_t i = 0; i < bit_len; ++i) { + if (bin_str[i] == '1') { + result->bits[i / 8] |= 1 << (7 - (i % 8)); + } + } + return result; +} + +bits_t *bits_from_raw(const unsigned char *bits, size_t bit_len) { + bits_t *result = try_calloc(sizeof(bits_t)); + result->bitlen = bit_len; + result->allocated = BYTE_LEN(bit_len); + if (bit_len > 0) result->bits = try_memdup(bits, result->allocated); + return result; +} + +bits_t *bits_from_bitvec(GEN v) { + size_t bit_len = (size_t)glength(v); + bits_t *result = bits_new(bit_len); + for (size_t i = 0; i < bit_len; ++i) { + if (gel(v, i + 1) == (GEN)1) result->bits[i / 8] |= 1 << (7 - (i % 8)); + } + return result; +} + +GEN bits_to_i(const bits_t *bits) { + pari_sp ltop = avma; + GEN result = stoi(0); + for (size_t i = 0; i < bits->bitlen; ++i) { + if (GET_BIT(bits->bits, i) != 0) + result = addii(result, int2n(bits->bitlen - i - 1)); + } + return gerepileupto(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. + for (size_t i = 0; i < BYTE_LEN(bits->bitlen); ++i) { + sprintf(result + (i * 2), "%02x", bits->bits[i]); + } + return result; +} + +char *bits_to_bin(const bits_t *bits) { + char *result = try_calloc(bits->bitlen + 1); + for (size_t i = 0; i < bits->bitlen; ++i) { + sprintf(result + i, "%1u", GET_BIT(bits->bits, i)); + } + return result; +} + +unsigned char *bits_to_raw(const bits_t *bits) { + if (bits->bitlen == 0) { + return NULL; + } + return try_memdup(bits->bits, BYTE_LEN(bits->bitlen)); +} + +size_t bits_to_rawlen(const bits_t *bits) { return BYTE_LEN(bits->bitlen); } + +GEN bits_to_bitvec(const bits_t *bits) { + GEN bitvec = gtovecsmall0(gen_0, bits->bitlen); + for (size_t i = 0; i < bits->bitlen; ++i) { + if (GET_BIT(bits->bits, i) != 0) gel(bitvec, i + 1) = (GEN)1; + } + return bitvec; +} + +static unsigned char or_func(unsigned char one, unsigned char other) { + return one | other; +} + +static unsigned char and_func(unsigned char one, unsigned char other) { + return one & other; +} + +static bits_t *bits_bitwise(const bits_t *one, const bits_t *other, + unsigned char (*bitwise_func)(unsigned char, + unsigned char)) { + const bits_t *shorter; + const bits_t *longer; + if (one->bitlen > other->bitlen) { + shorter = other; + longer = one; + } else { + shorter = one; + longer = other; + } + + bits_t *result = bits_new(longer->bitlen); + for (size_t i = 0; i < longer->bitlen; ++i) { + size_t longer_pos = longer->bitlen - i - 1; + + unsigned char longer_bit = + (unsigned char)GET_BIT(longer->bits, longer_pos); + unsigned char shorter_bit = 0; + if (shorter->bitlen > i) { + size_t shorter_pos = shorter->bitlen - i - 1; + shorter_bit = (unsigned char)GET_BIT(shorter->bits, shorter_pos); + } + + unsigned char result_bit = bitwise_func(longer_bit, shorter_bit); + result->bits[longer_pos / 8] |= result_bit << (7 - (longer_pos % 8)); + } + + return result; +} + +void bits_concatzv(bits_t *one, va_list valist) { + const bits_t *next; + while ((next = va_arg(valist, const bits_t *)) != NULL) { + if (next->bitlen == 0) continue; + size_t new_bitlen = one->bitlen + next->bitlen; + size_t new_alloc = BYTE_LEN(new_bitlen); + if (new_alloc > one->allocated) { + one->bits = try_realloc(one->bits, new_alloc); + for (size_t i = one->allocated; i < new_alloc; ++i) { + one->bits[i] = 0; + } + one->allocated = new_alloc; + } + for (size_t j = 0; j < next->bitlen; ++j) { + SET_BIT(one->bits, one->bitlen + j, GET_BIT(next->bits, j)); + } + one->bitlen = new_bitlen; + } +} + +void bits_concatz(bits_t *one, ...) { + va_list valist; + va_start(valist, one); + + bits_concatzv(one, valist); + + va_end(valist); +} + +bits_t *bits_concat(const bits_t *one, ...) { + va_list valist; + va_start(valist, one); + + bits_t *result = bits_copy(one); + + bits_concatzv(result, valist); + + va_end(valist); + return result; +} + +bits_t *bits_or(const bits_t *one, const bits_t *other) { + return bits_bitwise(one, other, or_func); +} + +bits_t *bits_and(const bits_t *one, const bits_t *other) { + return bits_bitwise(one, other, and_func); +} + +void bits_notz(bits_t *bits) { + if (bits->bitlen == 0) return; + for (size_t i = 0; i < bits->bitlen / 8; ++i) { + bits->bits[i] = ~bits->bits[i]; + } + if (bits->bitlen % 8 != 0) { + size_t mask_len = bits->bitlen % 8; + unsigned char mask = 0; + for (size_t i = 7; i >= 0; --i) { + mask |= 1 << i; + if (--mask_len == 0) break; + } + size_t last_pos = (bits->bitlen / 8); + unsigned char anti_mask = ~mask; + unsigned char last_byte = bits->bits[last_pos]; + bits->bits[last_pos] = (~last_byte & mask) | (last_byte & anti_mask); + } +} + +bits_t *bits_not(const bits_t *bits) { + bits_t *result = bits_copy(bits); + bits_notz(result); + return result; +} + +void bits_rotz(bits_t *bits) { + unsigned char original_bits[bits->allocated]; + for (size_t i = 0; i < bits->allocated; ++i) { + original_bits[i] = bits->bits[i]; + bits->bits[i] = 0; + } + for (size_t i = 0; i < bits->bitlen / 2; ++i) { + size_t left_pos = i; + size_t right_pos = bits->bitlen - i - 1; + unsigned char left_bit = + (unsigned char)GET_BIT(original_bits, left_pos); + unsigned char right_bit = + (unsigned char)GET_BIT(original_bits, right_pos); + bits->bits[right_pos / 8] |= left_bit << (7 - (right_pos % 8)); + bits->bits[left_pos / 8] |= right_bit << (7 - (left_pos % 8)); + } + if (bits->bitlen % 2 == 1) { + size_t middle_pos = bits->bitlen / 2; + + unsigned char middle_bit = + (unsigned char)GET_BIT(original_bits, middle_pos); + bits->bits[middle_pos / 8] |= middle_bit << (7 - (middle_pos % 8)); + } +} + +bits_t *bits_rot(const bits_t *bits) { + bits_t *result = bits_copy(bits); + bits_rotz(result); + return result; +} + +void bits_shiftz(bits_t *bits, long amount) { + if (amount == 0) return; + unsigned char original_bits[bits->allocated]; + for (size_t i = 0; i < bits->allocated; ++i) { + original_bits[i] = bits->bits[i]; + bits->bits[i] = 0; + } + for (size_t i = 0; i < bits->bitlen; ++i) { + unsigned char new_bit = 0; + if ((amount > 0 && i + amount < bits->bitlen) || + (amount < 0 && i >= -amount)) { + new_bit = (unsigned char)GET_BIT(original_bits, i + amount); + } + bits->bits[i / 8] |= new_bit << (7 - (i % 8)); + } +} + +bits_t *bits_shift(const bits_t *bits, long amount) { + bits_t *result = bits_copy(bits); + bits_shiftz(result, amount); + return result; +} + +void bits_shiftrz(bits_t *bits, long amount) { + if (amount == 0) return; + unsigned char original_bits[bits->allocated]; + for (size_t i = 0; i < bits->allocated; ++i) { + original_bits[i] = bits->bits[i]; + bits->bits[i] = 0; + } + for (size_t i = 0; i < bits->bitlen; ++i) { + unsigned char new_bit = 0; + size_t new_pos = 0; + if ((amount > 0 && i + amount < bits->bitlen) || + (amount < 0 && i >= -amount)) { + new_pos = i + amount; + } else if (amount > 0) { + new_pos = (i + amount) % bits->bitlen; + } else if (amount < 0) { + long mod_amount = amount % bits->bitlen; + new_pos = (i + mod_amount) % bits->bitlen; + } + new_bit = (unsigned char)GET_BIT(original_bits, new_pos); + bits->bits[i / 8] |= new_bit << (7 - (i % 8)); + } +} + +bits_t *bits_shiftr(const bits_t *bits, long amount) { + bits_t *result = bits_copy(bits); + bits_shiftrz(result, amount); + return result; +} + +void bits_shiftiz(bits_t *bits, long amount) { + if (amount > 0) { + bits_lengthenz(bits, -amount); + } else if (amount < 0) { + bits_shortenz(bits, amount); + } +} + +bits_t *bits_shifti(const bits_t *bits, long amount) { + bits_t *result = bits_copy(bits); + bits_shiftiz(result, amount); + return result; +} + +void bits_lengthenz(bits_t *bits, long amount) { + size_t abs_amount; + if (amount > 0) { + abs_amount = (size_t)amount; + } else if (amount < 0) { + abs_amount = (size_t)-amount; + } else { + return; + } + size_t new_alloc = BYTE_LEN(bits->bitlen + abs_amount); + if (new_alloc > bits->allocated) { + bits->bits = try_realloc(bits->bits, new_alloc); + for (size_t i = bits->allocated; i < new_alloc; ++i) { + bits->bits[i] = 0; + } + bits->allocated = new_alloc; + } + bits->bitlen += abs_amount; + + if (amount > 0) { + bits_shiftz(bits, -amount); + } +} + +bits_t *bits_lengthen(const bits_t *bits, long amount) { + bits_t *result = bits_copy(bits); + bits_lengthenz(result, amount); + return result; +} + +void bits_shortenz(bits_t *bits, long amount) { + size_t new_bits; + if (amount > 0) { + new_bits = bits->bitlen - amount; + bits_shiftz(bits, amount); + } else if (amount < 0) { + new_bits = bits->bitlen + amount; + for (size_t i = new_bits; i < bits->bitlen; ++i) { + bits->bits[i / 8] &= ~(1 << (7 - (i % 8))); + } + } else { + return; + } + bits->bitlen = new_bits; +} + +bits_t *bits_shorten(const bits_t *bits, long amount) { + bits_t *result = bits_copy(bits); + bits_shortenz(result, amount); + return result; +} + +void bits_sha1(const bits_t *bits, unsigned char hashout[20]) { + SHA_CTX ctx = {0}; + SHA1_Init(&ctx); + SHA1_Update(&ctx, bits->bits, (int)BYTE_LEN(bits->bitlen)); + SHA1_Final(hashout, &ctx); +} + +bool bits_eq(const bits_t *one, const bits_t *other) { + 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; + if (one->bitlen % 8 != 0) { + size_t mask_len = one->bitlen % 8; + unsigned char mask = 0; + for (size_t i = 7; i >= 0; --i) { + mask |= 1 << i; + if (--mask_len == 0) break; + } + size_t last_byte = (one->bitlen / 8); + unsigned char one_masked = one->bits[last_byte] & mask; + unsigned char other_masked = other->bits[last_byte] & mask; + return one_masked == other_masked; + } + return true; +} diff --git a/src/util/bits.h b/src/util/bits.h new file mode 100644 index 0000000..3ea0dd2 --- /dev/null +++ b/src/util/bits.h @@ -0,0 +1,96 @@ +/* + * ecgen, tool for generating Elliptic curve domain parameters + * Copyright (C) 2017 J08nY + */ + +#ifndef ECGEN_BITS_H +#define ECGEN_BITS_H + +#include "misc/types.h" + +#define BYTE_LEN(bit_len) \ + (((bit_len) % 8 == 0) ? (bit_len) / 8 : ((bit_len) / 8) + 1) + +#define GET_BIT(bit_array, bit_pos) \ + (((bit_array)[(bit_pos) / 8] & (1 << (7 - ((bit_pos) % 8)))) >> \ + (7 - ((bit_pos) % 8))) + +#define SET_BIT(bit_array, bit_pos, bit_value) \ + do { \ + unsigned char val = 1 << (7 - ((bit_pos) % 8)); \ + if ((bit_value) == 1) { \ + (bit_array)[(bit_pos) / 8] |= val; \ + } else { \ + (bit_array)[(bit_pos) / 8] &= ~val; \ + } \ + } while (0); + +bits_t *bits_new(size_t bit_len); + +bits_t *bits_copy(const bits_t *bits); + +void bits_free(bits_t **bits); + +bits_t *bits_from_i(GEN i); + +bits_t *bits_from_hex(const char *hex_str); + +bits_t *bits_from_bin(const char *bin_str); + +bits_t *bits_from_raw(const unsigned char *bits, size_t bit_len); + +bits_t *bits_from_bitvec(GEN v); + +GEN bits_to_i(const bits_t *bits); + +char *bits_to_hex(const bits_t *bits); + +char *bits_to_bin(const bits_t *bits); + +unsigned char *bits_to_raw(const bits_t *bits); + +size_t bits_to_rawlen(const bits_t *bits); + +GEN bits_to_bitvec(const bits_t *bits); + +void bits_concatz(bits_t *one, ...); + +bits_t *bits_concat(const bits_t *one, ...); + +bits_t *bits_or(const bits_t *one, const bits_t *other); + +bits_t *bits_and(const bits_t *one, const bits_t *other); + +void bits_notz(bits_t *bits); + +bits_t *bits_not(const bits_t *bits); + +void bits_rotz(bits_t *bits); + +bits_t *bits_rot(const bits_t *bits); + +void bits_shiftz(bits_t *bits, long amount); + +bits_t *bits_shift(const bits_t *bits, long amount); + +void bits_shiftrz(bits_t *bits, long amount); + +bits_t *bits_shiftr(const bits_t *bits, long amount); + +void bits_shiftiz(bits_t *bits, long amount); + +bits_t *bits_shifti(const bits_t *bits, long amount); + +void bits_lengthenz(bits_t *bits, long amount); + +bits_t *bits_lengthen(const bits_t *bits, long amount); + +void bits_shortenz(bits_t *bits, long amount); + +bits_t *bits_shorten(const bits_t *bits, long amount); + +void bits_sha1(const bits_t *bits, unsigned char hashout[20]); + +bool bits_eq(const bits_t *one, const bits_t *other); + +#endif // ECGEN_BITS_H diff --git a/src/util/memory.c b/src/util/memory.c index 53f68c9..6051459 100644 --- a/src/util/memory.c +++ b/src/util/memory.c @@ -5,7 +5,6 @@ #include "memory.h" #include <pari/pari.h> - static void *(*malloc_func)(size_t) = pari_malloc; static void *(*calloc_func)(size_t) = pari_calloc; @@ -25,9 +24,7 @@ void *alloc(void *(*fun)(size_t), size_t size) { void *try_malloc(size_t size) { return alloc(malloc_func, size); } -void *try_calloc(size_t size) { - return alloc(calloc_func, size); -} +void *try_calloc(size_t size) { return alloc(calloc_func, size); } void *try_realloc(void *ptr, size_t size) { void *result = realloc_func(ptr, size); @@ -38,13 +35,22 @@ void *try_realloc(void *ptr, size_t size) { return result; } -void try_free(void *ptr) { - free_func(ptr); +char *try_strdup(const char *str) { + size_t len = strlen(str); + return try_memdup(str, len + 1); +} + +void *try_memdup(const void *mem, size_t len) { + void *result = try_malloc(len); + memcpy(result, mem, len); + return result; } +void try_free(void *ptr) { free_func(ptr); } + void set_mem_funcs(void *(*malloc_fun)(size_t), void *(*calloc_fun)(size_t), - void *(*realloc_fun)(void *, size_t), - void(*free_fun)(void *)) { + void *(*realloc_fun)(void *, size_t), + void (*free_fun)(void *)) { malloc_func = malloc_fun; calloc_func = calloc_fun; realloc_func = realloc_fun; diff --git a/src/util/memory.h b/src/util/memory.h index 7070430..29b2df9 100644 --- a/src/util/memory.h +++ b/src/util/memory.h @@ -34,6 +34,21 @@ void *try_realloc(void *ptr, size_t size); /** * @brief + * @param str + * @return + */ +char *try_strdup(const char *str); + +/** + * @brief + * @param mem + * @param len + * @return + */ +void *try_memdup(const void *mem, size_t len); + +/** + * @brief * @param ptr */ void try_free(void *ptr); @@ -46,7 +61,7 @@ void try_free(void *ptr); * @param free_fun */ void set_mem_funcs(void *(*malloc_fun)(size_t), void *(*calloc_fun)(size_t), - void *(*realloc_fun)(void *, size_t), - void(*free_fun)(void *)); + void *(*realloc_fun)(void *, size_t), + void (*free_fun)(void *)); #endif // ECGEN_MEMORY_H diff --git a/src/util/random.c b/src/util/random.c index bd7b89b..9af43cc 100644 --- a/src/util/random.c +++ b/src/util/random.c @@ -43,9 +43,7 @@ bool random_init(void) { GEN random_prime(unsigned long bits) { pari_sp ltop = avma; - GEN range = gtovec0(gen_0, 2); - gel(range, 1) = powis(gen_2, bits - 1); - gel(range, 2) = powis(gen_2, bits); + GEN range = mkvec2(int2n(bits - 1), int2n(bits)); GEN p; pari_sp btop = avma; @@ -60,9 +58,6 @@ GEN random_prime(unsigned long bits) { GEN random_int(unsigned long bits) { pari_sp ltop = avma; - GEN range = gtovec0(gen_0, 2); - gel(range, 1) = powis(gen_2, bits - 1); - gel(range, 2) = powis(gen_2, bits); - + GEN range = mkvec2(int2n(bits - 1), int2n(bits)); return gerepilecopy(ltop, genrand(range)); } |