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 discreate logarithm for small values
  24  * @author Christian Grothoff
  25  *
  26  * TODO:
  27  * - support negative factors
  28  */
  29 #include "platform.h"
  30 #include <gcrypt.h>
  31 #include "gnunet_crypto_lib.h"
  32 #include "gnunet_container_lib.h"
  33
  34
  35 /**
  36  * Name of the curve we are using.  Note that we have hard-coded
  37  * structs that use 256 bits, so using a bigger curve will require
  38  * changes that break stuff badly.  The name of the curve given here
  39  * must be agreed by all peers and be supported by libgcrypt.
  40  */
  41 #define CURVE "Ed25519"
  42
  43
  44 /**
  45  *
  46  */
  47 static void
  48 extract_pk (gcry_mpi_point_t pt,
  49               gcry_ctx_t ctx,
  50               struct GNUNET_PeerIdentity *pid)
  51 {
  52   gcry_mpi_t q_y;
  53
  54   GNUNET_assert (0 == gcry_mpi_ec_set_point ("q", pt, ctx));
  55   q_y = gcry_mpi_ec_get_mpi ("q@eddsa", ctx, 0);
  56   GNUNET_assert (q_y);
  57   GNUNET_CRYPTO_mpi_print_unsigned (pid->public_key.q_y,
  58                                     sizeof (pid->public_key.q_y),
  59                                     q_y);
  60   gcry_mpi_release (q_y);
  61 }
  62
  63
  64 /**
  65  * Internal structure used to cache pre-calculated values for DLOG calculation.
  66  */
  67 struct GNUNET_CRYPTO_EccDlogContext
  68 {
  69   unsigned int max;
  70   unsigned int mem;
  71   struct GNUNET_CONTAINER_MultiPeerMap *map;
  72   gcry_ctx_t ctx;
  73
  74 };
  75
  76
  77 /**
  78  * Do pre-calculation for ECC discrete logarithm for small factors.
  79  *
  80  * @param max maximum value the factor can be
  81  * @param mem memory to use (should be smaller than @a max), must not be zero.
  82  * @return @a max if dlog failed, otherwise the factor
  83  */
  84 struct GNUNET_CRYPTO_EccDlogContext *
  85 GNUNET_CRYPTO_ecc_dlog_prepare (unsigned int max,
  86                                 unsigned int mem)
  87 {
  88   struct GNUNET_CRYPTO_EccDlogContext *edc;
  89   unsigned int K = ((max + (mem-1)) / mem);
  90   gcry_mpi_point_t g;
  91   struct GNUNET_PeerIdentity key;
  92   gcry_mpi_point_t gKi;
  93   gcry_mpi_t fact;
  94   unsigned int i;
  95
  96   edc = GNUNET_new (struct GNUNET_CRYPTO_EccDlogContext);
  97   edc->max = max;
  98   edc->mem = mem;
  99
 100   edc->map = GNUNET_CONTAINER_multipeermap_create (mem * 2,
 101                                                    GNUNET_NO);
 102
 103   GNUNET_assert (0 == gcry_mpi_ec_new (&edc->ctx,
 104                                        NULL,
 105                                        CURVE));
 106   g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
 107   GNUNET_assert (NULL != g);
 108   fact = gcry_mpi_new (0);
 109   gKi = gcry_mpi_point_new (0);
 110   for (i=0;i<=mem;i++)
 111   {
 112     gcry_mpi_set_ui (fact, i * K);
 113     gcry_mpi_ec_mul (gKi, fact, g, edc->ctx);
 114     extract_pk (gKi, edc->ctx, &key);
 115     GNUNET_assert (GNUNET_OK ==
 116                    GNUNET_CONTAINER_multipeermap_put (edc->map,
 117                                                       &key,
 118                                                       (void*) (long) i + 1,
 119                                                       GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
 120   }
 121   gcry_mpi_release (fact);
 122   gcry_mpi_point_release (gKi);
 123   gcry_mpi_point_release (g);
 124   return edc;
 125 }
 126
 127
 128 /**
 129  * Calculate ECC discrete logarithm for small factors.
 130  *
 131  * @param edc precalculated values, determine range of factors
 132  * @param input point on the curve to factor
 133  * @return `edc->max` if dlog failed, otherwise the factor
 134  */
 135 unsigned int
 136 GNUNET_CRYPTO_ecc_dlog (struct GNUNET_CRYPTO_EccDlogContext *edc,
 137                         gcry_mpi_point_t input)
 138 {
 139   unsigned int K = ((edc->max + (edc->mem-1)) / edc->mem);
 140   gcry_mpi_point_t g;
 141   struct GNUNET_PeerIdentity key;
 142   gcry_mpi_point_t q;
 143   unsigned int i;
 144   unsigned int res;
 145   void *retp;
 146
 147   g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
 148   GNUNET_assert (NULL != g);
 149   q = gcry_mpi_point_new (0);
 150
 151   res = edc->max;
 152   for (i=0;i<=edc->max/edc->mem;i++)
 153   {
 154     if (0 == i)
 155       extract_pk (input, edc->ctx, &key);
 156     else
 157       extract_pk (q, edc->ctx, &key);
 158     retp = GNUNET_CONTAINER_multipeermap_get (edc->map,
 159                                               &key);
 160     if (NULL != retp)
 161     {
 162       res = (((long) retp) - 1) * K - i;
 163       fprintf (stderr,
 164                "Got DLOG %u\n",
 165                res);
 166     }
 167     if (i == edc->max/edc->mem)
 168       break;
 169     /* q = q + g */
 170     if (0 == i)
 171       gcry_mpi_ec_add (q, input, g, edc->ctx);
 172     else
 173       gcry_mpi_ec_add (q, q, g, edc->ctx);
 174   }
 175   gcry_mpi_point_release (g);
 176   gcry_mpi_point_release (q);
 177
 178   return res;
 179 }
 180
 181
 182 /**
 183  * Release precalculated values.
 184  *
 185  * @param edc dlog context
 186  */
 187 void
 188 GNUNET_CRYPTO_ecc_dlog_release (struct GNUNET_CRYPTO_EccDlogContext *edc)
 189 {
 190   gcry_ctx_release (edc->ctx);
 191   GNUNET_CONTAINER_multipeermap_destroy (edc->map);
 192   GNUNET_free (edc);
 193 }
 194
 195 /* end of crypto_ecc_dlog.c */
 196