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/>.
18 SPDX-License-Identifier: AGPL3.0-or-later
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 {
68 * Maximum absolute value the calculation supports.
73 * How much memory should we use (relates to the number of entries in the map).
78 * Map mapping points (here "interpreted" as EdDSA public keys) to
79 * a "void * = long" which corresponds to the numeric value of the
80 * point. As NULL is used to represent "unknown", the actual value
81 * represented by the entry in the map is the "long" minus @e max.
83 struct GNUNET_CONTAINER_MultiPeerMap *map;
86 * 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);
183 for (i = 0; i <= mem; i++)
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);
196 for (i = 1; i < mem; i++)
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);
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)));
295 gcry_mpi_randomize(r,
299 while (gcry_mpi_cmp(r, n) >= 0);
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);
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 * Multiply the point @a p on the elliptic curve by @a val.
412 * @param edc calculation context for ECC operations
413 * @param p point to multiply
414 * @param val (positive) value to encode into a point
415 * @return representation of the value as an ECC point,
416 * must be freed using #GNUNET_CRYPTO_ecc_free()
419 GNUNET_CRYPTO_ecc_pmul_mpi(struct GNUNET_CRYPTO_EccDlogContext *edc,
425 r = gcry_mpi_point_new(0);
426 gcry_mpi_ec_mul(r, val, p, edc->ctx);
432 * Obtain a random point on the curve and its
433 * additive inverse. Both returned values
434 * must be freed using #GNUNET_CRYPTO_ecc_free().
436 * @param edc calculation context for ECC operations
437 * @param[out] r set to a random point on the curve
438 * @param[out] r_inv set to the additive inverse of @a r
441 GNUNET_CRYPTO_ecc_rnd(struct GNUNET_CRYPTO_EccDlogContext *edc,
443 gcry_mpi_point_t *r_inv)
449 fact = GNUNET_CRYPTO_ecc_random_mod_n(edc);
452 g = gcry_mpi_ec_get_point("g", edc->ctx, 0);
453 GNUNET_assert(NULL != g);
454 *r = gcry_mpi_point_new(0);
455 gcry_mpi_ec_mul(*r, fact, g, edc->ctx);
457 /* calculate 'r_inv' */
458 n = gcry_mpi_ec_get_mpi("n", edc->ctx, 1);
459 gcry_mpi_sub(fact, n, fact); /* fact = n - fact = - fact */
460 *r_inv = gcry_mpi_point_new(0);
461 gcry_mpi_ec_mul(*r_inv, fact, g, edc->ctx);
464 gcry_mpi_release(fact);
465 gcry_mpi_point_release(g);
470 * Obtain a random scalar for point multiplication on the curve and
471 * its multiplicative inverse.
473 * @param edc calculation context for ECC operations
474 * @param[out] r set to a random scalar on the curve
475 * @param[out] r_inv set to the multiplicative inverse of @a r
478 GNUNET_CRYPTO_ecc_rnd_mpi(struct GNUNET_CRYPTO_EccDlogContext *edc,
484 *r = GNUNET_CRYPTO_ecc_random_mod_n(edc);
485 /* r_inv = n - r = - r */
486 *r_inv = gcry_mpi_new(0);
487 n = gcry_mpi_ec_get_mpi("n", edc->ctx, 1);
488 gcry_mpi_sub(*r_inv, n, *r);
493 * Free a point value returned by the API.
495 * @param p point to free
498 GNUNET_CRYPTO_ecc_free(gcry_mpi_point_t p)
500 gcry_mpi_point_release(p);
504 /* end of crypto_ecc_dlog.c */