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 * Do pre-calculation for ECC discrete logarithm for small factors.
97 * @param max maximum value the factor can be
98 * @param mem memory to use (should be smaller than @a max), must not be zero.
99 * @return @a max if dlog failed, otherwise the factor
101 struct GNUNET_CRYPTO_EccDlogContext *
102 GNUNET_CRYPTO_ecc_dlog_prepare (unsigned int max,
105 struct GNUNET_CRYPTO_EccDlogContext *edc;
106 unsigned int K = ((max + (mem-1)) / mem);
108 struct GNUNET_PeerIdentity key;
109 gcry_mpi_point_t gKi;
114 GNUNET_assert (max < INT32_MAX);
115 edc = GNUNET_new (struct GNUNET_CRYPTO_EccDlogContext);
119 edc->map = GNUNET_CONTAINER_multipeermap_create (mem * 2,
122 GNUNET_assert (0 == gcry_mpi_ec_new (&edc->ctx,
125 g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
126 GNUNET_assert (NULL != g);
127 fact = gcry_mpi_new (0);
128 gKi = gcry_mpi_point_new (0);
131 gcry_mpi_set_ui (fact, i * K);
132 gcry_mpi_ec_mul (gKi, fact, g, edc->ctx);
133 extract_pk (gKi, edc->ctx, &key);
134 GNUNET_assert (GNUNET_OK ==
135 GNUNET_CONTAINER_multipeermap_put (edc->map,
137 (void*) (long) i + max,
138 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
140 /* negative values */
141 n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
144 gcry_mpi_set_ui (fact, i * K);
145 gcry_mpi_sub (fact, n, fact);
146 gcry_mpi_ec_mul (gKi, fact, g, edc->ctx);
147 extract_pk (gKi, edc->ctx, &key);
148 GNUNET_assert (GNUNET_OK ==
149 GNUNET_CONTAINER_multipeermap_put (edc->map,
151 (void*) (long) max - i,
152 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
154 gcry_mpi_release (fact);
155 gcry_mpi_release (n);
156 gcry_mpi_point_release (gKi);
157 gcry_mpi_point_release (g);
163 * Calculate ECC discrete logarithm for small factors.
165 * @param edc precalculated values, determine range of factors
166 * @param input point on the curve to factor
167 * @return `edc->max` if dlog failed, otherwise the factor
170 GNUNET_CRYPTO_ecc_dlog (struct GNUNET_CRYPTO_EccDlogContext *edc,
171 gcry_mpi_point_t input)
173 unsigned int K = ((edc->max + (edc->mem-1)) / edc->mem);
175 struct GNUNET_PeerIdentity key;
181 g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
182 GNUNET_assert (NULL != g);
183 q = gcry_mpi_point_new (0);
186 for (i=0;i<=edc->max/edc->mem;i++)
189 extract_pk (input, edc->ctx, &key);
191 extract_pk (q, edc->ctx, &key);
192 retp = GNUNET_CONTAINER_multipeermap_get (edc->map,
196 res = (((long) retp) - edc->max) * K - i;
197 /* we continue the loop here to make the implementation
198 "constant-time". If we do not care about this, we could just
199 'break' here and do fewer operations... */
201 if (i == edc->max/edc->mem)
205 gcry_mpi_ec_add (q, input, g, edc->ctx);
207 gcry_mpi_ec_add (q, q, g, edc->ctx);
209 gcry_mpi_point_release (g);
210 gcry_mpi_point_release (q);
217 * Generate a random value mod n.
219 * @param edc ECC context
220 * @return random value mod n.
223 GNUNET_CRYPTO_ecc_random_mod_n (struct GNUNET_CRYPTO_EccDlogContext *edc)
226 unsigned int highbit;
229 n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
231 /* check public key for number of bits, bail out if key is all zeros */
232 highbit = 256; /* Curve25519 */
233 while ( (! gcry_mpi_test_bit (n, highbit)) &&
236 GNUNET_assert (0 != highbit);
237 /* generate fact < n (without bias) */
238 GNUNET_assert (NULL != (r = gcry_mpi_new (0)));
240 gcry_mpi_randomize (r,
244 while (gcry_mpi_cmp (r, n) >= 0);
245 gcry_mpi_release (n);
251 * Release precalculated values.
253 * @param edc dlog context
256 GNUNET_CRYPTO_ecc_dlog_release (struct GNUNET_CRYPTO_EccDlogContext *edc)
258 gcry_ctx_release (edc->ctx);
259 GNUNET_CONTAINER_multipeermap_destroy (edc->map);
265 * Multiply the generator g of the elliptic curve by @a val
266 * to obtain the point on the curve representing @a val.
267 * Afterwards, point addition will correspond to integer
268 * addition. #GNUNET_CRYPTO_ecc_dlog() can be used to
269 * convert a point back to an integer (as long as the
270 * integer is smaller than the MAX of the @a edc context).
272 * @param edc calculation context for ECC operations
273 * @param val value to encode into a point
274 * @return representation of the value as an ECC point,
275 * must be freed using #GNUNET_CRYPTO_ecc_free()
278 GNUNET_CRYPTO_ecc_dexp (struct GNUNET_CRYPTO_EccDlogContext *edc,
286 g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
287 GNUNET_assert (NULL != g);
288 fact = gcry_mpi_new (0);
291 n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
292 gcry_mpi_set_ui (fact, - val);
293 gcry_mpi_sub (fact, n, fact);
294 gcry_mpi_release (n);
298 gcry_mpi_set_ui (fact, val);
300 r = gcry_mpi_point_new (0);
301 gcry_mpi_ec_mul (r, fact, g, edc->ctx);
302 gcry_mpi_release (fact);
303 gcry_mpi_point_release (g);
309 * Multiply the generator g of the elliptic curve by @a val
310 * to obtain the point on the curve representing @a val.
312 * @param edc calculation context for ECC operations
313 * @param val (positive) value to encode into a point
314 * @return representation of the value as an ECC point,
315 * must be freed using #GNUNET_CRYPTO_ecc_free()
318 GNUNET_CRYPTO_ecc_dexp_mpi (struct GNUNET_CRYPTO_EccDlogContext *edc,
324 g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
325 GNUNET_assert (NULL != g);
326 r = gcry_mpi_point_new (0);
327 gcry_mpi_ec_mul (r, val, g, edc->ctx);
328 gcry_mpi_point_release (g);
334 * Add two points on the elliptic curve.
336 * @param edc calculation context for ECC operations
337 * @param a some value
338 * @param b some value
339 * @return @a a + @a b, must be freed using #GNUNET_CRYPTO_ecc_free()
342 GNUNET_CRYPTO_ecc_add (struct GNUNET_CRYPTO_EccDlogContext *edc,
348 r = gcry_mpi_point_new (0);
349 gcry_mpi_ec_add (r, a, b, edc->ctx);
355 * Obtain a random point on the curve and its
356 * additive inverse. Both returned values
357 * must be freed using #GNUNET_CRYPTO_ecc_free().
359 * @param edc calculation context for ECC operations
360 * @param[out] r set to a random point on the curve
361 * @param[out] r_inv set to the additive inverse of @a r
364 GNUNET_CRYPTO_ecc_rnd (struct GNUNET_CRYPTO_EccDlogContext *edc,
366 gcry_mpi_point_t *r_inv)
372 fact = GNUNET_CRYPTO_ecc_random_mod_n (edc);
375 g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
376 GNUNET_assert (NULL != g);
377 *r = gcry_mpi_point_new (0);
378 gcry_mpi_ec_mul (*r, fact, g, edc->ctx);
380 /* calculate 'r_inv' */
381 n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
382 gcry_mpi_sub (fact, n, fact); /* fact = n - fact = - fact */
383 *r_inv = gcry_mpi_point_new (0);
384 gcry_mpi_ec_mul (*r_inv, fact, g, edc->ctx);
386 gcry_mpi_release (n);
387 gcry_mpi_release (fact);
388 gcry_mpi_point_release (g);
393 * Free a point value returned by the API.
395 * @param p point to free
398 GNUNET_CRYPTO_ecc_free (gcry_mpi_point_t p)
400 gcry_mpi_point_release (p);
404 /* end of crypto_ecc_dlog.c */