src/util/crypto_ecc_dlog.c

   1 /*
   2      This file is part of GNUnet.
   3      Copyright (C) 2012, 2013, 2015 Christian Grothoff (and other contributing authors)
   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  * Do pre-calculation for ECC discrete logarithm for small factors.
  96  *
  97  * @param max maximum value the factor can be
  98  * @param mem memory to use (should be smaller than @a max), must not be zero.
  99  * @return @a max if dlog failed, otherwise the factor
 100  */
 101 struct GNUNET_CRYPTO_EccDlogContext *
 102 GNUNET_CRYPTO_ecc_dlog_prepare (unsigned int max,
 103                                 unsigned int mem)
 104 {
 105   struct GNUNET_CRYPTO_EccDlogContext *edc;
 106   unsigned int K = ((max + (mem-1)) / mem);
 107   gcry_mpi_point_t g;
 108   struct GNUNET_PeerIdentity key;
 109   gcry_mpi_point_t gKi;
 110   gcry_mpi_t fact;
 111   gcry_mpi_t n;
 112   unsigned int i;
 113
 114   GNUNET_assert (max < INT32_MAX);
 115   edc = GNUNET_new (struct GNUNET_CRYPTO_EccDlogContext);
 116   edc->max = max;
 117   edc->mem = mem;
 118
 119   edc->map = GNUNET_CONTAINER_multipeermap_create (mem * 2,
 120                                                    GNUNET_NO);
 121
 122   GNUNET_assert (0 == gcry_mpi_ec_new (&edc->ctx,
 123                                        NULL,
 124                                        CURVE));
 125   g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
 126   GNUNET_assert (NULL != g);
 127   fact = gcry_mpi_new (0);
 128   gKi = gcry_mpi_point_new (0);
 129   for (i=0;i<=mem;i++)
 130   {
 131     gcry_mpi_set_ui (fact, i * K);
 132     gcry_mpi_ec_mul (gKi, fact, g, edc->ctx);
 133     extract_pk (gKi, edc->ctx, &key);
 134     GNUNET_assert (GNUNET_OK ==
 135                    GNUNET_CONTAINER_multipeermap_put (edc->map,
 136                                                       &key,
 137                                                       (void*) (long) i + max,
 138                                                       GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
 139   }
 140   /* negative values */
 141   n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
 142   for (i=1;i<mem;i++)
 143   {
 144     gcry_mpi_set_ui (fact, i * K);
 145     gcry_mpi_sub (fact, n, fact);
 146     gcry_mpi_ec_mul (gKi, fact, g, edc->ctx);
 147     extract_pk (gKi, edc->ctx, &key);
 148     GNUNET_assert (GNUNET_OK ==
 149                    GNUNET_CONTAINER_multipeermap_put (edc->map,
 150                                                       &key,
 151                                                       (void*) (long) max - i,
 152                                                       GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
 153   }
 154   gcry_mpi_release (fact);
 155   gcry_mpi_release (n);
 156   gcry_mpi_point_release (gKi);
 157   gcry_mpi_point_release (g);
 158   return edc;
 159 }
 160
 161
 162 /**
 163  * Calculate ECC discrete logarithm for small factors.
 164  *
 165  * @param edc precalculated values, determine range of factors
 166  * @param input point on the curve to factor
 167  * @return `edc->max` if dlog failed, otherwise the factor
 168  */
 169 int
 170 GNUNET_CRYPTO_ecc_dlog (struct GNUNET_CRYPTO_EccDlogContext *edc,
 171                         gcry_mpi_point_t input)
 172 {
 173   unsigned int K = ((edc->max + (edc->mem-1)) / edc->mem);
 174   gcry_mpi_point_t g;
 175   struct GNUNET_PeerIdentity key;
 176   gcry_mpi_point_t q;
 177   unsigned int i;
 178   int res;
 179   void *retp;
 180
 181   g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
 182   GNUNET_assert (NULL != g);
 183   q = gcry_mpi_point_new (0);
 184
 185   res = edc->max;
 186   for (i=0;i<=edc->max/edc->mem;i++)
 187   {
 188     if (0 == i)
 189       extract_pk (input, edc->ctx, &key);
 190     else
 191       extract_pk (q, edc->ctx, &key);
 192     retp = GNUNET_CONTAINER_multipeermap_get (edc->map,
 193                                               &key);
 194     if (NULL != retp)
 195     {
 196       res = (((long) retp) - edc->max) * K - i;
 197       /* we continue the loop here to make the implementation
 198          "constant-time". If we do not care about this, we could just
 199          'break' here and do fewer operations... */
 200     }
 201     if (i == edc->max/edc->mem)
 202       break;
 203     /* q = q + g */
 204     if (0 == i)
 205       gcry_mpi_ec_add (q, input, g, edc->ctx);
 206     else
 207       gcry_mpi_ec_add (q, q, g, edc->ctx);
 208   }
 209   gcry_mpi_point_release (g);
 210   gcry_mpi_point_release (q);
 211
 212   return res;
 213 }
 214
 215
 216 /**
 217  * Generate a random value mod n.
 218  *
 219  * @param edc ECC context
 220  * @return random value mod n.
 221  */
 222 gcry_mpi_t
 223 GNUNET_CRYPTO_ecc_random_mod_n (struct GNUNET_CRYPTO_EccDlogContext *edc)
 224 {
 225   gcry_mpi_t n;
 226   unsigned int highbit;
 227   gcry_mpi_t r;
 228
 229   n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
 230
 231   /* check public key for number of bits, bail out if key is all zeros */
 232   highbit = 256; /* Curve25519 */
 233   while ( (! gcry_mpi_test_bit (n, highbit)) &&
 234           (0 != highbit) )
 235     highbit--;
 236   GNUNET_assert (0 != highbit);
 237   /* generate fact < n (without bias) */
 238   GNUNET_assert (NULL != (r = gcry_mpi_new (0)));
 239   do {
 240     gcry_mpi_randomize (r,
 241                         highbit + 1,
 242                         GCRY_STRONG_RANDOM);
 243   }
 244   while (gcry_mpi_cmp (r, n) >= 0);
 245   gcry_mpi_release (n);
 246   return r;
 247 }
 248
 249
 250 /**
 251  * Release precalculated values.
 252  *
 253  * @param edc dlog context
 254  */
 255 void
 256 GNUNET_CRYPTO_ecc_dlog_release (struct GNUNET_CRYPTO_EccDlogContext *edc)
 257 {
 258   gcry_ctx_release (edc->ctx);
 259   GNUNET_CONTAINER_multipeermap_destroy (edc->map);
 260   GNUNET_free (edc);
 261 }
 262
 263
 264 /**
 265  * Multiply the generator g of the elliptic curve by @a val
 266  * to obtain the point on the curve representing @a val.
 267  * Afterwards, point addition will correspond to integer
 268  * addition.  #GNUNET_CRYPTO_ecc_dlog() can be used to
 269  * convert a point back to an integer (as long as the
 270  * integer is smaller than the MAX of the @a edc context).
 271  *
 272  * @param edc calculation context for ECC operations
 273  * @param val value to encode into a point
 274  * @return representation of the value as an ECC point,
 275  *         must be freed using #GNUNET_CRYPTO_ecc_free()
 276  */
 277 gcry_mpi_point_t
 278 GNUNET_CRYPTO_ecc_dexp (struct GNUNET_CRYPTO_EccDlogContext *edc,
 279                         int val)
 280 {
 281   gcry_mpi_t fact;
 282   gcry_mpi_t n;
 283   gcry_mpi_point_t g;
 284   gcry_mpi_point_t r;
 285
 286   g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
 287   GNUNET_assert (NULL != g);
 288   fact = gcry_mpi_new (0);
 289   if (val < 0)
 290   {
 291     n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
 292     gcry_mpi_set_ui (fact, - val);
 293     gcry_mpi_sub (fact, n, fact);
 294     gcry_mpi_release (n);
 295   }
 296   else
 297   {
 298     gcry_mpi_set_ui (fact, val);
 299   }
 300   r = gcry_mpi_point_new (0);
 301   gcry_mpi_ec_mul (r, fact, g, edc->ctx);
 302   gcry_mpi_release (fact);
 303   gcry_mpi_point_release (g);
 304   return r;
 305 }
 306
 307
 308 /**
 309  * Multiply the generator g of the elliptic curve by @a val
 310  * to obtain the point on the curve representing @a val.
 311  *
 312  * @param edc calculation context for ECC operations
 313  * @param val (positive) value to encode into a point
 314  * @return representation of the value as an ECC point,
 315  *         must be freed using #GNUNET_CRYPTO_ecc_free()
 316  */
 317 gcry_mpi_point_t
 318 GNUNET_CRYPTO_ecc_dexp_mpi (struct GNUNET_CRYPTO_EccDlogContext *edc,
 319                             gcry_mpi_t val)
 320 {
 321   gcry_mpi_point_t g;
 322   gcry_mpi_point_t r;
 323
 324   g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
 325   GNUNET_assert (NULL != g);
 326   r = gcry_mpi_point_new (0);
 327   gcry_mpi_ec_mul (r, val, g, edc->ctx);
 328   gcry_mpi_point_release (g);
 329   return r;
 330 }
 331
 332
 333 /**
 334  * Add two points on the elliptic curve.
 335  *
 336  * @param edc calculation context for ECC operations
 337  * @param a some value
 338  * @param b some value
 339  * @return @a a + @a b, must be freed using #GNUNET_CRYPTO_ecc_free()
 340  */
 341 gcry_mpi_point_t
 342 GNUNET_CRYPTO_ecc_add (struct GNUNET_CRYPTO_EccDlogContext *edc,
 343                        gcry_mpi_point_t a,
 344                        gcry_mpi_point_t b)
 345 {
 346   gcry_mpi_point_t r;
 347
 348   r = gcry_mpi_point_new (0);
 349   gcry_mpi_ec_add (r, a, b, edc->ctx);
 350   return r;
 351 }
 352
 353
 354 /**
 355  * Obtain a random point on the curve and its
 356  * additive inverse. Both returned values
 357  * must be freed using #GNUNET_CRYPTO_ecc_free().
 358  *
 359  * @param edc calculation context for ECC operations
 360  * @param[out] r set to a random point on the curve
 361  * @param[out] r_inv set to the additive inverse of @a r
 362  */
 363 void
 364 GNUNET_CRYPTO_ecc_rnd (struct GNUNET_CRYPTO_EccDlogContext *edc,
 365                        gcry_mpi_point_t *r,
 366                        gcry_mpi_point_t *r_inv)
 367 {
 368   gcry_mpi_t fact;
 369   gcry_mpi_t n;
 370   gcry_mpi_point_t g;
 371
 372   fact = GNUNET_CRYPTO_ecc_random_mod_n (edc);
 373
 374   /* calculate 'r' */
 375   g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
 376   GNUNET_assert (NULL != g);
 377   *r = gcry_mpi_point_new (0);
 378   gcry_mpi_ec_mul (*r, fact, g, edc->ctx);
 379
 380   /* calculate 'r_inv' */
 381   n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
 382   gcry_mpi_sub (fact, n, fact); /* fact = n - fact = - fact */
 383   *r_inv = gcry_mpi_point_new (0);
 384   gcry_mpi_ec_mul (*r_inv, fact, g, edc->ctx);
 385
 386   gcry_mpi_release (n);
 387   gcry_mpi_release (fact);
 388   gcry_mpi_point_release (g);
 389 }
 390
 391
 392 /**
 393  * Free a point value returned by the API.
 394  *
 395  * @param p point to free
 396  */
 397 void
 398 GNUNET_CRYPTO_ecc_free (gcry_mpi_point_t p)
 399 {
 400   gcry_mpi_point_release (p);
 401 }
 402
 403
 404 /* end of crypto_ecc_dlog.c */
 405