GNUnet  0.11.x
Data Structures | Functions
crypto_ecc_dlog.c File Reference

ECC addition and discreate logarithm for small values. More...

#include "platform.h"
#include <gcrypt.h>
#include "gnunet_crypto_lib.h"
#include "gnunet_container_lib.h"
Include dependency graph for crypto_ecc_dlog.c:

Go to the source code of this file.

Data Structures

struct  GNUNET_CRYPTO_EccDlogContext
 Internal structure used to cache pre-calculated values for DLOG calculation. More...
 

Functions

struct GNUNET_CRYPTO_EccDlogContextGNUNET_CRYPTO_ecc_dlog_prepare (unsigned int max, unsigned int mem)
 Do pre-calculation for ECC discrete logarithm for small factors. More...
 
int GNUNET_CRYPTO_ecc_dlog (struct GNUNET_CRYPTO_EccDlogContext *edc, const struct GNUNET_CRYPTO_EccPoint *input)
 Calculate ECC discrete logarithm for small factors. More...
 
void GNUNET_CRYPTO_ecc_random_mod_n (struct GNUNET_CRYPTO_EccScalar *r)
 Generate a random value mod n. More...
 
void GNUNET_CRYPTO_ecc_dlog_release (struct GNUNET_CRYPTO_EccDlogContext *edc)
 Release precalculated values. More...
 
void GNUNET_CRYPTO_ecc_dexp (int val, struct GNUNET_CRYPTO_EccPoint *r)
 Multiply the generator g of the elliptic curve by val to obtain the point on the curve representing val. More...
 
enum GNUNET_GenericReturnValue GNUNET_CRYPTO_ecc_dexp_mpi (const struct GNUNET_CRYPTO_EccScalar *val, struct GNUNET_CRYPTO_EccPoint *r)
 Multiply the generator g of the elliptic curve by val to obtain the point on the curve representing val. More...
 
enum GNUNET_GenericReturnValue GNUNET_CRYPTO_ecc_add (const struct GNUNET_CRYPTO_EccPoint *a, const struct GNUNET_CRYPTO_EccPoint *b, struct GNUNET_CRYPTO_EccPoint *r)
 Add two points on the elliptic curve. More...
 
enum GNUNET_GenericReturnValue GNUNET_CRYPTO_ecc_pmul_mpi (const struct GNUNET_CRYPTO_EccPoint *p, const struct GNUNET_CRYPTO_EccScalar *val, struct GNUNET_CRYPTO_EccPoint *r)
 Multiply the point p on the elliptic curve by val. More...
 
enum GNUNET_GenericReturnValue GNUNET_CRYPTO_ecc_rnd (struct GNUNET_CRYPTO_EccPoint *r, struct GNUNET_CRYPTO_EccPoint *r_inv)
 Obtain a random point on the curve and its additive inverse. More...
 
void GNUNET_CRYPTO_ecc_rnd_mpi (struct GNUNET_CRYPTO_EccScalar *r, struct GNUNET_CRYPTO_EccScalar *r_neg)
 Obtain a random scalar for point multiplication on the curve and its additive inverse. More...
 
void GNUNET_CRYPTO_ecc_scalar_from_int (int64_t val, struct GNUNET_CRYPTO_EccScalar *r)
 Create a scalar from int value. More...
 

Detailed Description

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

Definition in file crypto_ecc_dlog.c.

Function Documentation

◆ GNUNET_CRYPTO_ecc_dlog_prepare()

struct GNUNET_CRYPTO_EccDlogContext* GNUNET_CRYPTO_ecc_dlog_prepare ( unsigned int  max,
unsigned int  mem 
)

Do pre-calculation for ECC discrete logarithm for small factors.

Parameters
maxmaximum value the factor can be
memmemory to use (should be smaller than max), must not be zero.
Returns
NULL on error

Definition at line 65 of file crypto_ecc_dlog.c.

