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  * Convert point value to binary representation.
  95  *
  96  * @param edc calculation context for ECC operations
  97  * @param point computational point representation
  98  * @param[out] bin binary point representation
  99  */
 100 void
 101 GNUNET_CRYPTO_ecc_point_to_bin (struct GNUNET_CRYPTO_EccDlogContext *edc,
 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);
 110   GNUNET_CRYPTO_mpi_print_unsigned (bin->q_y,
 111                                     sizeof(bin->q_y),
 112                                     q_y);
 113   gcry_mpi_release (q_y);
 114 }
 115
 116
 117 /**
 118  * Convert binary representation of a point to computational representation.
 119  *
 120  * @param edc calculation context for ECC operations
 121  * @param bin binary point representation
 122  * @return computational representation
 123  */
 124 gcry_mpi_point_t
 125 GNUNET_CRYPTO_ecc_bin_to_point (struct GNUNET_CRYPTO_EccDlogContext *edc,
 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
 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   {
 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 */