GNUnet  0.10.x
crypto_ecc_dlog.c
Go to the documentation of this file.
1 /*
2  This file is part of GNUnet.
3  Copyright (C) 2012, 2013, 2015 GNUnet e.V.
4 
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.
9 
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.
14 
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/>.
17 
18  SPDX-License-Identifier: AGPL3.0-or-later
19  */
20 
28 #include "platform.h"
29 #include <gcrypt.h>
30 #include "gnunet_crypto_lib.h"
31 #include "gnunet_container_lib.h"
32 
33 
40 #define CURVE "Ed25519"
41 
42 
46 static void
47 extract_pk(gcry_mpi_point_t pt,
48  gcry_ctx_t ctx,
49  struct GNUNET_PeerIdentity *pid)
50 {
51  gcry_mpi_t q_y;
52 
53  GNUNET_assert(0 == gcry_mpi_ec_set_point("q", pt, ctx));
54  q_y = gcry_mpi_ec_get_mpi("q@eddsa", ctx, 0);
55  GNUNET_assert(q_y);
57  sizeof(pid->public_key.q_y),
58  q_y);
59  gcry_mpi_release(q_y);
60 }
61 
62 
70  unsigned int max;
71 
75  unsigned int mem;
76 
84 
88  gcry_ctx_t ctx;
89 };
90 
91 
99 void
101  gcry_mpi_point_t point,
102  struct GNUNET_CRYPTO_EccPoint *bin)
103 {
104  gcry_mpi_t q_y;
105 
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);
108  GNUNET_assert(q_y);
110  sizeof(bin->q_y),
111  q_y);
112  gcry_mpi_release(q_y);
113 }
114 
115 
123 gcry_mpi_point_t
125  const struct GNUNET_CRYPTO_EccPoint *bin)
126 {
127  gcry_sexp_t pub_sexpr;
128  gcry_ctx_t ctx;
129  gcry_mpi_point_t q;
130 
131  (void)edc;
132  if (0 != gcry_sexp_build(&pub_sexpr, NULL,
133  "(public-key(ecc(curve " CURVE ")(q %b)))",
134  (int)sizeof(bin->q_y),
135  bin->q_y))
136  {
137  GNUNET_break(0);
138  return NULL;
139  }
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);
144  return q;
145 }
146 
147 
157  unsigned int mem)
158 {
160  unsigned int K = ((max + (mem - 1)) / mem);
161  gcry_mpi_point_t g;
162  struct GNUNET_PeerIdentity key;
163  gcry_mpi_point_t gKi;
164  gcry_mpi_t fact;
165  gcry_mpi_t n;
166  unsigned int i;
167 
168  GNUNET_assert(max < INT32_MAX);
170  edc->max = max;
171  edc->mem = mem;
172 
174  GNUNET_NO);
175 
176  GNUNET_assert(0 == gcry_mpi_ec_new(&edc->ctx,
177  NULL,
178  CURVE));
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++)
184  {
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);
190  &key,
191  (void*)(long)i + max,
193  }
194  /* negative values */
195  n = gcry_mpi_ec_get_mpi("n", edc->ctx, 1);
196  for (i = 1; i < mem; i++)
197  {
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);
204  &key,
205  (void*)(long)max - i,
207  }
208  gcry_mpi_release(fact);
209  gcry_mpi_release(n);
210  gcry_mpi_point_release(gKi);
211  gcry_mpi_point_release(g);
212  return edc;
213 }
214 
215 
223 int
225  gcry_mpi_point_t input)
226 {
227  unsigned int K = ((edc->max + (edc->mem - 1)) / edc->mem);
228  gcry_mpi_point_t g;
229  struct GNUNET_PeerIdentity key;
230  gcry_mpi_point_t q;
231  unsigned int i;
232  int res;
233  void *retp;
234 
235  g = gcry_mpi_ec_get_point("g", edc->ctx, 0);
236  GNUNET_assert(NULL != g);
237  q = gcry_mpi_point_new(0);
238 
239  res = INT_MAX;
240  for (i = 0; i <= edc->max / edc->mem; i++)
241  {
242  if (0 == i)
243  extract_pk(input, edc->ctx, &key);
244  else
245  extract_pk(q, edc->ctx, &key);
247  &key);
248  if (NULL != retp)
249  {
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... */
254  }
255  if (i == edc->max / edc->mem)
256  break;
257  /* q = q + g */
258  if (0 == i)
259  gcry_mpi_ec_add(q, input, g, edc->ctx);
260  else
261  gcry_mpi_ec_add(q, q, g, edc->ctx);
262  }
263  gcry_mpi_point_release(g);
264  gcry_mpi_point_release(q);
265 
266  return res;
267 }
268 
269 
276 gcry_mpi_t
278 {
279  gcry_mpi_t n;
280  unsigned int highbit;
281  gcry_mpi_t r;
282 
283  n = gcry_mpi_ec_get_mpi("n", edc->ctx, 1);
284 
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)) &&
288  (0 != highbit))
289  highbit--;
290  GNUNET_assert(0 != highbit);
291  /* generate fact < n (without bias) */
292  GNUNET_assert(NULL != (r = gcry_mpi_new(0)));
293  do
294  {
295  gcry_mpi_randomize(r,
296  highbit + 1,
297  GCRY_STRONG_RANDOM);
298  }
299  while (gcry_mpi_cmp(r, n) >= 0);
300  gcry_mpi_release(n);
301  return r;
302 }
303 
304 
310 void
312 {
313  gcry_ctx_release(edc->ctx);
315  GNUNET_free(edc);
316 }
317 
318 
332 gcry_mpi_point_t
334  int val)
335 {
336  gcry_mpi_t fact;
337  gcry_mpi_t n;
338  gcry_mpi_point_t g;
339  gcry_mpi_point_t r;
340 
341  g = gcry_mpi_ec_get_point("g", edc->ctx, 0);
342  GNUNET_assert(NULL != g);
343  fact = gcry_mpi_new(0);
344  if (val < 0)
345  {
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);
350  }
351  else
352  {
353  gcry_mpi_set_ui(fact, val);
354  }
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);
359  return r;
360 }
361 
362 
372 gcry_mpi_point_t
374  gcry_mpi_t val)
375 {
376  gcry_mpi_point_t g;
377  gcry_mpi_point_t r;
378 
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);
384  return r;
385 }
386 
387 
396 gcry_mpi_point_t
398  gcry_mpi_point_t a,
399  gcry_mpi_point_t b)
400 {
401  gcry_mpi_point_t r;
402 
403  r = gcry_mpi_point_new(0);
404  gcry_mpi_ec_add(r, a, b, edc->ctx);
405  return r;
406 }
407 
408 
418 gcry_mpi_point_t
420  gcry_mpi_point_t p,
421  gcry_mpi_t val)
422 {
423  gcry_mpi_point_t r;
424 
425  r = gcry_mpi_point_new(0);
426  gcry_mpi_ec_mul(r, val, p, edc->ctx);
427  return r;
428 }
429 
430 
440 void
442  gcry_mpi_point_t *r,
443  gcry_mpi_point_t *r_inv)
444 {
445  gcry_mpi_t fact;
446  gcry_mpi_t n;
447  gcry_mpi_point_t g;
448 
449  fact = GNUNET_CRYPTO_ecc_random_mod_n(edc);
450 
451  /* calculate 'r' */
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);
456 
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);
462 
463  gcry_mpi_release(n);
464  gcry_mpi_release(fact);
465  gcry_mpi_point_release(g);
466 }
467 
468 
477 void
479  gcry_mpi_t *r,
480  gcry_mpi_t *r_inv)
481 {
482  gcry_mpi_t n;
483 
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);
489 }
490 
491 
497 void
498 GNUNET_CRYPTO_ecc_free(gcry_mpi_point_t p)
499 {
500  gcry_mpi_point_release(p);
501 }
502 
503 
504 /* end of crypto_ecc_dlog.c */
Point on a curve (always for Curve25519) encoded in a format suitable for network transmission (ECDH)...
gcry_mpi_point_t GNUNET_CRYPTO_ecc_dexp_mpi(struct GNUNET_CRYPTO_EccDlogContext *edc, gcry_mpi_t val)
Multiply the generator g of the elliptic curve by val to obtain the point on the curve representing v...
gcry_mpi_point_t GNUNET_CRYPTO_ecc_bin_to_point(struct GNUNET_CRYPTO_EccDlogContext *edc, const struct GNUNET_CRYPTO_EccPoint *bin)
Convert binary representation of a point to computational representation.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
struct GNUNET_CONTAINER_MultiPeerMap * map
Map mapping points (here "interpreted" as EdDSA public keys) to a "void * = long" which corresponds t...
void GNUNET_CRYPTO_ecc_rnd(struct GNUNET_CRYPTO_EccDlogContext *edc, gcry_mpi_point_t *r, gcry_mpi_point_t *r_inv)
Obtain a random point on the curve and its additive inverse.
static void extract_pk(gcry_mpi_point_t pt, gcry_ctx_t ctx, struct GNUNET_PeerIdentity *pid)
void GNUNET_CRYPTO_mpi_print_unsigned(void *buf, size_t size, gcry_mpi_t val)
Output the given MPI value to the given buffer in network byte order.
Definition: crypto_mpi.c:75
gcry_mpi_point_t GNUNET_CRYPTO_ecc_dexp(struct GNUNET_CRYPTO_EccDlogContext *edc, int val)
Multiply the generator g of the elliptic curve by val to obtain the point on the curve representing v...
#define GNUNET_NO
Definition: gnunet_common.h:78
struct GNUNET_CRYPTO_EccDlogContext * GNUNET_CRYPTO_ecc_dlog_prepare(unsigned int max, unsigned int mem)
Do pre-calculation for ECC discrete logarithm for small factors.
gcry_ctx_t ctx
Context to use for operations on the elliptic curve.
#define GNUNET_OK
Named constants for return values.
Definition: gnunet_common.h:75
gcry_mpi_point_t GNUNET_CRYPTO_ecc_pmul_mpi(struct GNUNET_CRYPTO_EccDlogContext *edc, gcry_mpi_point_t p, gcry_mpi_t val)
Multiply the point p on the elliptic curve by val.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
struct GNUNET_CONTAINER_MultiPeerMap * GNUNET_CONTAINER_multipeermap_create(unsigned int len, int do_not_copy_keys)
Create a multi peer map (hash map for public keys of peers).
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur...
static struct GNUNET_DNSSTUB_Context * ctx
Context for DNS resolution.
void GNUNET_CONTAINER_multipeermap_destroy(struct GNUNET_CONTAINER_MultiPeerMap *map)
Destroy a hash map.
void GNUNET_CRYPTO_ecc_free(gcry_mpi_point_t p)
Free a point value returned by the API.
#define INT_MAX
cryptographic primitives for GNUnet
unsigned char q_y[256/8]
Q consists of an x- and a y-value, each mod p (256 bits), given here in affine coordinates and Ed2551...
static struct GNUNET_CRYPTO_EccDlogContext * edc
Context for DLOG operations on a curve.
static struct GNUNET_OS_Process * p
Helper process we started.
Definition: gnunet-qr.c:59
Internal representation of the hash map.
static int res
static struct GNUNET_REVOCATION_Query * q
Handle for revocation query.
void GNUNET_CRYPTO_ecc_dlog_release(struct GNUNET_CRYPTO_EccDlogContext *edc)
Release precalculated values.
There must only be one value per key; storing a value should fail if a value under the same key alrea...
unsigned char q_y[256/8]
Point Q consists of a y-value mod p (256 bits); the x-value is always positive.
gcry_mpi_point_t GNUNET_CRYPTO_ecc_add(struct GNUNET_CRYPTO_EccDlogContext *edc, gcry_mpi_point_t a, gcry_mpi_point_t b)
Add two points on the elliptic curve.
int GNUNET_CONTAINER_multipeermap_put(struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt)
Store a key-value pair in the map.
void GNUNET_CRYPTO_ecc_rnd_mpi(struct GNUNET_CRYPTO_EccDlogContext *edc, gcry_mpi_t *r, gcry_mpi_t *r_inv)
Obtain a random scalar for point multiplication on the curve and its multiplicative inverse...
The identity of the host (wraps the signing key of the peer).
void * GNUNET_CONTAINER_multipeermap_get(const struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key)
Given a key find a value in the map matching the key.
int GNUNET_CRYPTO_ecc_dlog(struct GNUNET_CRYPTO_EccDlogContext *edc, gcry_mpi_point_t input)
Calculate ECC discrete logarithm for small factors.
Internal structure used to cache pre-calculated values for DLOG calculation.
#define CURVE
Name of the curve we are using.
static struct GNUNET_PeerIdentity pid
Identity of the peer we transmit to / connect to.
void GNUNET_CRYPTO_ecc_point_to_bin(struct GNUNET_CRYPTO_EccDlogContext *edc, gcry_mpi_point_t point, struct GNUNET_CRYPTO_EccPoint *bin)
Convert point value to binary representation.
unsigned int max
Maximum absolute value the calculation supports.
#define GNUNET_free(ptr)
Wrapper around free.
gcry_mpi_t GNUNET_CRYPTO_ecc_random_mod_n(struct GNUNET_CRYPTO_EccDlogContext *edc)
Generate a random value mod n.
struct GNUNET_CRYPTO_EddsaPublicKey public_key
unsigned int mem
How much memory should we use (relates to the number of entries in the map).