References edc, GNUNET_assert, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY, GNUNET_CONTAINER_multipeermap_create(), GNUNET_CONTAINER_multipeermap_put(), GNUNET_CRYPTO_ecc_scalar_from_int(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_i2s(), GNUNET_log, GNUNET_new, GNUNET_NO, GNUNET_OK, consensus-simulation::int, GNUNET_CRYPTO_EccDlogContext::map, GNUNET_CRYPTO_EccDlogContext::max, GNUNET_CRYPTO_EccDlogContext::mem, and GNUNET_CRYPTO_EccScalar::v.

Referenced by run().

67 {
69  int K = ((max + (mem - 1)) / mem);
70 
71  GNUNET_assert (max < INT32_MAX);
73  edc->max = max;
74  edc->mem = mem;
76  GNUNET_NO);
77  for (int i = -(int) mem; i <= (int) mem; i++)
78  {
79  struct GNUNET_CRYPTO_EccScalar Ki;
80  struct GNUNET_PeerIdentity key;
81 
83  &Ki);
84  if (0 == i) /* libsodium does not like to multiply with zero */
86  0 ==
87  crypto_core_ed25519_sub ((unsigned char *) &key,
88  (unsigned char *) &key,
89  (unsigned char *) &key));
90  else
92  0 ==
93  crypto_scalarmult_ed25519_base_noclamp ((unsigned char*) &key,
94  Ki.v));
96  "K*i: %d (mem=%u, i=%d) => %s\n",
97  K * i,
98  mem,
99  i,
100  GNUNET_i2s (&key));
103  &key,
104  (void *) (long) i + max,
106  }
107  return edc;
108 }
void GNUNET_CRYPTO_ecc_scalar_from_int(int64_t val, struct GNUNET_CRYPTO_EccScalar *r)
Create a scalar from int value.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
struct GNUNET_CONTAINER_MultiPeerMap * map
Map mapping points (here "interpreted" as EdDSA public keys) to a "void * = long" which corresponds t...
#define GNUNET_new(type)
Allocate a struct or union of the given type.
struct GNUNET_CONTAINER_MultiPeerMap * GNUNET_CONTAINER_multipeermap_create(unsigned int len, int do_not_copy_keys)
Create a multi peer map (hash map for public keys of peers).
#define max(x, y)
static struct GNUNET_CRYPTO_EccDlogContext * edc
Context for DLOG operations on a curve.
There must only be one value per key; storing a value should fail if a value under the same key alrea...
struct GNUNET_HashCode key
The key used in the DHT.
int GNUNET_CONTAINER_multipeermap_put(struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt)
Store a key-value pair in the map.
The identity of the host (wraps the signing key of the peer).
A ECC scalar for use in point multiplications.
#define GNUNET_log(kind,...)
Internal structure used to cache pre-calculated values for DLOG calculation.
const char * GNUNET_i2s(const struct GNUNET_PeerIdentity *pid)
Convert a peer identity to a string (for printing debug messages).
unsigned int max
Maximum absolute value the calculation supports.
unsigned int mem
How much memory should we use (relates to the number of entries in the map).
Here is the call graph for this function:
Here is the caller graph for this function:

◆ GNUNET_CRYPTO_ecc_dlog()

int GNUNET_CRYPTO_ecc_dlog ( struct GNUNET_CRYPTO_EccDlogContext edc,
const struct GNUNET_CRYPTO_EccPoint input 
)

Calculate ECC discrete logarithm for small factors.

Opposite of GNUNET_CRYPTO_ecc_dexp().

Parameters
dlcprecalculated values, determine range of factors
inputpoint on the curve to factor
Returns
INT_MAX if dlog failed, otherwise the factor

Definition at line 112 of file crypto_ecc_dlog.c.

