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
  19 /**
  20  * @file util/crypto_ecc_dlog.c
  21  * @brief ECC addition and discreate logarithm for small values.
  22  *        Allows us to use ECC for computations as long as the
  23  *        result is relativey small.
  24  * @author Christian Grothoff
  25  */
  26 #include "platform.h"
  27 #include <gcrypt.h>
  28 #include "gnunet_crypto_lib.h"
  29 #include "gnunet_container_lib.h"
  30
  31
  32 /**
  33  * Name of the curve we are using.  Note that we have hard-coded
  34  * structs that use 256 bits, so using a bigger curve will require
  35  * changes that break stuff badly.  The name of the curve given here
  36  * must be agreed by all peers and be supported by libgcrypt.
  37  */
  38 #define CURVE "Ed25519"
  39
  40
  41 /**
  42  *
  43  */
  44 static void
  45 extract_pk (gcry_mpi_point_t pt,
  46             gcry_ctx_t ctx,
  47             struct GNUNET_PeerIdentity *pid)
  48 {
  49   gcry_mpi_t q_y;
  50
  51   GNUNET_assert (0 == gcry_mpi_ec_set_point ("q", pt, ctx));
  52   q_y = gcry_mpi_ec_get_mpi ("q@eddsa", ctx, 0);
  53   GNUNET_assert (q_y);
  54   GNUNET_CRYPTO_mpi_print_unsigned (pid->public_key.q_y,
  55                                     sizeof (pid->public_key.q_y),
  56                                     q_y);
  57   gcry_mpi_release (q_y);
  58 }
  59
  60
  61 /**
  62  * Internal structure used to cache pre-calculated values for DLOG calculation.
  63  */
  64 struct GNUNET_CRYPTO_EccDlogContext
  65 {
  66   /**
  67    * Maximum absolute value the calculation supports.
  68    */
  69   unsigned int max;
  70
  71   /**
  72    * How much memory should we use (relates to the number of entries in the map).
  73    */
  74   unsigned int mem;
  75
  76   /**
  77    * Map mapping points (here "interpreted" as EdDSA public keys) to
  78    * a "void * = long" which corresponds to the numeric value of the
  79    * point.  As NULL is used to represent "unknown", the actual value
  80    * represented by the entry in the map is the "long" minus @e max.
  81    */
  82   struct GNUNET_CONTAINER_MultiPeerMap *map;
  83
  84   /**
  85    * Context to use for operations on the elliptic curve.
  86    */
  87   gcry_ctx_t ctx;
  88
  89 };
  90
  91
  92 /**
  93  * Convert point value to binary representation.
  94  *
  95  * @param edc calculation context for ECC operations
  96  * @param point computational point representation
  97  * @param[out] bin binary point representation
  98  */
  99 void
 100 GNUNET_CRYPTO_ecc_point_to_bin (struct GNUNET_CRYPTO_EccDlogContext *edc,
 101                                 gcry_mpi_point_t point,
 102                                 struct GNUNET_CRYPTO_EccPoint *bin)
 103 {
 104   gcry_mpi_t q_y;
 105
 106   GNUNET_assert (0 == gcry_mpi_ec_set_point ("q", point, edc->ctx));
 107   q_y = gcry_mpi_ec_get_mpi ("q@eddsa", edc->ctx, 0);
 108   GNUNET_assert (q_y);
 109   GNUNET_CRYPTO_mpi_print_unsigned (bin->q_y,
 110                                     sizeof (bin->q_y),
 111                                     q_y);
 112   gcry_mpi_release (q_y);
 113 }
 114
 115
 116 /**
 117  * Convert binary representation of a point to computational representation.
 118  *
 119  * @param edc calculation context for ECC operations
 120  * @param bin binary point representation
 121  * @return computational representation
 122  */
 123 gcry_mpi_point_t
 124 GNUNET_CRYPTO_ecc_bin_to_point (struct GNUNET_CRYPTO_EccDlogContext *edc,
 125                                 const struct GNUNET_CRYPTO_EccPoint *bin)
 126 {
 127   gcry_sexp_t pub_sexpr;
 128   gcry_ctx_t ctx;
 129   gcry_mpi_point_t q;
 130
 131   (void) edc;
 132   if (0 != gcry_sexp_build (&pub_sexpr, NULL,
 133                             "(public-key(ecc(curve " CURVE ")(q %b)))",
 134                             (int) sizeof (bin->q_y),
 135                             bin->q_y))
 136   {
 137     GNUNET_break (0);
 138     return NULL;
 139   }
 140   GNUNET_assert (0 == gcry_mpi_ec_new (&ctx, pub_sexpr, NULL));
 141   gcry_sexp_release (pub_sexpr);
 142   q = gcry_mpi_ec_get_point ("q", ctx, 0);
 143   gcry_ctx_release (ctx);
 144   return q;
 145 }
 146
 147
 148 /**
 149  * Do pre-calculation for ECC discrete logarithm for small factors.
 150  *
 151  * @param max maximum value the factor can be
 152  * @param mem memory to use (should be smaller than @a max), must not be zero.
 153  * @return NULL on error
 154  */
 155 struct GNUNET_CRYPTO_EccDlogContext *
 156 GNUNET_CRYPTO_ecc_dlog_prepare (unsigned int max,
 157                                 unsigned int mem)
 158 {
 159   struct GNUNET_CRYPTO_EccDlogContext *edc;
 160   unsigned int K = ((max + (mem-1)) / mem);
 161   gcry_mpi_point_t g;
 162   struct GNUNET_PeerIdentity key;
 163   gcry_mpi_point_t gKi;
 164   gcry_mpi_t fact;
 165   gcry_mpi_t n;
 166   unsigned int i;
 167
 168   GNUNET_assert (max < INT32_MAX);
 169   edc = GNUNET_new (struct GNUNET_CRYPTO_EccDlogContext);
 170   edc->max = max;
 171   edc->mem = mem;
 172
 173   edc->map = GNUNET_CONTAINER_multipeermap_create (mem * 2,
 174                                                    GNUNET_NO);
 175
 176   GNUNET_assert (0 == gcry_mpi_ec_new (&edc->ctx,
 177                                        NULL,
 178                                        CURVE));
 179   g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
 180   GNUNET_assert (NULL != g);
 181   fact = gcry_mpi_new (0);
 182   gKi = gcry_mpi_point_new (0);
 183   for (i=0;i<=mem;i++)
 184   {
 185     gcry_mpi_set_ui (fact, i * K);
 186     gcry_mpi_ec_mul (gKi, fact, g, edc->ctx);
 187     extract_pk (gKi, edc->ctx, &key);
 188     GNUNET_assert (GNUNET_OK ==
 189                    GNUNET_CONTAINER_multipeermap_put (edc->map,
 190                                                       &key,
 191                                                       (void*) (long) i + max,
 192                                                       GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
 193   }
 194   /* negative values */
 195   n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
 196   for (i=1;i<mem;i++)
 197   {
 198     gcry_mpi_set_ui (fact, i * K);
 199     gcry_mpi_sub (fact, n, fact);
 200     gcry_mpi_ec_mul (gKi, fact, g, edc->ctx);
 201     extract_pk (gKi, edc->ctx, &key);
 202     GNUNET_assert (GNUNET_OK ==
 203                    GNUNET_CONTAINER_multipeermap_put (edc->map,
 204                                                       &key,
 205                                                       (void*) (long) max - i,
 206                                                       GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
 207   }
 208   gcry_mpi_release (fact);
 209   gcry_mpi_release (n);
 210   gcry_mpi_point_release (gKi);
 211   gcry_mpi_point_release (g);
 212   return edc;
 213 }
 214
 215
 216 /**
 217  * Calculate ECC discrete logarithm for small factors.
 218  *
 219  * @param edc precalculated values, determine range of factors
 220  * @param input point on the curve to factor
 221  * @return INT_MAX if dlog failed, otherwise the factor
 222  */
 223 int
 224 GNUNET_CRYPTO_ecc_dlog (struct GNUNET_CRYPTO_EccDlogContext *edc,
 225                         gcry_mpi_point_t input)
 226 {
 227   unsigned int K = ((edc->max + (edc->mem-1)) / edc->mem);
 228   gcry_mpi_point_t g;
 229   struct GNUNET_PeerIdentity key;
 230   gcry_mpi_point_t q;
 231   unsigned int i;
 232   int res;
 233   void *retp;
 234
 235   g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
 236   GNUNET_assert (NULL != g);
 237   q = gcry_mpi_point_new (0);
 238
 239   res = INT_MAX;
 240   for (i=0;i<=edc->max/edc->mem;i++)
 241   {
 242     if (0 == i)
 243       extract_pk (input, edc->ctx, &key);
 244     else
 245       extract_pk (q, edc->ctx, &key);
 246     retp = GNUNET_CONTAINER_multipeermap_get (edc->map,
 247                                               &key);
 248     if (NULL != retp)
 249     {
 250       res = (((long) retp) - edc->max) * K - i;
 251       /* we continue the loop here to make the implementation
 252          "constant-time". If we do not care about this, we could just
 253          'break' here and do fewer operations... */
 254     }
 255     if (i == edc->max/edc->mem)
 256       break;
 257     /* q = q + g */
 258     if (0 == i)
 259       gcry_mpi_ec_add (q, input, g, edc->ctx);
 260     else
 261       gcry_mpi_ec_add (q, q, g, edc->ctx);
 262   }
 263   gcry_mpi_point_release (g);
 264   gcry_mpi_point_release (q);
 265
 266   return res;
 267 }
 268
 269
 270 /**
 271  * Generate a random value mod n.
 272  *
 273  * @param edc ECC context
 274  * @return random value mod n.
 275  */
 276 gcry_mpi_t
 277 GNUNET_CRYPTO_ecc_random_mod_n (struct GNUNET_CRYPTO_EccDlogContext *edc)
 278 {
 279   gcry_mpi_t n;
 280   unsigned int highbit;
 281   gcry_mpi_t r;
 282
 283   n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
 284
 285   /* check public key for number of bits, bail out if key is all zeros */
 286   highbit = 256; /* Curve25519 */
 287   while ( (! gcry_mpi_test_bit (n, highbit)) &&
 288           (0 != highbit) )
 289     highbit--;
 290   GNUNET_assert (0 != highbit);
 291   /* generate fact < n (without bias) */
 292   GNUNET_assert (NULL != (r = gcry_mpi_new (0)));
 293   do {
 294     gcry_mpi_randomize (r,
 295                         highbit + 1,
 296                         GCRY_STRONG_RANDOM);
 297   }
 298   while (gcry_mpi_cmp (r, n) >= 0);
 299   gcry_mpi_release (n);
 300   return r;
 301 }
 302
 303
 304 /**
 305  * Release precalculated values.
 306  *
 307  * @param edc dlog context
 308  */
 309 void
 310 GNUNET_CRYPTO_ecc_dlog_release (struct GNUNET_CRYPTO_EccDlogContext *edc)
 311 {
 312   gcry_ctx_release (edc->ctx);
 313   GNUNET_CONTAINER_multipeermap_destroy (edc->map);
 314   GNUNET_free (edc);
 315 }
 316
 317
 318 /**
 319  * Multiply the generator g of the elliptic curve by @a val
 320  * to obtain the point on the curve representing @a val.
 321  * Afterwards, point addition will correspond to integer
 322  * addition.  #GNUNET_CRYPTO_ecc_dlog() can be used to
 323  * convert a point back to an integer (as long as the
 324  * integer is smaller than the MAX of the @a edc context).
 325  *
 326  * @param edc calculation context for ECC operations
 327  * @param val value to encode into a point
 328  * @return representation of the value as an ECC point,
 329  *         must be freed using #GNUNET_CRYPTO_ecc_free()
 330  */
 331 gcry_mpi_point_t
 332 GNUNET_CRYPTO_ecc_dexp (struct GNUNET_CRYPTO_EccDlogContext *edc,
 333                         int val)
 334 {
 335   gcry_mpi_t fact;
 336   gcry_mpi_t n;
 337   gcry_mpi_point_t g;
 338   gcry_mpi_point_t r;
 339
 340   g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
 341   GNUNET_assert (NULL != g);
 342   fact = gcry_mpi_new (0);
 343   if (val < 0)
 344   {
 345     n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
 346     gcry_mpi_set_ui (fact, - val);
 347     gcry_mpi_sub (fact, n, fact);
 348     gcry_mpi_release (n);
 349   }
 350   else
 351   {
 352     gcry_mpi_set_ui (fact, val);
 353   }
 354   r = gcry_mpi_point_new (0);
 355   gcry_mpi_ec_mul (r, fact, g, edc->ctx);
 356   gcry_mpi_release (fact);
 357   gcry_mpi_point_release (g);
 358   return r;
 359 }
 360
 361
 362 /**
 363  * Multiply the generator g of the elliptic curve by @a val
 364  * to obtain the point on the curve representing @a val.
 365  *
 366  * @param edc calculation context for ECC operations
 367  * @param val (positive) value to encode into a point
 368  * @return representation of the value as an ECC point,
 369  *         must be freed using #GNUNET_CRYPTO_ecc_free()
 370  */
 371 gcry_mpi_point_t
 372 GNUNET_CRYPTO_ecc_dexp_mpi (struct GNUNET_CRYPTO_EccDlogContext *edc,
 373                             gcry_mpi_t val)
 374 {
 375   gcry_mpi_point_t g;
 376   gcry_mpi_point_t r;
 377
 378   g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
 379   GNUNET_assert (NULL != g);
 380   r = gcry_mpi_point_new (0);
 381   gcry_mpi_ec_mul (r, val, g, edc->ctx);
 382   gcry_mpi_point_release (g);
 383   return r;
 384 }
 385
 386
 387 /**
 388  * Add two points on the elliptic curve.
 389  *
 390  * @param edc calculation context for ECC operations
 391  * @param a some value
 392  * @param b some value
 393  * @return @a a + @a b, must be freed using #GNUNET_CRYPTO_ecc_free()
 394  */
 395 gcry_mpi_point_t
 396 GNUNET_CRYPTO_ecc_add (struct GNUNET_CRYPTO_EccDlogContext *edc,
 397                        gcry_mpi_point_t a,
 398                        gcry_mpi_point_t b)
 399 {
 400   gcry_mpi_point_t r;
 401
 402   r = gcry_mpi_point_new (0);
 403   gcry_mpi_ec_add (r, a, b, edc->ctx);
 404   return r;
 405 }
 406
 407
 408 /**
 409  * Multiply the point @a p on the elliptic curve by @a val.
 410  *
 411  * @param edc calculation context for ECC operations
 412  * @param p point to multiply
 413  * @param val (positive) value to encode into a point
 414  * @return representation of the value as an ECC point,
 415  *         must be freed using #GNUNET_CRYPTO_ecc_free()
 416  */
 417 gcry_mpi_point_t
 418 GNUNET_CRYPTO_ecc_pmul_mpi (struct GNUNET_CRYPTO_EccDlogContext *edc,
 419                             gcry_mpi_point_t p,
 420                             gcry_mpi_t val)
 421 {
 422   gcry_mpi_point_t r;
 423
 424   r = gcry_mpi_point_new (0);
 425   gcry_mpi_ec_mul (r, val, p, edc->ctx);
 426   return r;
 427 }
 428
 429
 430 /**
 431  * Obtain a random point on the curve and its
 432  * additive inverse. Both returned values
 433  * must be freed using #GNUNET_CRYPTO_ecc_free().
 434  *
 435  * @param edc calculation context for ECC operations
 436  * @param[out] r set to a random point on the curve
 437  * @param[out] r_inv set to the additive inverse of @a r
 438  */
 439 void
 440 GNUNET_CRYPTO_ecc_rnd (struct GNUNET_CRYPTO_EccDlogContext *edc,
 441                        gcry_mpi_point_t *r,
 442                        gcry_mpi_point_t *r_inv)
 443 {
 444   gcry_mpi_t fact;
 445   gcry_mpi_t n;
 446   gcry_mpi_point_t g;
 447
 448   fact = GNUNET_CRYPTO_ecc_random_mod_n (edc);
 449
 450   /* calculate 'r' */
 451   g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
 452   GNUNET_assert (NULL != g);
 453   *r = gcry_mpi_point_new (0);
 454   gcry_mpi_ec_mul (*r, fact, g, edc->ctx);
 455
 456   /* calculate 'r_inv' */
 457   n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
 458   gcry_mpi_sub (fact, n, fact); /* fact = n - fact = - fact */
 459   *r_inv = gcry_mpi_point_new (0);
 460   gcry_mpi_ec_mul (*r_inv, fact, g, edc->ctx);
 461
 462   gcry_mpi_release (n);
 463   gcry_mpi_release (fact);
 464   gcry_mpi_point_release (g);
 465 }
 466
 467
 468 /**
 469  * Obtain a random scalar for point multiplication on the curve and
 470  * its multiplicative inverse.
 471  *
 472  * @param edc calculation context for ECC operations
 473  * @param[out] r set to a random scalar on the curve
 474  * @param[out] r_inv set to the multiplicative inverse of @a r
 475  */
 476 void
 477 GNUNET_CRYPTO_ecc_rnd_mpi (struct GNUNET_CRYPTO_EccDlogContext *edc,
 478                            gcry_mpi_t *r,
 479                            gcry_mpi_t *r_inv)
 480 {
 481   gcry_mpi_t n;
 482
 483   *r = GNUNET_CRYPTO_ecc_random_mod_n (edc);
 484   /* r_inv = n - r = - r */
 485   *r_inv = gcry_mpi_new (0);
 486   n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
 487   gcry_mpi_sub (*r_inv, n, *r);
 488 }
 489
 490
 491 /**
 492  * Free a point value returned by the API.
 493  *
 494  * @param p point to free
 495  */
 496 void
 497 GNUNET_CRYPTO_ecc_free (gcry_mpi_point_t p)
 498 {
 499   gcry_mpi_point_release (p);
 500 }
 501
 502
 503 /* end of crypto_ecc_dlog.c */