path: root/src/util/crypto_ecc_dlog.c

/*
     This file is part of GNUnet.
     Copyright (C) 2012, 2013, 2015 GNUnet e.V.

     GNUnet is free software: you can redistribute it and/or modify it
     under the terms of the GNU General Public License as published
     by the Free Software Foundation, either version 3 of the License,
     or (at your option) any later version.

     GNUnet is distributed in the hope that it will be useful, but
     WITHOUT ANY WARRANTY; without even the implied warranty of
     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     Affero General Public License for more details.
*/

/**
 * @file util/crypto_ecc_dlog.c
 * @brief ECC addition and discreate logarithm for small values.
 *        Allows us to use ECC for computations as long as the
 *        result is relativey small.
 * @author Christian Grothoff
 */
#include "platform.h"
#include <gcrypt.h>
#include "gnunet_crypto_lib.h"
#include "gnunet_container_lib.h"


/**
 * Name of the curve we are using.  Note that we have hard-coded
 * structs that use 256 bits, so using a bigger curve will require
 * changes that break stuff badly.  The name of the curve given here
 * must be agreed by all peers and be supported by libgcrypt.
 */
#define CURVE "Ed25519"


/**
 *
 */
static void
extract_pk (gcry_mpi_point_t pt,
            gcry_ctx_t ctx,
            struct GNUNET_PeerIdentity *pid)
{
  gcry_mpi_t q_y;

  GNUNET_assert (0 == gcry_mpi_ec_set_point ("q", pt, ctx));
  q_y = gcry_mpi_ec_get_mpi ("q@eddsa", ctx, 0);
  GNUNET_assert (q_y);
  GNUNET_CRYPTO_mpi_print_unsigned (pid->public_key.q_y,
				    sizeof (pid->public_key.q_y),
                                    q_y);
  gcry_mpi_release (q_y);
}


/**
 * Internal structure used to cache pre-calculated values for DLOG calculation.
 */
struct GNUNET_CRYPTO_EccDlogContext
{
  /**
   * Maximum absolute value the calculation supports.
   */
  unsigned int max;

  /**
   * How much memory should we use (relates to the number of entries in the map).
   */
  unsigned int mem;

  /**
   * Map mapping points (here "interpreted" as EdDSA public keys) to
   * a "void * = long" which corresponds to the numeric value of the
   * point.  As NULL is used to represent "unknown", the actual value
   * represented by the entry in the map is the "long" minus @e max.
   */
  struct GNUNET_CONTAINER_MultiPeerMap *map;

  /**
   * Context to use for operations on the elliptic curve.
   */
  gcry_ctx_t ctx;

};


/**
 * Convert point value to binary representation.
 *
 * @param edc calculation context for ECC operations
 * @param point computational point representation
 * @param[out] bin binary point representation
 */
void
GNUNET_CRYPTO_ecc_point_to_bin (struct GNUNET_CRYPTO_EccDlogContext *edc,
                                gcry_mpi_point_t point,
                                struct GNUNET_CRYPTO_EccPoint *bin)
{
  gcry_mpi_t q_y;

  GNUNET_assert (0 == gcry_mpi_ec_set_point ("q", point, edc->ctx));
  q_y = gcry_mpi_ec_get_mpi ("q@eddsa", edc->ctx, 0);
  GNUNET_assert (q_y);
  GNUNET_CRYPTO_mpi_print_unsigned (bin->q_y,
				    sizeof (bin->q_y),
                                    q_y);
  gcry_mpi_release (q_y);
}


/**
 * Convert binary representation of a point to computational representation.
 *
 * @param edc calculation context for ECC operations
 * @param bin binary point representation
 * @return computational representation
 */