References GNUNET_assert, GNUNET_CONTAINER_multipeermap_get(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_i2s(), GNUNET_log, INT_MAX, GNUNET_CRYPTO_EccDlogContext::map, GNUNET_CRYPTO_EccDlogContext::max, GNUNET_CRYPTO_EccDlogContext::mem, res, GNUNET_CRYPTO_EccPoint::v, and GNUNET_CRYPTO_EccScalar::v.

Referenced by handle_bobs_cryptodata_message().

114 {
115  unsigned int K = ((edc->max + (edc->mem - 1)) / edc->mem);
116  int res;
117  struct GNUNET_CRYPTO_EccPoint g;
118  struct GNUNET_CRYPTO_EccPoint q;
119  struct GNUNET_CRYPTO_EccPoint nq;
120 
121  {
122  struct GNUNET_CRYPTO_EccScalar fact;
123 
124  memset (&fact,
125  0,
126  sizeof (fact));
127  sodium_increment (fact.v,
128  sizeof (fact.v));
129  GNUNET_assert (0 ==
130  crypto_scalarmult_ed25519_base_noclamp (g.v,
131  fact.v));
132  }
133  /* make compiler happy: initialize q and nq, technically not needed! */
134  memset (&q,
135  0,
136  sizeof (q));
137  memset (&nq,
138  0,
139  sizeof (nq));
140  res = INT_MAX;
141  for (unsigned int i = 0; i <= edc->max / edc->mem; i++)
142  {
143  struct GNUNET_PeerIdentity key;
144  void *retp;
145 
146  GNUNET_assert (sizeof (key) == crypto_scalarmult_BYTES);
147  if (0 == i)
148  {
149  memcpy (&key,
150  input,
151  sizeof (key));
152  }
153  else
154  {
155  memcpy (&key,
156  &q,
157  sizeof (key));
158  }
160  "Trying offset i=%u): %s\n",
161  i,
162  GNUNET_i2s (&key));
164  &key);
165  if (NULL != retp)
166  {
167  res = (((long) retp) - edc->max) * K - i;
168  /* we continue the loop here to make the implementation
169  "constant-time". If we do not care about this, we could just
170  'break' here and do fewer operations... */
171  }
172  if (i == edc->max / edc->mem)
173  break;
174  /* q = q + g */
175  if (0 == i)
176  {
177  GNUNET_assert (0 ==
178  crypto_core_ed25519_add (q.v,
179  input->v,
180  g.v));
181  }
182  else
183  {
184  GNUNET_assert (0 ==
185  crypto_core_ed25519_add (q.v,
186  q.v,
187  g.v));
188  }
189  }
190  return res;
191 }
Point on a curve (always for Curve25519) encoded in a format suitable for network transmission (ECDH)...
unsigned char v[256/8]
Q consists of an x- and a y-value, each mod p (256 bits), given here in affine coordinates and Ed2551...
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
struct GNUNET_CONTAINER_MultiPeerMap * map
Map mapping points (here "interpreted" as EdDSA public keys) to a "void * = long" which corresponds t...
#define INT_MAX
static int res
static struct GNUNET_REVOCATION_Query * q
Handle for revocation query.
struct GNUNET_HashCode key
The key used in the DHT.
The identity of the host (wraps the signing key of the peer).
A ECC scalar for use in point multiplications.
void * GNUNET_CONTAINER_multipeermap_get(const struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key)
Given a key find a value in the map matching the key.
#define GNUNET_log(kind,...)
const char * GNUNET_i2s(const struct GNUNET_PeerIdentity *pid)
Convert a peer identity to a string (for printing debug messages).
unsigned int max
Maximum absolute value the calculation supports.
unsigned int mem
How much memory should we use (relates to the number of entries in the map).
Here is the call graph for this function:
Here is the caller graph for this function:

◆ GNUNET_CRYPTO_ecc_random_mod_n()

void GNUNET_CRYPTO_ecc_random_mod_n ( struct GNUNET_CRYPTO_EccScalar r)

Generate a random value mod n.

Parameters
[out]rrandom value mod n.

Definition at line 195 of file crypto_ecc_dlog.c.

References GNUNET_CRYPTO_EccScalar::v.

Referenced by GNUNET_CRYPTO_ecc_rnd(), GNUNET_CRYPTO_ecc_rnd_mpi(), and send_alices_cryptodata_message().

196 {
197  crypto_core_ed25519_scalar_random (r->v);
198 }
unsigned char v[256/8]
Here is the caller graph for this function:

◆ GNUNET_CRYPTO_ecc_dlog_release()

void GNUNET_CRYPTO_ecc_dlog_release ( struct GNUNET_CRYPTO_EccDlogContext dlc)

Release precalculated values.

Parameters
dlcdlog context

Definition at line 202 of file crypto_ecc_dlog.c.

References GNUNET_CONTAINER_multipeermap_destroy(), GNUNET_free, and GNUNET_CRYPTO_EccDlogContext::map.

Referenced by shutdown_task().

203 {
205  GNUNET_free (edc);
206 }
struct GNUNET_CONTAINER_MultiPeerMap * map
Map mapping points (here "interpreted" as EdDSA public keys) to a "void * = long" which corresponds t...
void GNUNET_CONTAINER_multipeermap_destroy(struct GNUNET_CONTAINER_MultiPeerMap *map)
Destroy a hash map.
#define GNUNET_free(ptr)
Wrapper around free.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ GNUNET_CRYPTO_ecc_dexp()

void GNUNET_CRYPTO_ecc_dexp ( int  val,
struct GNUNET_CRYPTO_EccPoint r 
)

Multiply the generator g of the elliptic curve by val to obtain the point on the curve representing 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 edc context).

Parameters
valvalue to encode into a point
rwhere to write the point (must be allocated)

Definition at line 210 of file crypto_ecc_dlog.c.

References GNUNET_CRYPTO_ecc_scalar_from_int(), GNUNET_CRYPTO_EccPoint::v, and GNUNET_CRYPTO_EccScalar::v.

