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   (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 */