gcry_mpi_point_t
GNUNET_CRYPTO_ecc_bin_to_point (struct GNUNET_CRYPTO_EccDlogContext *edc,
                                const struct GNUNET_CRYPTO_EccPoint *bin)
{
  gcry_sexp_t pub_sexpr;
  gcry_ctx_t ctx;
  gcry_mpi_point_t q;

  (void) edc;
  if (0 != gcry_sexp_build (&pub_sexpr, NULL,
                            "(public-key(ecc(curve " CURVE ")(q %b)))",
                            (int) sizeof (bin->q_y),
                            bin->q_y))
  {
    GNUNET_break (0);
    return NULL;
  }
  GNUNET_assert (0 == gcry_mpi_ec_new (&ctx, pub_sexpr, NULL));
  gcry_sexp_release (pub_sexpr);
  q = gcry_mpi_ec_get_point ("q", ctx, 0);
  gcry_ctx_release (ctx);
  return q;
}


/**
 * Do pre-calculation for ECC discrete logarithm for small factors.
 *
 * @param max maximum value the factor can be
 * @param mem memory to use (should be smaller than @a max), must not be zero.
 * @return NULL on error
 */
struct GNUNET_CRYPTO_EccDlogContext *
GNUNET_CRYPTO_ecc_dlog_prepare (unsigned int max,
				unsigned int mem)
{
  struct GNUNET_CRYPTO_EccDlogContext *edc;
  unsigned int K = ((max + (mem-1)) / mem);
  gcry_mpi_point_t g;
  struct GNUNET_PeerIdentity key;
  gcry_mpi_point_t gKi;
  gcry_mpi_t fact;
  gcry_mpi_t n;
  unsigned int i;

  GNUNET_assert (max < INT32_MAX);
  edc = GNUNET_new (struct GNUNET_CRYPTO_EccDlogContext);
  edc->max = max;
  edc->mem = mem;

  edc->map = GNUNET_CONTAINER_multipeermap_create (mem * 2,
						   GNUNET_NO);

  GNUNET_assert (0 == gcry_mpi_ec_new (&edc->ctx,
				       NULL,
				       CURVE));
  g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
  GNUNET_assert (NULL != g);
  fact = gcry_mpi_new (0);
  gKi = gcry_mpi_point_new (0);
  for (i=0;i<=mem;i++)
  {
    gcry_mpi_set_ui (fact, i * K);
    gcry_mpi_ec_mul (gKi, fact, g, edc->ctx);
    extract_pk (gKi, edc->ctx, &key);
    GNUNET_assert (GNUNET_OK ==
		   GNUNET_CONTAINER_multipeermap_put (edc->map,
						      &key,
						      (void*) (long) i + max,
						      GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
  }
  /* negative values */
  n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
  for (i=1;i<mem;i++)
  {
    gcry_mpi_set_ui (fact, i * K);
    gcry_mpi_sub (fact, n, fact);
    gcry_mpi_ec_mul (gKi, fact, g, edc->ctx);
    extract_pk (gKi, edc->ctx, &key);
    GNUNET_assert (GNUNET_OK ==
		   GNUNET_CONTAINER_multipeermap_put (edc->map,
						      &key,
						      (void*) (long) max - i,
						      GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
  }
  gcry_mpi_release (fact);
  gcry_mpi_release (n);
  gcry_mpi_point_release (gKi);
  gcry_mpi_point_release (g);
  return edc;
}


/**
 * Calculate ECC discrete logarithm for small factors.
 *
 * @param edc precalculated values, determine range of factors
 * @param input point on the curve to factor
 * @return INT_MAX if dlog failed, otherwise the factor
 */
int
GNUNET_CRYPTO_ecc_dlog (struct GNUNET_CRYPTO_EccDlogContext *edc,
			gcry_mpi_point_t input)
{
  unsigned int K = ((edc->max + (edc->mem-1)) / edc->mem);
  gcry_mpi_point_t g;
  struct GNUNET_PeerIdentity key;
  gcry_mpi_point_t q;
  unsigned int i;
  int res;
  void *retp;

  g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
  GNUNET_assert (NULL != g);
  q = gcry_mpi_point_new (0);

  res = INT_MAX;
  for (i=0;i<=edc->max/edc->mem;i++)
  {
    if (0 == i)
      extract_pk (input, edc->ctx, &key);
    else
      extract_pk (q, edc->ctx, &key);
    retp = GNUNET_CONTAINER_multipeermap_get (edc->map,
					      &key);
    if (NULL != retp)
    {
      res = (((long) retp) - edc->max) * K - i;
      /* we continue the loop here to make the implementation
	 "constant-time". If we do not care about this, we could just
	 'break' here and do fewer operations... */
    }
    if (i == edc->max/edc->mem)
      break;
    /* q = q + g */
    if (0 == i)
      gcry_mpi_ec_add (q, input, g, edc->ctx);
    else
      gcry_mpi_ec_add (q, q, g, edc->ctx);
  }
  gcry_mpi_point_release (g);
  gcry_mpi_point_release (q);

  return res;
}


/**
 * Generate a random value mod n.
 *
 * @param edc ECC context
 * @return random value mod n.
 */
gcry_mpi_t
GNUNET_CRYPTO_ecc_random_mod_n (struct GNUNET_CRYPTO_EccDlogContext *edc)
{
  gcry_mpi_t n;
  unsigned int highbit;
  gcry_mpi_t r;

  n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);

  /* check public key for number of bits, bail out if key is all zeros */
  highbit = 256; /* Curve25519 */
  while ( (! gcry_mpi_test_bit (n, highbit)) &&
          (0 != highbit) )
    highbit--;
  GNUNET_assert (0 != highbit);
  /* generate fact < n (without bias) */
  GNUNET_assert (NULL != (r = gcry_mpi_new (0)));
  do {
    gcry_mpi_randomize (r,
			highbit + 1,
			GCRY_STRONG_RANDOM);
  }
  while (gcry_mpi_cmp (r, n) >= 0);
  gcry_mpi_release (n);
  return r;
}


/**
 * Release precalculated values.
 *
 * @param edc dlog context
 */
void
GNUNET_CRYPTO_ecc_dlog_release (struct GNUNET_CRYPTO_EccDlogContext *edc)
{
  gcry_ctx_release (edc->ctx);
  GNUNET_CONTAINER_multipeermap_destroy (edc->map);
  GNUNET_free (edc);
}


/**
 * Multiply the generator g of the elliptic curve by @a val
 * to obtain the point on the curve representing @a val.
 * Afterwards, point addition will correspond to integer
 * addition.  #GNUNET_CRYPTO_ecc_dlog() can be used to
 * convert a point back to an integer (as long as the
 * integer is smaller than the MAX of the @a edc context).
 *
 * @param edc calculation context for ECC operations
 * @param val value to encode into a point
 * @return representation of the value as an ECC point,
 *         must be freed using #GNUNET_CRYPTO_ecc_free()
 */
gcry_mpi_point_t
GNUNET_CRYPTO_ecc_dexp (struct GNUNET_CRYPTO_EccDlogContext *edc,
			int val)
{
  gcry_mpi_t fact;
  gcry_mpi_t n;
  gcry_mpi_point_t g;
  gcry_mpi_point_t r;

  g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
  GNUNET_assert (NULL != g);
  fact = gcry_mpi_new (0);
  if (val < 0)
  {
    n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
    gcry_mpi_set_ui (fact, - val);
    gcry_mpi_sub (fact, n, fact);
    gcry_mpi_release (n);
  }
  else
  {
    gcry_mpi_set_ui (fact, val);
  }
  r = gcry_mpi_point_new (0);
  gcry_mpi_ec_mul (r, fact, g, edc->ctx);
  gcry_mpi_release (fact);
  gcry_mpi_point_release (g);
  return r;
}


/**
 * Multiply the generator g of the elliptic curve by @a val
 * to obtain the point on the curve representing @a val.
 *
 * @param edc calculation context for ECC operations
 * @param val (positive) value to encode into a point
 * @return representation of the value as an ECC point,
 *         must be freed using #GNUNET_CRYPTO_ecc_free()
 */
gcry_mpi_point_t
GNUNET_CRYPTO_ecc_dexp_mpi (struct GNUNET_CRYPTO_EccDlogContext *edc,
			    gcry_mpi_t val)
{
  gcry_mpi_point_t g;
  gcry_mpi_point_t r;

  g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
  GNUNET_assert (NULL != g);
  r = gcry_mpi_point_new (0);
  gcry_mpi_ec_mul (r, val, g, edc->ctx);
  gcry_mpi_point_release (g);
  return r;
}


/**
 * Add two points on the elliptic curve.
 *
 * @param edc calculation context for ECC operations
 * @param a some value
 * @param b some value
 * @return @a a + @a b, must be freed using #GNUNET_CRYPTO_ecc_free()
 */
gcry_mpi_point_t
GNUNET_CRYPTO_ecc_add (struct GNUNET_CRYPTO_EccDlogContext *edc,
		       gcry_mpi_point_t a,
		       gcry_mpi_point_t b)
{
  gcry_mpi_point_t r;

  r = gcry_mpi_point_new (0);
  gcry_mpi_ec_add (r, a, b, edc->ctx);
  return r;
}


/**
 * Multiply the point @a p on the elliptic curve by @a val.
 *
 * @param edc calculation context for ECC operations
 * @param p point to multiply
 * @param val (positive) value to encode into a point
 * @return representation of the value as an ECC point,
 *         must be freed using #GNUNET_CRYPTO_ecc_free()
 */
gcry_mpi_point_t
GNUNET_CRYPTO_ecc_pmul_mpi (struct GNUNET_CRYPTO_EccDlogContext *edc,
                            gcry_mpi_point_t p,
			    gcry_mpi_t val)
{
  gcry_mpi_point_t r;

  r = gcry_mpi_point_new (0);
  gcry_mpi_ec_mul (r, val, p, edc->ctx);
  return r;
}


/**
 * Obtain a random point on the curve and its
 * additive inverse. Both returned values
 * must be freed using #GNUNET_CRYPTO_ecc_free().
 *
 * @param edc calculation context for ECC operations
 * @param[out] r set to a random point on the curve
 * @param[out] r_inv set to the additive inverse of @a r
 */
void
GNUNET_CRYPTO_ecc_rnd (struct GNUNET_CRYPTO_EccDlogContext *edc,
		       gcry_mpi_point_t *r,
		       gcry_mpi_point_t *r_inv)
{
  gcry_mpi_t fact;
  gcry_mpi_t n;
  gcry_mpi_point_t g;

  fact = GNUNET_CRYPTO_ecc_random_mod_n (edc);

  /* calculate 'r' */
  g = gcry_mpi_ec_get_point ("g", edc->ctx, 0);
  GNUNET_assert (NULL != g);
  *r = gcry_mpi_point_new (0);
  gcry_mpi_ec_mul (*r, fact, g, edc->ctx);

  /* calculate 'r_inv' */
  n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
  gcry_mpi_sub (fact, n, fact); /* fact = n - fact = - fact */
  *r_inv = gcry_mpi_point_new (0);
  gcry_mpi_ec_mul (*r_inv, fact, g, edc->ctx);

  gcry_mpi_release (n);
  gcry_mpi_release (fact);
  gcry_mpi_point_release (g);
}


/**
 * Obtain a random scalar for point multiplication on the curve and
 * its multiplicative inverse.
 *
 * @param edc calculation context for ECC operations
 * @param[out] r set to a random scalar on the curve
 * @param[out] r_inv set to the multiplicative inverse of @a r
 */
void
GNUNET_CRYPTO_ecc_rnd_mpi (struct GNUNET_CRYPTO_EccDlogContext *edc,
                           gcry_mpi_t *r,
                           gcry_mpi_t *r_inv)
{
  gcry_mpi_t n;

  *r = GNUNET_CRYPTO_ecc_random_mod_n (edc);
  /* r_inv = n - r = - r */
  *r_inv = gcry_mpi_new (0);
  n = gcry_mpi_ec_get_mpi ("n", edc->ctx, 1);
  gcry_mpi_sub (*r_inv, n, *r);
}


/**
 * Free a point value returned by the API.
 *
 * @param p point to free
 */
void
GNUNET_CRYPTO_ecc_free (gcry_mpi_point_t p)
{
  gcry_mpi_point_release (p);
}


/* end of crypto_ecc_dlog.c */