212 {
213  struct GNUNET_CRYPTO_EccScalar fact;
214 
216  &fact);
217  crypto_scalarmult_ed25519_base_noclamp (r->v,
218  fact.v);
219 }
void GNUNET_CRYPTO_ecc_scalar_from_int(int64_t val, struct GNUNET_CRYPTO_EccScalar *r)
Create a scalar from int value.
unsigned char v[256/8]
Q consists of an x- and a y-value, each mod p (256 bits), given here in affine coordinates and Ed2551...
A ECC scalar for use in point multiplications.
Here is the call graph for this function:

◆ GNUNET_CRYPTO_ecc_dexp_mpi()

enum GNUNET_GenericReturnValue GNUNET_CRYPTO_ecc_dexp_mpi ( const struct GNUNET_CRYPTO_EccScalar val,
struct GNUNET_CRYPTO_EccPoint r 
)

Multiply the generator g of the elliptic curve by val to obtain the point on the curve representing val.

Parameters
val(positive) value to encode into a point
rwhere to write the point (must be allocated)
Returns
GNUNET_OK on success.

Definition at line 223 of file crypto_ecc_dlog.c.

References GNUNET_OK, GNUNET_SYSERR, GNUNET_CRYPTO_EccPoint::v, and GNUNET_CRYPTO_EccScalar::v.

Referenced by send_alices_cryptodata_message().

225 {
226  if (0 ==
227  crypto_scalarmult_ed25519_base_noclamp (r->v,
228  val->v))
229  return GNUNET_OK;
230  return GNUNET_SYSERR;
231 }
unsigned char v[256/8]
Q consists of an x- and a y-value, each mod p (256 bits), given here in affine coordinates and Ed2551...
unsigned char v[256/8]
Here is the caller graph for this function:

◆ GNUNET_CRYPTO_ecc_add()

enum GNUNET_GenericReturnValue GNUNET_CRYPTO_ecc_add ( const struct GNUNET_CRYPTO_EccPoint a,
const struct GNUNET_CRYPTO_EccPoint b,
struct GNUNET_CRYPTO_EccPoint r 
)

Add two points on the elliptic curve.

Parameters
asome value
bsome value
rwhere to write the point (must be allocated)
Returns
GNUNET_OK on success.

Definition at line 235 of file crypto_ecc_dlog.c.

References GNUNET_OK, GNUNET_SYSERR, and GNUNET_CRYPTO_EccPoint::v.

Referenced by handle_alices_cryptodata_message(), and handle_bobs_cryptodata_message().

238 {
239  if (0 ==
240  crypto_core_ed25519_add (r->v,
241  a->v,
242  b->v))
243  return GNUNET_OK;
244  return GNUNET_SYSERR;
245 }
unsigned char v[256/8]
Q consists of an x- and a y-value, each mod p (256 bits), given here in affine coordinates and Ed2551...
Here is the caller graph for this function:

◆ GNUNET_CRYPTO_ecc_pmul_mpi()

enum GNUNET_GenericReturnValue GNUNET_CRYPTO_ecc_pmul_mpi ( const struct GNUNET_CRYPTO_EccPoint p,
const struct GNUNET_CRYPTO_EccScalar val,
struct GNUNET_CRYPTO_EccPoint r 
)

Multiply the point p on the elliptic curve by val.

Parameters
ppoint to multiply
val(positive) value to encode into a point
rwhere to write the point (must be allocated)
Returns
GNUNET_OK on success.

Definition at line 249 of file crypto_ecc_dlog.c.

References GNUNET_OK, GNUNET_SYSERR, GNUNET_CRYPTO_EccPoint::v, and GNUNET_CRYPTO_EccScalar::v.

Referenced by handle_alices_cryptodata_message(), and handle_bobs_cryptodata_message().

252 {
253  if (0 ==
254  crypto_scalarmult_ed25519_noclamp (r->v,
255  val->v,
256  p->v))
257  return GNUNET_OK;
258  return GNUNET_SYSERR;
259 }
unsigned char v[256/8]
Q consists of an x- and a y-value, each mod p (256 bits), given here in affine coordinates and Ed2551...
unsigned char v[256/8]
Here is the caller graph for this function:

◆ GNUNET_CRYPTO_ecc_rnd()

enum GNUNET_GenericReturnValue GNUNET_CRYPTO_ecc_rnd ( struct GNUNET_CRYPTO_EccPoint r,
struct GNUNET_CRYPTO_EccPoint r_inv 
)

