first try raw, unexpanded name
[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 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
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   (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
150 /**
151  * Do pre-calculation for ECC discrete logarithm for small factors.
152  *
153  * @param max maximum value the factor can be
154  * @param mem memory to use (should be smaller than @a max), must not be zero.
155  * @return NULL on error
156  */
157 struct GNUNET_CRYPTO_EccDlogContext *
158 GNUNET_CRYPTO_ecc_dlog_prepare (unsigned int max,
159                                 unsigned int mem)
160 {
161   struct GNUNET_CRYPTO_EccDlogContext *edc;
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);
171   edc = GNUNET_new (struct GNUNET_CRYPTO_EccDlogContext);
172   edc->max = max;
173   edc->mem = mem;
174
175   edc->map = GNUNET_CONTAINER_multipeermap_create (mem * 2,
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);
190     GNUNET_assert (GNUNET_OK ==
191                    GNUNET_CONTAINER_multipeermap_put (edc->map,
192                                                       &key,
193                                                       (void*) (long) i + max,
194                                                       GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
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);
204     GNUNET_assert (GNUNET_OK ==
205                    GNUNET_CONTAINER_multipeermap_put (edc->map,
206                                                       &key,
207                                                       (void*) (long) max - i,
208                                                       GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
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
218 /**
219  * Calculate ECC discrete logarithm for small factors.
220  *
221  * @param edc precalculated values, determine range of factors
222  * @param input point on the curve to factor
223  * @return INT_MAX if dlog failed, otherwise the factor
224  */
225 int
226 GNUNET_CRYPTO_ecc_dlog (struct GNUNET_CRYPTO_EccDlogContext *edc,
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);
248     retp = GNUNET_CONTAINER_multipeermap_get (edc->map,
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
272 /**
273  * Generate a random value mod n.
274  *
275  * @param edc ECC context
276  * @return random value mod n.
277  */
278 gcry_mpi_t
279 GNUNET_CRYPTO_ecc_random_mod_n (struct GNUNET_CRYPTO_EccDlogContext *edc)
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
306 /**
307  * Release precalculated values.
308  *
309  * @param edc dlog context
310  */
311 void
312 GNUNET_CRYPTO_ecc_dlog_release (struct GNUNET_CRYPTO_EccDlogContext *edc)
313 {
314   gcry_ctx_release (edc->ctx);
315   GNUNET_CONTAINER_multipeermap_destroy (edc->map);
316   GNUNET_free (edc);
317 }
318
319
320 /**
321  * Multiply the generator g of the elliptic curve by @a val
322  * to obtain the point on the curve representing @a val.
323  * Afterwards, point addition will correspond to integer
324  * addition.  #GNUNET_CRYPTO_ecc_dlog() can be used to
325  * convert a point back to an integer (as long as the
326  * integer is smaller than the MAX of the @a edc context).
327  *
328  * @param edc calculation context for ECC operations
329  * @param val value to encode into a point
330  * @return representation of the value as an ECC point,
331  *         must be freed using #GNUNET_CRYPTO_ecc_free()
332  */
333 gcry_mpi_point_t
334 GNUNET_CRYPTO_ecc_dexp (struct GNUNET_CRYPTO_EccDlogContext *edc,
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
364 /**
365  * Multiply the generator g of the elliptic curve by @a val
366  * to obtain the point on the curve representing @a val.
367  *
368  * @param edc calculation context for ECC operations
369  * @param val (positive) value to encode into a point
370  * @return representation of the value as an ECC point,
371  *         must be freed using #GNUNET_CRYPTO_ecc_free()
372  */
373 gcry_mpi_point_t
374 GNUNET_CRYPTO_ecc_dexp_mpi (struct GNUNET_CRYPTO_EccDlogContext *edc,
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
389 /**
390  * Add two points on the elliptic curve.
391  *
392  * @param edc calculation context for ECC operations
393  * @param a some value
394  * @param b some value
395  * @return @a a + @a b, must be freed using #GNUNET_CRYPTO_ecc_free()
396  */
397 gcry_mpi_point_t
398 GNUNET_CRYPTO_ecc_add (struct GNUNET_CRYPTO_EccDlogContext *edc,
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
410 /**
411  * Multiply the point @a p on the elliptic curve by @a val.
412  *
413  * @param edc calculation context for ECC operations
414  * @param p point to multiply
415  * @param val (positive) value to encode into a point
416  * @return representation of the value as an ECC point,
417  *         must be freed using #GNUNET_CRYPTO_ecc_free()
418  */
419 gcry_mpi_point_t
420 GNUNET_CRYPTO_ecc_pmul_mpi (struct GNUNET_CRYPTO_EccDlogContext *edc,
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
432 /**
433  * Obtain a random point on the curve and its
434  * additive inverse. Both returned values
435  * must be freed using #GNUNET_CRYPTO_ecc_free().
436  *
437  * @param edc calculation context for ECC operations
438  * @param[out] r set to a random point on the curve
439  * @param[out] r_inv set to the additive inverse of @a r
440  */
441 void
442 GNUNET_CRYPTO_ecc_rnd (struct GNUNET_CRYPTO_EccDlogContext *edc,
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
470 /**
471  * Obtain a random scalar for point multiplication on the curve and
472  * its multiplicative inverse.
473  *
474  * @param edc calculation context for ECC operations
475  * @param[out] r set to a random scalar on the curve
476  * @param[out] r_inv set to the multiplicative inverse of @a r
477  */
478 void
479 GNUNET_CRYPTO_ecc_rnd_mpi (struct GNUNET_CRYPTO_EccDlogContext *edc,
480                            gcry_mpi_t *r,
481                            gcry_mpi_t *r_inv)
482 {
483   gcry_mpi_t n;
484
485   *r = GNUNET_CRYPTO_ecc_random_mod_n (edc);
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
493 /**
494  * Free a point value returned by the API.
495  *
496  * @param p point to free
497  */
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 */