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