Merge branch 'master' of ssh://gnunet.org/gnunet
[oweals/gnunet.git] / src / util / crypto_ecc_dlog.c
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
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.
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      General Public License for more details.
14
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.
19 */
20
21 /**
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
27  */
28 #include "platform.h"
29 #include <gcrypt.h>
30 #include "gnunet_crypto_lib.h"
31 #include "gnunet_container_lib.h"
32
33
34 /**
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.
39  */
40 #define CURVE "Ed25519"
41
42
43 /**
44  *
45  */
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);
56   GNUNET_CRYPTO_mpi_print_unsigned (pid->public_key.q_y,
57                                     sizeof (pid->public_key.q_y),
58                                     q_y);
59   gcry_mpi_release (q_y);
60 }
61
62
63 /**
64  * Internal structure used to cache pre-calculated values for DLOG calculation.
65  */
66 struct GNUNET_CRYPTO_EccDlogContext
67 {
68   /**
69    * Maximum absolute value the calculation supports.
70    */
71   unsigned int max;
72
73   /**
74    * How much memory should we use (relates to the number of entries in the map).
75    */
76   unsigned int mem;
77
78   /**
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.
83    */
84   struct GNUNET_CONTAINER_MultiPeerMap *map;
85
86   /**
87    * Context to use for operations on the elliptic curve.
88    */
89   gcry_ctx_t ctx;
90
91 };
92
93
94 /**
95  * Convert point value to binary representation.
96  *
97  * @param edc calculation context for ECC operations
98  * @param point computational point representation
99  * @param[out] bin binary point representation
100  */
101 void
102 GNUNET_CRYPTO_ecc_point_to_bin (struct GNUNET_CRYPTO_EccDlogContext *edc,
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);
111   GNUNET_CRYPTO_mpi_print_unsigned (bin->q_y,
112                                     sizeof (bin->q_y),
113                                     q_y);
114   gcry_mpi_release (q_y);
115 }
116
117
118 /**
119  * Convert binary representation of a point to computational representation.
120  *
121  * @param edc calculation context for ECC operations
122  * @param bin binary point representation
123  * @return computational representation
124  */
125 gcry_mpi_point_t
126 GNUNET_CRYPTO_ecc_bin_to_point (struct GNUNET_CRYPTO_EccDlogContext *edc,
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   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
149 /**
150  * Do pre-calculation for ECC discrete logarithm for small factors.
151  *
152  * @param max maximum value the factor can be
153  * @param mem memory to use (should be smaller than @a max), must not be zero.
154  * @return NULL on error
155  */
156 struct GNUNET_CRYPTO_EccDlogContext *
157 GNUNET_CRYPTO_ecc_dlog_prepare (unsigned int max,
158                                 unsigned int mem)
159 {
160   struct GNUNET_CRYPTO_EccDlogContext *edc;
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);
170   edc = GNUNET_new (struct GNUNET_CRYPTO_EccDlogContext);
171   edc->max = max;
172   edc->mem = mem;
173
174   edc->map = GNUNET_CONTAINER_multipeermap_create (mem * 2,
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);
189     GNUNET_assert (GNUNET_OK ==
190                    GNUNET_CONTAINER_multipeermap_put (edc->map,
191                                                       &key,
192                                                       (void*) (long) i + max,
193                                                       GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
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);
203     GNUNET_assert (GNUNET_OK ==
204                    GNUNET_CONTAINER_multipeermap_put (edc->map,
205                                                       &key,
206                                                       (void*) (long) max - i,
207                                                       GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
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
217 /**
218  * Calculate ECC discrete logarithm for small factors.
219  *
220  * @param edc precalculated values, determine range of factors
221  * @param input point on the curve to factor
222  * @return INT_MAX if dlog failed, otherwise the factor
223  */
224 int
225 GNUNET_CRYPTO_ecc_dlog (struct GNUNET_CRYPTO_EccDlogContext *edc,
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);
247     retp = GNUNET_CONTAINER_multipeermap_get (edc->map,
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
271 /**
272  * Generate a random value mod n.
273  *
274  * @param edc ECC context
275  * @return random value mod n.
276  */
277 gcry_mpi_t
278 GNUNET_CRYPTO_ecc_random_mod_n (struct GNUNET_CRYPTO_EccDlogContext *edc)
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     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
305 /**
306  * Release precalculated values.
307  *
308  * @param edc dlog context
309  */
310 void
311 GNUNET_CRYPTO_ecc_dlog_release (struct GNUNET_CRYPTO_EccDlogContext *edc)
312 {
313   gcry_ctx_release (edc->ctx);
314   GNUNET_CONTAINER_multipeermap_destroy (edc->map);
315   GNUNET_free (edc);
316 }
317
318
319 /**
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).
326  *
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()
331  */
332 gcry_mpi_point_t
333 GNUNET_CRYPTO_ecc_dexp (struct GNUNET_CRYPTO_EccDlogContext *edc,
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
363 /**
364  * Multiply the generator g of the elliptic curve by @a val
365  * to obtain the point on the curve representing @a val.
366  *
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()
371  */
372 gcry_mpi_point_t
373 GNUNET_CRYPTO_ecc_dexp_mpi (struct GNUNET_CRYPTO_EccDlogContext *edc,
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
388 /**
389  * Add two points on the elliptic curve.
390  *
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()
395  */
396 gcry_mpi_point_t
397 GNUNET_CRYPTO_ecc_add (struct GNUNET_CRYPTO_EccDlogContext *edc,
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
409 /**
410  * Multiply the point @a p on the elliptic curve by @a val.
411  *
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()
417  */
418 gcry_mpi_point_t
419 GNUNET_CRYPTO_ecc_pmul_mpi (struct GNUNET_CRYPTO_EccDlogContext *edc,
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
431 /**
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().
435  *
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
439  */
440 void
441 GNUNET_CRYPTO_ecc_rnd (struct GNUNET_CRYPTO_EccDlogContext *edc,
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
469 /**
470  * Obtain a random scalar for point multiplication on the curve and
471  * its multiplicative inverse.
472  *
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
476  */
477 void
478 GNUNET_CRYPTO_ecc_rnd_mpi (struct GNUNET_CRYPTO_EccDlogContext *edc,
479                            gcry_mpi_t *r,
480                            gcry_mpi_t *r_inv)
481 {
482   gcry_mpi_t n;
483
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);
489 }
490
491
492 /**
493  * Free a point value returned by the API.
494  *
495  * @param p point to free
496  */
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 */