X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=src%2Futil%2Fcrypto_ecc_dlog.c;h=f6eb58a9ac4ddcdd729c101820f2fc01260732a9;hb=4707789ebfb4cef9672db31e3ceb8f98381901d0;hp=34f3c203d223079c77e228075967d0fe3dbe2e98;hpb=fece22eebf8c8d54e79d05f748019e7234823828;p=oweals%2Fgnunet.git diff --git a/src/util/crypto_ecc_dlog.c b/src/util/crypto_ecc_dlog.c index 34f3c203d..f6eb58a9a 100644 --- a/src/util/crypto_ecc_dlog.c +++ b/src/util/crypto_ecc_dlog.c @@ -1,6 +1,6 @@ /* This file is part of GNUnet. - Copyright (C) 2012, 2013, 2015 Christian Grothoff (and other contributing authors) + Copyright (C) 2012, 2013, 2015 GNUnet e.V. GNUnet is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published @@ -20,11 +20,10 @@ /** * @file util/crypto_ecc_dlog.c - * @brief ECC discreate logarithm for small values + * @brief ECC addition and discreate logarithm for small values. + * Allows us to use ECC for computations as long as the + * result is relativey small. * @author Christian Grothoff - * - * TODO: - * - support negative factors */ #include "platform.h" #include @@ -46,11 +45,11 @@ */ static void extract_pk (gcry_mpi_point_t pt, - gcry_ctx_t ctx, - struct GNUNET_PeerIdentity *pid) + gcry_ctx_t ctx, + struct GNUNET_PeerIdentity *pid) { gcry_mpi_t q_y; - + GNUNET_assert (0 == gcry_mpi_ec_set_point ("q", pt, ctx)); q_y = gcry_mpi_ec_get_mpi ("q@eddsa", ctx, 0); GNUNET_assert (q_y); @@ -64,19 +63,92 @@ extract_pk (gcry_mpi_point_t pt, /** * Internal structure used to cache pre-calculated values for DLOG calculation. */ -struct GNUNET_CRYPTO_EccDlogContext +struct GNUNET_CRYPTO_EccDlogContext { + /** + * Maximum absolute value the calculation supports. + */ unsigned int max; + + /** + * How much memory should we use (relates to the number of entries in the map). + */ unsigned int mem; + + /** + * Map mapping points (here "interpreted" as EdDSA public keys) to + * a "void * = long" which corresponds to the numeric value of the + * point. As NULL is used to represent "unknown", the actual value + * represented by the entry in the map is the "long" minus @e max. + */ struct GNUNET_CONTAINER_MultiPeerMap *map; + + /** + * Context to use for operations on the elliptic curve. + */ gcry_ctx_t ctx; }; +/** + * Convert point value to binary representation. + * + * @param edc calculation context for ECC operations + * @param point computational point representation + * @param[out] bin binary point representation + */ +void +GNUNET_CRYPTO_ecc_point_to_bin (struct GNUNET_CRYPTO_EccDlogContext *edc, + gcry_mpi_point_t point, + struct GNUNET_CRYPTO_EccPoint *bin) +{ + gcry_mpi_t q_y; + + GNUNET_assert (0 == gcry_mpi_ec_set_point ("q", point, edc->ctx)); + q_y = gcry_mpi_ec_get_mpi ("q@eddsa", edc->ctx, 0); + GNUNET_assert (q_y); + GNUNET_CRYPTO_mpi_print_unsigned (bin->q_y, + sizeof (bin->q_y), + q_y); + gcry_mpi_release (q_y); +} + + +/** + * Convert binary representation of a point to computational representation. + * + * @param edc calculation context for ECC operations + * @param bin binary point representation + * @return computational representation + */ +gcry_mpi_point_t +GNUNET_CRYPTO_ecc_bin_to_point (struct GNUNET_CRYPTO_EccDlogContext *edc, + const struct GNUNET_CRYPTO_EccPoint *bin) +{ + gcry_sexp_t pub_sexpr; + gcry_ctx_t ctx; + gcry_mpi_point_t q; + + if (0 != gcry_sexp_build (&pub_sexpr, NULL, + "(public-key(ecc(curve " CURVE ")(q %b)))", + (int) sizeof (bin->q_y), + bin->q_y)) + { + GNUNET_break (0); + return NULL; + } + GNUNET_assert (0 == gcry_mpi_ec_new (&ctx, pub_sexpr, NULL)); + gcry_sexp_release (pub_sexpr); + q = gcry_mpi_ec_get_point ("q", ctx, 0); + gcry_ctx_release (ctx); + return q; +} + + /** * Do pre-calculation for ECC discrete logarithm for small factors. - * + * * @param max maximum value the factor can be * @param mem memory to use (should be smaller than @a max), must not be zero. * @return @a max if dlog failed, otherwise the factor @@ -91,8 +163,10 @@ GNUNET_CRYPTO_ecc_dlog_prepare (unsigned int max, struct GNUNET_PeerIdentity key; gcry_mpi_point_t gKi; gcry_mpi_t fact; + gcry_mpi_t n; unsigned int i; + GNUNET_assert (max < INT32_MAX); edc = GNUNET_new (struct GNUNET_CRYPTO_EccDlogContext); edc->max = max; edc->mem = mem; @@ -100,8 +174,8 @@ GNUNET_CRYPTO_ecc_dlog_prepare (unsigned int max, edc->map = GNUNET_CONTAINER_multipeermap_create (mem * 2, GNUNET_NO); - GNUNET_assert (0 == gcry_mpi_ec_new (&edc->ctx, - NULL, + GNUNET_assert (0 == gcry_mpi_ec_new (&edc->ctx, + NULL, CURVE)); g = gcry_mpi_ec_get_point ("g", edc->ctx, 0); GNUNET_assert (NULL != g); @@ -115,10 +189,25 @@ GNUNET_CRYPTO_ecc_dlog_prepare (unsigned int max, GNUNET_assert (GNUNET_OK == GNUNET_CONTAINER_multipeermap_put (edc->map, &key, - (void*) (long) i + 1, + (void*) (long) i + max, + GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); + } + /* negative values */ + n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1); + for (i=1;ictx); + extract_pk (gKi, edc->ctx, &key); + GNUNET_assert (GNUNET_OK == + GNUNET_CONTAINER_multipeermap_put (edc->map, + &key, + (void*) (long) max - i, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); } gcry_mpi_release (fact); + gcry_mpi_release (n); gcry_mpi_point_release (gKi); gcry_mpi_point_release (g); return edc; @@ -127,12 +216,12 @@ GNUNET_CRYPTO_ecc_dlog_prepare (unsigned int max, /** * Calculate ECC discrete logarithm for small factors. - * + * * @param edc precalculated values, determine range of factors * @param input point on the curve to factor * @return `edc->max` if dlog failed, otherwise the factor */ -unsigned int +int GNUNET_CRYPTO_ecc_dlog (struct GNUNET_CRYPTO_EccDlogContext *edc, gcry_mpi_point_t input) { @@ -141,13 +230,13 @@ GNUNET_CRYPTO_ecc_dlog (struct GNUNET_CRYPTO_EccDlogContext *edc, struct GNUNET_PeerIdentity key; gcry_mpi_point_t q; unsigned int i; - unsigned int res; + int res; void *retp; g = gcry_mpi_ec_get_point ("g", edc->ctx, 0); GNUNET_assert (NULL != g); q = gcry_mpi_point_new (0); - + res = edc->max; for (i=0;i<=edc->max/edc->mem;i++) { @@ -159,10 +248,10 @@ GNUNET_CRYPTO_ecc_dlog (struct GNUNET_CRYPTO_EccDlogContext *edc, &key); if (NULL != retp) { - res = (((long) retp) - 1) * K - i; - fprintf (stderr, - "Got DLOG %u\n", - res); + res = (((long) retp) - edc->max) * K - i; + /* we continue the loop here to make the implementation + "constant-time". If we do not care about this, we could just + 'break' here and do fewer operations... */ } if (i == edc->max/edc->mem) break; @@ -170,7 +259,7 @@ GNUNET_CRYPTO_ecc_dlog (struct GNUNET_CRYPTO_EccDlogContext *edc, if (0 == i) gcry_mpi_ec_add (q, input, g, edc->ctx); else - gcry_mpi_ec_add (q, q, g, edc->ctx); + gcry_mpi_ec_add (q, q, g, edc->ctx); } gcry_mpi_point_release (g); gcry_mpi_point_release (q); @@ -179,6 +268,40 @@ GNUNET_CRYPTO_ecc_dlog (struct GNUNET_CRYPTO_EccDlogContext *edc, } +/** + * Generate a random value mod n. + * + * @param edc ECC context + * @return random value mod n. + */ +gcry_mpi_t +GNUNET_CRYPTO_ecc_random_mod_n (struct GNUNET_CRYPTO_EccDlogContext *edc) +{ + gcry_mpi_t n; + unsigned int highbit; + gcry_mpi_t r; + + n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1); + + /* check public key for number of bits, bail out if key is all zeros */ + highbit = 256; /* Curve25519 */ + while ( (! gcry_mpi_test_bit (n, highbit)) && + (0 != highbit) ) + highbit--; + GNUNET_assert (0 != highbit); + /* generate fact < n (without bias) */ + GNUNET_assert (NULL != (r = gcry_mpi_new (0))); + do { + gcry_mpi_randomize (r, + highbit + 1, + GCRY_STRONG_RANDOM); + } + while (gcry_mpi_cmp (r, n) >= 0); + gcry_mpi_release (n); + return r; +} + + /** * Release precalculated values. * @@ -191,6 +314,191 @@ GNUNET_CRYPTO_ecc_dlog_release (struct GNUNET_CRYPTO_EccDlogContext *edc) GNUNET_CONTAINER_multipeermap_destroy (edc->map); GNUNET_free (edc); } - -/* end of crypto_ecc_dlog.c */ + +/** + * Multiply the generator g of the elliptic curve by @a val + * to obtain the point on the curve representing @a val. + * Afterwards, point addition will correspond to integer + * addition. #GNUNET_CRYPTO_ecc_dlog() can be used to + * convert a point back to an integer (as long as the + * integer is smaller than the MAX of the @a edc context). + * + * @param edc calculation context for ECC operations + * @param val value to encode into a point + * @return representation of the value as an ECC point, + * must be freed using #GNUNET_CRYPTO_ecc_free() + */ +gcry_mpi_point_t +GNUNET_CRYPTO_ecc_dexp (struct GNUNET_CRYPTO_EccDlogContext *edc, + int val) +{ + gcry_mpi_t fact; + gcry_mpi_t n; + gcry_mpi_point_t g; + gcry_mpi_point_t r; + + g = gcry_mpi_ec_get_point ("g", edc->ctx, 0); + GNUNET_assert (NULL != g); + fact = gcry_mpi_new (0); + if (val < 0) + { + n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1); + gcry_mpi_set_ui (fact, - val); + gcry_mpi_sub (fact, n, fact); + gcry_mpi_release (n); + } + else + { + gcry_mpi_set_ui (fact, val); + } + r = gcry_mpi_point_new (0); + gcry_mpi_ec_mul (r, fact, g, edc->ctx); + gcry_mpi_release (fact); + gcry_mpi_point_release (g); + return r; +} + + +/** + * Multiply the generator g of the elliptic curve by @a val + * to obtain the point on the curve representing @a val. + * + * @param edc calculation context for ECC operations + * @param val (positive) value to encode into a point + * @return representation of the value as an ECC point, + * must be freed using #GNUNET_CRYPTO_ecc_free() + */ +gcry_mpi_point_t +GNUNET_CRYPTO_ecc_dexp_mpi (struct GNUNET_CRYPTO_EccDlogContext *edc, + gcry_mpi_t val) +{ + gcry_mpi_point_t g; + gcry_mpi_point_t r; + + g = gcry_mpi_ec_get_point ("g", edc->ctx, 0); + GNUNET_assert (NULL != g); + r = gcry_mpi_point_new (0); + gcry_mpi_ec_mul (r, val, g, edc->ctx); + gcry_mpi_point_release (g); + return r; +} + + +/** + * Add two points on the elliptic curve. + * + * @param edc calculation context for ECC operations + * @param a some value + * @param b some value + * @return @a a + @a b, must be freed using #GNUNET_CRYPTO_ecc_free() + */ +gcry_mpi_point_t +GNUNET_CRYPTO_ecc_add (struct GNUNET_CRYPTO_EccDlogContext *edc, + gcry_mpi_point_t a, + gcry_mpi_point_t b) +{ + gcry_mpi_point_t r; + + r = gcry_mpi_point_new (0); + gcry_mpi_ec_add (r, a, b, edc->ctx); + return r; +} + + +/** + * Multiply the point @a p on the elliptic curve by @a val. + * + * @param edc calculation context for ECC operations + * @param p point to multiply + * @param val (positive) value to encode into a point + * @return representation of the value as an ECC point, + * must be freed using #GNUNET_CRYPTO_ecc_free() + */ +gcry_mpi_point_t +GNUNET_CRYPTO_ecc_pmul_mpi (struct GNUNET_CRYPTO_EccDlogContext *edc, + gcry_mpi_point_t p, + gcry_mpi_t val) +{ + gcry_mpi_point_t r; + + r = gcry_mpi_point_new (0); + gcry_mpi_ec_mul (r, val, p, edc->ctx); + return r; +} + + +/** + * Obtain a random point on the curve and its + * additive inverse. Both returned values + * must be freed using #GNUNET_CRYPTO_ecc_free(). + * + * @param edc calculation context for ECC operations + * @param[out] r set to a random point on the curve + * @param[out] r_inv set to the additive inverse of @a r + */ +void +GNUNET_CRYPTO_ecc_rnd (struct GNUNET_CRYPTO_EccDlogContext *edc, + gcry_mpi_point_t *r, + gcry_mpi_point_t *r_inv) +{ + gcry_mpi_t fact; + gcry_mpi_t n; + gcry_mpi_point_t g; + + fact = GNUNET_CRYPTO_ecc_random_mod_n (edc); + + /* calculate 'r' */ + g = gcry_mpi_ec_get_point ("g", edc->ctx, 0); + GNUNET_assert (NULL != g); + *r = gcry_mpi_point_new (0); + gcry_mpi_ec_mul (*r, fact, g, edc->ctx); + + /* calculate 'r_inv' */ + n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1); + gcry_mpi_sub (fact, n, fact); /* fact = n - fact = - fact */ + *r_inv = gcry_mpi_point_new (0); + gcry_mpi_ec_mul (*r_inv, fact, g, edc->ctx); + + gcry_mpi_release (n); + gcry_mpi_release (fact); + gcry_mpi_point_release (g); +} + + +/** + * Obtain a random scalar for point multiplication on the curve and + * its multiplicative inverse. + * + * @param edc calculation context for ECC operations + * @param[out] r set to a random scalar on the curve + * @param[out] r_inv set to the multiplicative inverse of @a r + */ +void +GNUNET_CRYPTO_ecc_rnd_mpi (struct GNUNET_CRYPTO_EccDlogContext *edc, + gcry_mpi_t *r, + gcry_mpi_t *r_inv) +{ + gcry_mpi_t n; + + *r = GNUNET_CRYPTO_ecc_random_mod_n (edc); + /* r_inv = n - r = - r */ + *r_inv = gcry_mpi_new (0); + n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1); + gcry_mpi_sub (*r_inv, n, *r); +} + + +/** + * Free a point value returned by the API. + * + * @param p point to free + */ +void +GNUNET_CRYPTO_ecc_free (gcry_mpi_point_t p) +{ + gcry_mpi_point_release (p); +} + + +/* end of crypto_ecc_dlog.c */