2 This file is part of GNUnet.
3 Copyright (C) 2012, 2013, 2015 Christian Grothoff (and other contributing authors)
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 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 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
22 * @file util/crypto_ecc_dlog.c
23 * @brief ECC addition and discreate logarithm for small values.
24 * Allows us to use ECC for computations as long as the
25 * result is relativey small.
26 * @author Christian Grothoff
30 #include "gnunet_crypto_lib.h"
31 #include "gnunet_container_lib.h"
35 * Name of the curve we are using. Note that we have hard-coded
36 * structs that use 256 bits, so using a bigger curve will require
37 * changes that break stuff badly. The name of the curve given here
38 * must be agreed by all peers and be supported by libgcrypt.
40 #define CURVE "Ed25519"
47 extract_pk (gcry_mpi_point_t pt,
49 struct GNUNET_PeerIdentity *pid)
53 GNUNET_assert (0 == gcry_mpi_ec_set_point ("q", pt, ctx));
54 q_y = gcry_mpi_ec_get_mpi ("q@eddsa", ctx, 0);
56 GNUNET_CRYPTO_mpi_print_unsigned (pid->public_key.q_y,
57 sizeof (pid->public_key.q_y),
59 gcry_mpi_release (q_y);
64 * Internal structure used to cache pre-calculated values for DLOG calculation.
66 struct GNUNET_CRYPTO_EccDlogContext
69 * Maximum absolute value the calculation supports.
74 * How much memory should we use (relates to the number of entries in the map).
79 * Map mapping points (here "interpreted" as EdDSA public keys) to
80 * a "void * = long" which corresponds to the numeric value of the
81 * point. As NULL is used to represent "unknown", the actual value
82 * represented by the entry in the map is the "long" minus @e max.
84 struct GNUNET_CONTAINER_MultiPeerMap *map;
87 * Context to use for operations on the elliptic curve.
95 * Convert point value to binary representation.
97 * @param edc calculation context for ECC operations
98 * @param point computational point representation
99 * @param[out] bin binary point representation
102 GNUNET_CRYPTO_ecc_point_to_bin (struct GNUNET_CRYPTO_EccDlogContext *edc,
103 gcry_mpi_point_t point,
104 struct GNUNET_CRYPTO_EccPoint *bin)
108 GNUNET_assert (0 == gcry_mpi_ec_set_point ("q", point, edc->ctx));
109 q_y = gcry_mpi_ec_get_mpi ("q@eddsa", edc->ctx, 0);
111 GNUNET_CRYPTO_mpi_print_unsigned (bin->q_y,
114 gcry_mpi_release (q_y);
119 * Convert binary representation of a point to computational representation.
121 * @param edc calculation context for ECC operations
122 * @param bin binary point representation
123 * @return computational representation
126 GNUNET_CRYPTO_ecc_bin_to_point (struct GNUNET_CRYPTO_EccDlogContext *edc,
127 const struct GNUNET_CRYPTO_EccPoint *bin)
129 gcry_sexp_t pub_sexpr;
133 if (0 != gcry_sexp_build (&pub_sexpr, NULL,
134 "(public-key(ecc(curve " CURVE ")(q %b)))",
135 (int) sizeof (bin->q_y),
141 GNUNET_assert (0 == gcry_mpi_ec_new (&ctx, pub_sexpr, NULL));
142 gcry_sexp_release (pub_sexpr);
143 q = gcry_mpi_ec_get_point ("q", ctx, 0);
144 gcry_ctx_release (ctx);
150 * Do pre-calculation for ECC discrete logarithm for small factors.
152 * @param max maximum value the factor can be
153 * @param mem memory to use (should be smaller than @a max), must not be zero.
154 * @return @a max if dlog failed, otherwise the factor
156 struct GNUNET_CRYPTO_EccDlogContext *
157 GNUNET_CRYPTO_ecc_dlog_prepare (unsigned int max,
160 struct GNUNET_CRYPTO_EccDlogContext *edc;
161 unsigned int K = ((max + (mem-1)) / mem);
163 struct GNUNET_PeerIdentity key;
164 gcry_mpi_point_t gKi;
169 GNUNET_assert (max < INT32_MAX);
170 edc = GNUNET_new (struct GNUNET_CRYPTO_EccDlogContext);
174 edc->map = GNUNET_CONTAINER_multipeermap_create (mem * 2,
177 GNUNET_assert (0 == gcry_mpi_ec_new (&edc->ctx,
180 g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
181 GNUNET_assert (NULL != g);
182 fact = gcry_mpi_new (0);
183 gKi = gcry_mpi_point_new (0);
186 gcry_mpi_set_ui (fact, i * K);
187 gcry_mpi_ec_mul (gKi, fact, g, edc->ctx);
188 extract_pk (gKi, edc->ctx, &key);
189 GNUNET_assert (GNUNET_OK ==
190 GNUNET_CONTAINER_multipeermap_put (edc->map,
192 (void*) (long) i + max,
193 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
195 /* negative values */
196 n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
199 gcry_mpi_set_ui (fact, i * K);
200 gcry_mpi_sub (fact, n, fact);
201 gcry_mpi_ec_mul (gKi, fact, g, edc->ctx);
202 extract_pk (gKi, edc->ctx, &key);
203 GNUNET_assert (GNUNET_OK ==
204 GNUNET_CONTAINER_multipeermap_put (edc->map,
206 (void*) (long) max - i,
207 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
209 gcry_mpi_release (fact);
210 gcry_mpi_release (n);
211 gcry_mpi_point_release (gKi);
212 gcry_mpi_point_release (g);
218 * Calculate ECC discrete logarithm for small factors.
220 * @param edc precalculated values, determine range of factors
221 * @param input point on the curve to factor
222 * @return `edc->max` if dlog failed, otherwise the factor
225 GNUNET_CRYPTO_ecc_dlog (struct GNUNET_CRYPTO_EccDlogContext *edc,
226 gcry_mpi_point_t input)
228 unsigned int K = ((edc->max + (edc->mem-1)) / edc->mem);
230 struct GNUNET_PeerIdentity key;
236 g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
237 GNUNET_assert (NULL != g);
238 q = gcry_mpi_point_new (0);
241 for (i=0;i<=edc->max/edc->mem;i++)
244 extract_pk (input, edc->ctx, &key);
246 extract_pk (q, edc->ctx, &key);
247 retp = GNUNET_CONTAINER_multipeermap_get (edc->map,
251 res = (((long) retp) - edc->max) * K - i;
252 /* we continue the loop here to make the implementation
253 "constant-time". If we do not care about this, we could just
254 'break' here and do fewer operations... */
256 if (i == edc->max/edc->mem)
260 gcry_mpi_ec_add (q, input, g, edc->ctx);
262 gcry_mpi_ec_add (q, q, g, edc->ctx);
264 gcry_mpi_point_release (g);
265 gcry_mpi_point_release (q);
272 * Generate a random value mod n.
274 * @param edc ECC context
275 * @return random value mod n.
278 GNUNET_CRYPTO_ecc_random_mod_n (struct GNUNET_CRYPTO_EccDlogContext *edc)
281 unsigned int highbit;
284 n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
286 /* check public key for number of bits, bail out if key is all zeros */
287 highbit = 256; /* Curve25519 */
288 while ( (! gcry_mpi_test_bit (n, highbit)) &&
291 GNUNET_assert (0 != highbit);
292 /* generate fact < n (without bias) */
293 GNUNET_assert (NULL != (r = gcry_mpi_new (0)));
295 gcry_mpi_randomize (r,
299 while (gcry_mpi_cmp (r, n) >= 0);
300 gcry_mpi_release (n);
306 * Release precalculated values.
308 * @param edc dlog context
311 GNUNET_CRYPTO_ecc_dlog_release (struct GNUNET_CRYPTO_EccDlogContext *edc)
313 gcry_ctx_release (edc->ctx);
314 GNUNET_CONTAINER_multipeermap_destroy (edc->map);
320 * Multiply the generator g of the elliptic curve by @a val
321 * to obtain the point on the curve representing @a val.
322 * Afterwards, point addition will correspond to integer
323 * addition. #GNUNET_CRYPTO_ecc_dlog() can be used to
324 * convert a point back to an integer (as long as the
325 * integer is smaller than the MAX of the @a edc context).
327 * @param edc calculation context for ECC operations
328 * @param val value to encode into a point
329 * @return representation of the value as an ECC point,
330 * must be freed using #GNUNET_CRYPTO_ecc_free()
333 GNUNET_CRYPTO_ecc_dexp (struct GNUNET_CRYPTO_EccDlogContext *edc,
341 g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
342 GNUNET_assert (NULL != g);
343 fact = gcry_mpi_new (0);
346 n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
347 gcry_mpi_set_ui (fact, - val);
348 gcry_mpi_sub (fact, n, fact);
349 gcry_mpi_release (n);
353 gcry_mpi_set_ui (fact, val);
355 r = gcry_mpi_point_new (0);
356 gcry_mpi_ec_mul (r, fact, g, edc->ctx);
357 gcry_mpi_release (fact);
358 gcry_mpi_point_release (g);
364 * Multiply the generator g of the elliptic curve by @a val
365 * to obtain the point on the curve representing @a val.
367 * @param edc calculation context for ECC operations
368 * @param val (positive) value to encode into a point
369 * @return representation of the value as an ECC point,
370 * must be freed using #GNUNET_CRYPTO_ecc_free()
373 GNUNET_CRYPTO_ecc_dexp_mpi (struct GNUNET_CRYPTO_EccDlogContext *edc,
379 g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
380 GNUNET_assert (NULL != g);
381 r = gcry_mpi_point_new (0);
382 gcry_mpi_ec_mul (r, val, g, edc->ctx);
383 gcry_mpi_point_release (g);
389 * Add two points on the elliptic curve.
391 * @param edc calculation context for ECC operations
392 * @param a some value
393 * @param b some value
394 * @return @a a + @a b, must be freed using #GNUNET_CRYPTO_ecc_free()
397 GNUNET_CRYPTO_ecc_add (struct GNUNET_CRYPTO_EccDlogContext *edc,
403 r = gcry_mpi_point_new (0);
404 gcry_mpi_ec_add (r, a, b, edc->ctx);
410 * Obtain a random point on the curve and its
411 * additive inverse. Both returned values
412 * must be freed using #GNUNET_CRYPTO_ecc_free().
414 * @param edc calculation context for ECC operations
415 * @param[out] r set to a random point on the curve
416 * @param[out] r_inv set to the additive inverse of @a r
419 GNUNET_CRYPTO_ecc_rnd (struct GNUNET_CRYPTO_EccDlogContext *edc,
421 gcry_mpi_point_t *r_inv)
427 fact = GNUNET_CRYPTO_ecc_random_mod_n (edc);
430 g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
431 GNUNET_assert (NULL != g);
432 *r = gcry_mpi_point_new (0);
433 gcry_mpi_ec_mul (*r, fact, g, edc->ctx);
435 /* calculate 'r_inv' */
436 n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
437 gcry_mpi_sub (fact, n, fact); /* fact = n - fact = - fact */
438 *r_inv = gcry_mpi_point_new (0);
439 gcry_mpi_ec_mul (*r_inv, fact, g, edc->ctx);
441 gcry_mpi_release (n);
442 gcry_mpi_release (fact);
443 gcry_mpi_point_release (g);
448 * Free a point value returned by the API.
450 * @param p point to free
453 GNUNET_CRYPTO_ecc_free (gcry_mpi_point_t p)
455 gcry_mpi_point_release (p);
459 /* end of crypto_ecc_dlog.c */