Obtain a random point on the curve and its additive inverse.

Parameters
[out]rset to a random point on the curve
[out]r_invset to the additive inverse of r
Returns
GNUNET_OK on success.

Definition at line 263 of file crypto_ecc_dlog.c.

References GNUNET_CRYPTO_ecc_random_mod_n(), GNUNET_OK, GNUNET_SYSERR, GNUNET_CRYPTO_EccPoint::v, and GNUNET_CRYPTO_EccScalar::v.

265 {
266  struct GNUNET_CRYPTO_EccScalar s;
267  unsigned char inv_s[crypto_scalarmult_ed25519_SCALARBYTES];
268 
270  if (0 !=
271  crypto_scalarmult_ed25519_base_noclamp (r->v,
272  s.v))
273  return GNUNET_SYSERR;
274  crypto_core_ed25519_scalar_negate (inv_s,
275  s.v);
276  if (0 !=
277  crypto_scalarmult_ed25519_base_noclamp (r_inv->v,
278  inv_s))
279  return GNUNET_SYSERR;
280  return GNUNET_OK;
281 }
unsigned char v[256/8]
Q consists of an x- and a y-value, each mod p (256 bits), given here in affine coordinates and Ed2551...
void GNUNET_CRYPTO_ecc_random_mod_n(struct GNUNET_CRYPTO_EccScalar *r)
Generate a random value mod n.
A ECC scalar for use in point multiplications.
Here is the call graph for this function:

◆ GNUNET_CRYPTO_ecc_rnd_mpi()

void GNUNET_CRYPTO_ecc_rnd_mpi ( struct GNUNET_CRYPTO_EccScalar r,
struct GNUNET_CRYPTO_EccScalar r_neg 
)

Obtain a random scalar for point multiplication on the curve and its additive inverse.

Parameters
[out]rset to a random scalar on the curve
[out]r_negset to the negation of

Definition at line 285 of file crypto_ecc_dlog.c.

References GNUNET_CRYPTO_ecc_random_mod_n(), and GNUNET_CRYPTO_EccScalar::v.

Referenced by run().

287 {
289  crypto_core_ed25519_scalar_negate (r_neg->v,
290  r->v);
291 }
void GNUNET_CRYPTO_ecc_random_mod_n(struct GNUNET_CRYPTO_EccScalar *r)
Generate a random value mod n.
unsigned char v[256/8]
Here is the call graph for this function:
Here is the caller graph for this function:

◆ GNUNET_CRYPTO_ecc_scalar_from_int()

void GNUNET_CRYPTO_ecc_scalar_from_int ( int64_t  val,
struct GNUNET_CRYPTO_EccScalar r 
)

Create a scalar from int value.

Parameters
valthe int value
[out]rwhere to write the salar

Definition at line 295 of file crypto_ecc_dlog.c.

References GNUNET_assert, GNUNET_htonll(), and GNUNET_CRYPTO_EccScalar::v.

Referenced by GNUNET_CRYPTO_ecc_dexp(), GNUNET_CRYPTO_ecc_dlog_prepare(), handle_alices_cryptodata_message(), and send_alices_cryptodata_message().

297 {
298  unsigned char fact[crypto_scalarmult_ed25519_SCALARBYTES];
299  uint64_t valBe;
300 
301  GNUNET_assert (sizeof (*r) == sizeof (fact));
302  if (val < 0)
303  {
304  if (INT64_MIN == val)
305  valBe = GNUNET_htonll ((uint64_t) INT64_MAX);
306  else
307  valBe = GNUNET_htonll ((uint64_t) (-val));
308  }
309  else
310  {
311  valBe = GNUNET_htonll ((uint64_t) val);
312  }
313  memset (fact,
314  0,
315  sizeof (fact));
316  for (unsigned int i = 0; i < sizeof (val); i++)
317  fact[i] = ((unsigned char*) &valBe)[sizeof (val) - 1 - i];
318  if (val < 0)
319  {
320  if (INT64_MIN == val)
321  /* See above: fact is one too small, increment now that we can */
322  sodium_increment (fact,
323  sizeof (fact));
324  crypto_core_ed25519_scalar_negate (r->v,
325  fact);
326  }
327  else
328  {
329  memcpy (r,
330  fact,
331  sizeof (fact));
332  }
333 }
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
uint64_t GNUNET_htonll(uint64_t n)
Convert unsigned 64-bit integer to network byte order.
Definition: common_endian.c:36
unsigned char v[256/8]
Here is the call graph for this function:
Here is the caller graph for this function: