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    * Maximum absolute value the calculation supports.
  69    */
  70   unsigned int max;
  71
  72   /**
  73    * How much memory should we use (relates to the number of entries in the map).
  74    */
  75   unsigned int mem;
  76
  77   /**
  78    * Map mapping points (here "interpreted" as EdDSA public keys) to
  79    * a "void * = long" which corresponds to the numeric value of the
  80    * point.  As NULL is used to represent "unknown", the actual value
  81    * represented by the entry in the map is the "long" minus @e max.
  82    */
  83   struct GNUNET_CONTAINER_MultiPeerMap *map;
  84
  85   /**
  86    * Context to use for operations on the elliptic curve.
  87    */
  88   gcry_ctx_t ctx;
  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     {
 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 */