GNUnet  0.11.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 
100 void
102  gcry_mpi_point_t point,
103  struct GNUNET_CRYPTO_EccPoint *bin)
104 {
105  gcry_mpi_t q_y;
106 
107  GNUNET_assert (0 == gcry_mpi_ec_set_point ("q", point, edc->ctx));
108  q_y = gcry_mpi_ec_get_mpi ("q@eddsa", edc->ctx, 0);
109  GNUNET_assert (q_y);
111  sizeof(bin->q_y),
112  q_y);
113  gcry_mpi_release (q_y);
114 }
115 
116 
124 gcry_mpi_point_t
126  const struct GNUNET_CRYPTO_EccPoint *bin)
127 {
128  gcry_sexp_t pub_sexpr;
129  gcry_ctx_t ctx;
130  gcry_mpi_point_t q;
131 
132  (void) edc;
133  if (0 != gcry_sexp_build (&pub_sexpr, NULL,
134  "(public-key(ecc(curve " CURVE ")(q %b)))",
135  (int) sizeof(bin->q_y),
136  bin->q_y))
137  {
138  GNUNET_break (0);
139  return NULL;
140  }
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);
145  return q;
146 }
147 
148 
158  unsigned int mem)
159 {
161  unsigned int K = ((max + (mem - 1)) / mem);
162  gcry_mpi_point_t g;
163  struct GNUNET_PeerIdentity key;
164  gcry_mpi_point_t gKi;
165  gcry_mpi_t fact;
166  gcry_mpi_t n;
167  unsigned int i;
168 
169  GNUNET_assert (max < INT32_MAX);
171  edc->max = max;
172  edc->mem = mem;
173 
175  GNUNET_NO);
176 
177  GNUNET_assert (0 == gcry_mpi_ec_new (&edc->ctx,
178  NULL,
179  CURVE));
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);
184  for (i = 0; i <= mem; i++)
185  {
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);
191  &key,
192  (void*) (long) i + max,
194  }
195  /* negative values */
196  n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
197  for (i = 1; i < mem; i++)
198  {
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);
205  &key,
206  (void*) (long) max - i,
208  }
209  gcry_mpi_release (fact);
210  gcry_mpi_release (n);
211  gcry_mpi_point_release (gKi);
212  gcry_mpi_point_release (g);
213  return edc;
214 }
215 
216 
224 int
226  gcry_mpi_point_t input)
227 {
228  unsigned int K = ((edc->max + (edc->mem - 1)) / edc->mem);
229  gcry_mpi_point_t g;
230  struct GNUNET_PeerIdentity key;
231  gcry_mpi_point_t q;
232  unsigned int i;
233  int res;
234  void *retp;
235 
236  g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
237  GNUNET_assert (NULL != g);
238  q = gcry_mpi_point_new (0);
239 
240  res = INT_MAX;
241  for (i = 0; i <= edc->max / edc->mem; i++)
242  {
243  if (0 == i)
244  extract_pk (input, edc->ctx, &key);
245  else
246  extract_pk (q, edc->ctx, &key);
248  &key);
249  if (NULL != retp)
250  {
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... */
255  }
256  if (i == edc->max / edc->mem)
257  break;
258  /* q = q + g */
259  if (0 == i)
260  gcry_mpi_ec_add (q, input, g, edc->ctx);
261  else
262  gcry_mpi_ec_add (q, q, g, edc->ctx);
263  }
264  gcry_mpi_point_release (g);
265  gcry_mpi_point_release (q);
266 
267  return res;
268 }
269 
270 
277 gcry_mpi_t
279 {
280  gcry_mpi_t n;
281  unsigned int highbit;
282  gcry_mpi_t r;
283 
284  n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
285 
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)) &&
289  (0 != highbit))
290  highbit--;
291  GNUNET_assert (0 != highbit);
292  /* generate fact < n (without bias) */
293  GNUNET_assert (NULL != (r = gcry_mpi_new (0)));
294  do
295  {
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:78
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).