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 
67 {
71  unsigned int max;
72 
76  unsigned int mem;
77 
85 
89  gcry_ctx_t ctx;
90 
91 };
92 
93 
101 void
103  gcry_mpi_point_t point,
104  struct GNUNET_CRYPTO_EccPoint *bin)
105 {
106  gcry_mpi_t q_y;
107 
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);
110  GNUNET_assert (q_y);
112  sizeof (bin->q_y),
113  q_y);
114  gcry_mpi_release (q_y);
115 }
116 
117 
125 gcry_mpi_point_t
127  const struct GNUNET_CRYPTO_EccPoint *bin)
128 {
129  gcry_sexp_t pub_sexpr;
130  gcry_ctx_t ctx;
131  gcry_mpi_point_t q;
132 
133  (void) edc;
134  if (0 != gcry_sexp_build (&pub_sexpr, NULL,
135  "(public-key(ecc(curve " CURVE ")(q %b)))",
136  (int) sizeof (bin->q_y),
137  bin->q_y))
138  {
139  GNUNET_break (0);
140  return NULL;
141  }
142  GNUNET_assert (0 == gcry_mpi_ec_new (&ctx, pub_sexpr, NULL));
143  gcry_sexp_release (pub_sexpr);
144  q = gcry_mpi_ec_get_point ("q", ctx, 0);
145  gcry_ctx_release (ctx);
146  return q;
147 }
148 
149 
159  unsigned int mem)
160 {
162  unsigned int K = ((max + (mem-1)) / mem);
163  gcry_mpi_point_t g;
164  struct GNUNET_PeerIdentity key;
165  gcry_mpi_point_t gKi;
166  gcry_mpi_t fact;
167  gcry_mpi_t n;
168  unsigned int i;
169 
170  GNUNET_assert (max < INT32_MAX);
172  edc->max = max;
173  edc->mem = mem;
174 
176  GNUNET_NO);
177 
178  GNUNET_assert (0 == gcry_mpi_ec_new (&edc->ctx,
179  NULL,
180  CURVE));
181  g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
182  GNUNET_assert (NULL != g);
183  fact = gcry_mpi_new (0);
184  gKi = gcry_mpi_point_new (0);
185  for (i=0;i<=mem;i++)
186  {
187  gcry_mpi_set_ui (fact, i * K);
188  gcry_mpi_ec_mul (gKi, fact, g, edc->ctx);
189  extract_pk (gKi, edc->ctx, &key);
192  &key,
193  (void*) (long) i + max,
195  }
196  /* negative values */
197  n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
198  for (i=1;i<mem;i++)
199  {
200  gcry_mpi_set_ui (fact, i * K);
201  gcry_mpi_sub (fact, n, fact);
202  gcry_mpi_ec_mul (gKi, fact, g, edc->ctx);
203  extract_pk (gKi, edc->ctx, &key);
206  &key,
207  (void*) (long) max - i,
209  }
210  gcry_mpi_release (fact);
211  gcry_mpi_release (n);
212  gcry_mpi_point_release (gKi);
213  gcry_mpi_point_release (g);
214  return edc;
215 }
216 
217 
225 int
227  gcry_mpi_point_t input)
228 {
229  unsigned int K = ((edc->max + (edc->mem-1)) / edc->mem);
230  gcry_mpi_point_t g;
231  struct GNUNET_PeerIdentity key;
232  gcry_mpi_point_t q;
233  unsigned int i;
234  int res;
235  void *retp;
236 
237  g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
238  GNUNET_assert (NULL != g);
239  q = gcry_mpi_point_new (0);
240 
241  res = INT_MAX;
242  for (i=0;i<=edc->max/edc->mem;i++)
243  {
244  if (0 == i)
245  extract_pk (input, edc->ctx, &key);
246  else
247  extract_pk (q, edc->ctx, &key);
249  &key);
250  if (NULL != retp)
251  {
252  res = (((long) retp) - edc->max) * K - i;
253  /* we continue the loop here to make the implementation
254  "constant-time". If we do not care about this, we could just
255  'break' here and do fewer operations... */
256  }
257  if (i == edc->max/edc->mem)
258  break;
259  /* q = q + g */
260  if (0 == i)
261  gcry_mpi_ec_add (q, input, g, edc->ctx);
262  else
263  gcry_mpi_ec_add (q, q, g, edc->ctx);
264  }
265  gcry_mpi_point_release (g);
266  gcry_mpi_point_release (q);
267 
268  return res;
269 }
270 
271 
278 gcry_mpi_t
280 {
281  gcry_mpi_t n;
282  unsigned int highbit;
283  gcry_mpi_t r;
284 
285  n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
286 
287  /* check public key for number of bits, bail out if key is all zeros */
288  highbit = 256; /* Curve25519 */
289  while ( (! gcry_mpi_test_bit (n, highbit)) &&
290  (0 != highbit) )
291  highbit--;
292  GNUNET_assert (0 != highbit);
293  /* generate fact < n (without bias) */
294  GNUNET_assert (NULL != (r = gcry_mpi_new (0)));
295  do {
296  gcry_mpi_randomize (r,
297  highbit + 1,
298  GCRY_STRONG_RANDOM);
299  }
300  while (gcry_mpi_cmp (r, n) >= 0);
301  gcry_mpi_release (n);
302  return r;
303 }
304 
305 
311 void
313 {
314  gcry_ctx_release (edc->ctx);
316  GNUNET_free (edc);
317 }
318 
319 
333 gcry_mpi_point_t
335  int val)
336 {
337  gcry_mpi_t fact;
338  gcry_mpi_t n;
339  gcry_mpi_point_t g;
340  gcry_mpi_point_t r;
341 
342  g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
343  GNUNET_assert (NULL != g);
344  fact = gcry_mpi_new (0);
345  if (val < 0)
346  {
347  n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
348  gcry_mpi_set_ui (fact, - val);
349  gcry_mpi_sub (fact, n, fact);
350  gcry_mpi_release (n);
351  }
352  else
353  {
354  gcry_mpi_set_ui (fact, val);
355  }
356  r = gcry_mpi_point_new (0);
357  gcry_mpi_ec_mul (r, fact, g, edc->ctx);
358  gcry_mpi_release (fact);
359  gcry_mpi_point_release (g);
360  return r;
361 }
362 
363 
373 gcry_mpi_point_t
375  gcry_mpi_t val)
376 {
377  gcry_mpi_point_t g;
378  gcry_mpi_point_t r;
379 
380  g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
381  GNUNET_assert (NULL != g);
382  r = gcry_mpi_point_new (0);
383  gcry_mpi_ec_mul (r, val, g, edc->ctx);
384  gcry_mpi_point_release (g);
385  return r;
386 }
387 
388 
397 gcry_mpi_point_t
399  gcry_mpi_point_t a,
400  gcry_mpi_point_t b)
401 {
402  gcry_mpi_point_t r;
403 
404  r = gcry_mpi_point_new (0);
405  gcry_mpi_ec_add (r, a, b, edc->ctx);
406  return r;
407 }
408 
409 
419 gcry_mpi_point_t
421  gcry_mpi_point_t p,
422  gcry_mpi_t val)
423 {
424  gcry_mpi_point_t r;
425 
426  r = gcry_mpi_point_new (0);
427  gcry_mpi_ec_mul (r, val, p, edc->ctx);
428  return r;
429 }
430 
431 
441 void
443  gcry_mpi_point_t *r,
444  gcry_mpi_point_t *r_inv)
445 {
446  gcry_mpi_t fact;
447  gcry_mpi_t n;
448  gcry_mpi_point_t g;
449 
450  fact = GNUNET_CRYPTO_ecc_random_mod_n (edc);
451 
452  /* calculate 'r' */
453  g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
454  GNUNET_assert (NULL != g);
455  *r = gcry_mpi_point_new (0);
456  gcry_mpi_ec_mul (*r, fact, g, edc->ctx);
457 
458  /* calculate 'r_inv' */
459  n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
460  gcry_mpi_sub (fact, n, fact); /* fact = n - fact = - fact */
461  *r_inv = gcry_mpi_point_new (0);
462  gcry_mpi_ec_mul (*r_inv, fact, g, edc->ctx);
463 
464  gcry_mpi_release (n);
465  gcry_mpi_release (fact);
466  gcry_mpi_point_release (g);
467 }
468 
469 
478 void
480  gcry_mpi_t *r,
481  gcry_mpi_t *r_inv)
482 {
483  gcry_mpi_t n;
484 
486  /* r_inv = n - r = - r */
487  *r_inv = gcry_mpi_new (0);
488  n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
489  gcry_mpi_sub (*r_inv, n, *r);
490 }
491 
492 
498 void
499 GNUNET_CRYPTO_ecc_free (gcry_mpi_point_t p)
500 {
501  gcry_mpi_point_release (p);
502 }
503 
504 
505 /* 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:81
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:78
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).