/*
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 Affero 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.
You should have received a copy of the GNU Affero General Public License
along with this program. If not, see .
SPDX-License-Identifier: AGPL3.0-or-later
*/
/**
* @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
#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 */