2 This file is part of GNUnet.
3 Copyright (C) 2012, 2013, 2015 GNUnet e.V.
5 GNUnet is free software: you can redistribute it and/or modify it
6 under the terms of the GNU Affero General Public License as published
7 by the Free Software Foundation, either version 3 of the License,
8 or (at your option) any later version.
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Affero General Public License for more details.
15 You should have received a copy of the GNU Affero General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
20 * @file util/crypto_ecc_dlog.c
21 * @brief ECC addition and discreate logarithm for small values.
22 * Allows us to use ECC for computations as long as the
23 * result is relativey small.
24 * @author Christian Grothoff
28 #include "gnunet_crypto_lib.h"
29 #include "gnunet_container_lib.h"
33 * Name of the curve we are using. Note that we have hard-coded
34 * structs that use 256 bits, so using a bigger curve will require
35 * changes that break stuff badly. The name of the curve given here
36 * must be agreed by all peers and be supported by libgcrypt.
38 #define CURVE "Ed25519"
45 extract_pk (gcry_mpi_point_t pt,
47 struct GNUNET_PeerIdentity *pid)
51 GNUNET_assert (0 == gcry_mpi_ec_set_point ("q", pt, ctx));
52 q_y = gcry_mpi_ec_get_mpi ("q@eddsa", ctx, 0);
54 GNUNET_CRYPTO_mpi_print_unsigned (pid->public_key.q_y,
55 sizeof (pid->public_key.q_y),
57 gcry_mpi_release (q_y);
62 * Internal structure used to cache pre-calculated values for DLOG calculation.
64 struct GNUNET_CRYPTO_EccDlogContext
67 * Maximum absolute value the calculation supports.
72 * How much memory should we use (relates to the number of entries in the map).
77 * Map mapping points (here "interpreted" as EdDSA public keys) to
78 * a "void * = long" which corresponds to the numeric value of the
79 * point. As NULL is used to represent "unknown", the actual value
80 * represented by the entry in the map is the "long" minus @e max.
82 struct GNUNET_CONTAINER_MultiPeerMap *map;
85 * Context to use for operations on the elliptic curve.
93 * Convert point value to binary representation.
95 * @param edc calculation context for ECC operations
96 * @param point computational point representation
97 * @param[out] bin binary point representation
100 GNUNET_CRYPTO_ecc_point_to_bin (struct GNUNET_CRYPTO_EccDlogContext *edc,
101 gcry_mpi_point_t point,
102 struct GNUNET_CRYPTO_EccPoint *bin)
106 GNUNET_assert (0 == gcry_mpi_ec_set_point ("q", point, edc->ctx));
107 q_y = gcry_mpi_ec_get_mpi ("q@eddsa", edc->ctx, 0);
109 GNUNET_CRYPTO_mpi_print_unsigned (bin->q_y,
112 gcry_mpi_release (q_y);
117 * Convert binary representation of a point to computational representation.
119 * @param edc calculation context for ECC operations
120 * @param bin binary point representation
121 * @return computational representation
124 GNUNET_CRYPTO_ecc_bin_to_point (struct GNUNET_CRYPTO_EccDlogContext *edc,
125 const struct GNUNET_CRYPTO_EccPoint *bin)
127 gcry_sexp_t pub_sexpr;
132 if (0 != gcry_sexp_build (&pub_sexpr, NULL,
133 "(public-key(ecc(curve " CURVE ")(q %b)))",
134 (int) sizeof (bin->q_y),
140 GNUNET_assert (0 == gcry_mpi_ec_new (&ctx, pub_sexpr, NULL));
141 gcry_sexp_release (pub_sexpr);
142 q = gcry_mpi_ec_get_point ("q", ctx, 0);
143 gcry_ctx_release (ctx);
149 * Do pre-calculation for ECC discrete logarithm for small factors.
151 * @param max maximum value the factor can be
152 * @param mem memory to use (should be smaller than @a max), must not be zero.
153 * @return NULL on error
155 struct GNUNET_CRYPTO_EccDlogContext *
156 GNUNET_CRYPTO_ecc_dlog_prepare (unsigned int max,
159 struct GNUNET_CRYPTO_EccDlogContext *edc;
160 unsigned int K = ((max + (mem-1)) / mem);
162 struct GNUNET_PeerIdentity key;
163 gcry_mpi_point_t gKi;
168 GNUNET_assert (max < INT32_MAX);
169 edc = GNUNET_new (struct GNUNET_CRYPTO_EccDlogContext);
173 edc->map = GNUNET_CONTAINER_multipeermap_create (mem * 2,
176 GNUNET_assert (0 == gcry_mpi_ec_new (&edc->ctx,
179 g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
180 GNUNET_assert (NULL != g);
181 fact = gcry_mpi_new (0);
182 gKi = gcry_mpi_point_new (0);
185 gcry_mpi_set_ui (fact, i * K);
186 gcry_mpi_ec_mul (gKi, fact, g, edc->ctx);
187 extract_pk (gKi, edc->ctx, &key);
188 GNUNET_assert (GNUNET_OK ==
189 GNUNET_CONTAINER_multipeermap_put (edc->map,
191 (void*) (long) i + max,
192 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
194 /* negative values */
195 n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
198 gcry_mpi_set_ui (fact, i * K);
199 gcry_mpi_sub (fact, n, fact);
200 gcry_mpi_ec_mul (gKi, fact, g, edc->ctx);
201 extract_pk (gKi, edc->ctx, &key);
202 GNUNET_assert (GNUNET_OK ==
203 GNUNET_CONTAINER_multipeermap_put (edc->map,
205 (void*) (long) max - i,
206 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
208 gcry_mpi_release (fact);
209 gcry_mpi_release (n);
210 gcry_mpi_point_release (gKi);
211 gcry_mpi_point_release (g);
217 * Calculate ECC discrete logarithm for small factors.
219 * @param edc precalculated values, determine range of factors
220 * @param input point on the curve to factor
221 * @return INT_MAX if dlog failed, otherwise the factor
224 GNUNET_CRYPTO_ecc_dlog (struct GNUNET_CRYPTO_EccDlogContext *edc,
225 gcry_mpi_point_t input)
227 unsigned int K = ((edc->max + (edc->mem-1)) / edc->mem);
229 struct GNUNET_PeerIdentity key;
235 g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
236 GNUNET_assert (NULL != g);
237 q = gcry_mpi_point_new (0);
240 for (i=0;i<=edc->max/edc->mem;i++)
243 extract_pk (input, edc->ctx, &key);
245 extract_pk (q, edc->ctx, &key);
246 retp = GNUNET_CONTAINER_multipeermap_get (edc->map,
250 res = (((long) retp) - edc->max) * K - i;
251 /* we continue the loop here to make the implementation
252 "constant-time". If we do not care about this, we could just
253 'break' here and do fewer operations... */
255 if (i == edc->max/edc->mem)
259 gcry_mpi_ec_add (q, input, g, edc->ctx);
261 gcry_mpi_ec_add (q, q, g, edc->ctx);
263 gcry_mpi_point_release (g);
264 gcry_mpi_point_release (q);
271 * Generate a random value mod n.
273 * @param edc ECC context
274 * @return random value mod n.
277 GNUNET_CRYPTO_ecc_random_mod_n (struct GNUNET_CRYPTO_EccDlogContext *edc)
280 unsigned int highbit;
283 n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
285 /* check public key for number of bits, bail out if key is all zeros */
286 highbit = 256; /* Curve25519 */
287 while ( (! gcry_mpi_test_bit (n, highbit)) &&
290 GNUNET_assert (0 != highbit);
291 /* generate fact < n (without bias) */
292 GNUNET_assert (NULL != (r = gcry_mpi_new (0)));
294 gcry_mpi_randomize (r,
298 while (gcry_mpi_cmp (r, n) >= 0);
299 gcry_mpi_release (n);
305 * Release precalculated values.
307 * @param edc dlog context
310 GNUNET_CRYPTO_ecc_dlog_release (struct GNUNET_CRYPTO_EccDlogContext *edc)
312 gcry_ctx_release (edc->ctx);
313 GNUNET_CONTAINER_multipeermap_destroy (edc->map);
319 * Multiply the generator g of the elliptic curve by @a val
320 * to obtain the point on the curve representing @a val.
321 * Afterwards, point addition will correspond to integer
322 * addition. #GNUNET_CRYPTO_ecc_dlog() can be used to
323 * convert a point back to an integer (as long as the
324 * integer is smaller than the MAX of the @a edc context).
326 * @param edc calculation context for ECC operations
327 * @param val value to encode into a point
328 * @return representation of the value as an ECC point,
329 * must be freed using #GNUNET_CRYPTO_ecc_free()
332 GNUNET_CRYPTO_ecc_dexp (struct GNUNET_CRYPTO_EccDlogContext *edc,
340 g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
341 GNUNET_assert (NULL != g);
342 fact = gcry_mpi_new (0);
345 n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
346 gcry_mpi_set_ui (fact, - val);
347 gcry_mpi_sub (fact, n, fact);
348 gcry_mpi_release (n);
352 gcry_mpi_set_ui (fact, val);
354 r = gcry_mpi_point_new (0);
355 gcry_mpi_ec_mul (r, fact, g, edc->ctx);
356 gcry_mpi_release (fact);
357 gcry_mpi_point_release (g);
363 * Multiply the generator g of the elliptic curve by @a val
364 * to obtain the point on the curve representing @a val.
366 * @param edc calculation context for ECC operations
367 * @param val (positive) value to encode into a point
368 * @return representation of the value as an ECC point,
369 * must be freed using #GNUNET_CRYPTO_ecc_free()
372 GNUNET_CRYPTO_ecc_dexp_mpi (struct GNUNET_CRYPTO_EccDlogContext *edc,
378 g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
379 GNUNET_assert (NULL != g);
380 r = gcry_mpi_point_new (0);
381 gcry_mpi_ec_mul (r, val, g, edc->ctx);
382 gcry_mpi_point_release (g);
388 * Add two points on the elliptic curve.
390 * @param edc calculation context for ECC operations
391 * @param a some value
392 * @param b some value
393 * @return @a a + @a b, must be freed using #GNUNET_CRYPTO_ecc_free()
396 GNUNET_CRYPTO_ecc_add (struct GNUNET_CRYPTO_EccDlogContext *edc,
402 r = gcry_mpi_point_new (0);
403 gcry_mpi_ec_add (r, a, b, edc->ctx);
409 * Multiply the point @a p on the elliptic curve by @a val.
411 * @param edc calculation context for ECC operations
412 * @param p point to multiply
413 * @param val (positive) value to encode into a point
414 * @return representation of the value as an ECC point,
415 * must be freed using #GNUNET_CRYPTO_ecc_free()
418 GNUNET_CRYPTO_ecc_pmul_mpi (struct GNUNET_CRYPTO_EccDlogContext *edc,
424 r = gcry_mpi_point_new (0);
425 gcry_mpi_ec_mul (r, val, p, edc->ctx);
431 * Obtain a random point on the curve and its
432 * additive inverse. Both returned values
433 * must be freed using #GNUNET_CRYPTO_ecc_free().
435 * @param edc calculation context for ECC operations
436 * @param[out] r set to a random point on the curve
437 * @param[out] r_inv set to the additive inverse of @a r
440 GNUNET_CRYPTO_ecc_rnd (struct GNUNET_CRYPTO_EccDlogContext *edc,
442 gcry_mpi_point_t *r_inv)
448 fact = GNUNET_CRYPTO_ecc_random_mod_n (edc);
451 g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
452 GNUNET_assert (NULL != g);
453 *r = gcry_mpi_point_new (0);
454 gcry_mpi_ec_mul (*r, fact, g, edc->ctx);
456 /* calculate 'r_inv' */
457 n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
458 gcry_mpi_sub (fact, n, fact); /* fact = n - fact = - fact */
459 *r_inv = gcry_mpi_point_new (0);
460 gcry_mpi_ec_mul (*r_inv, fact, g, edc->ctx);
462 gcry_mpi_release (n);
463 gcry_mpi_release (fact);
464 gcry_mpi_point_release (g);
469 * Obtain a random scalar for point multiplication on the curve and
470 * its multiplicative inverse.
472 * @param edc calculation context for ECC operations
473 * @param[out] r set to a random scalar on the curve
474 * @param[out] r_inv set to the multiplicative inverse of @a r
477 GNUNET_CRYPTO_ecc_rnd_mpi (struct GNUNET_CRYPTO_EccDlogContext *edc,
483 *r = GNUNET_CRYPTO_ecc_random_mod_n (edc);
484 /* r_inv = n - r = - r */
485 *r_inv = gcry_mpi_new (0);
486 n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
487 gcry_mpi_sub (*r_inv, n, *r);
492 * Free a point value returned by the API.
494 * @param p point to free
497 GNUNET_CRYPTO_ecc_free (gcry_mpi_point_t p)
499 gcry_mpi_point_release (p);
503 /* end of crypto_ecc_dlog.c */