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.

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.
struct GNUNET_HashCode key
The key used in the DHT.
static struct GNUNET_CRYPTO_EccDlogContext * edc
Context for DLOG operations on a curve.
#define GNUNET_log(kind,...)
@ GNUNET_OK
Definition: gnunet_common.h:95
@ GNUNET_NO
Definition: gnunet_common.h:94
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).
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.
@ GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY
There must only be one value per key; storing a value should fail if a value under the same key alrea...
const char * GNUNET_i2s(const struct GNUNET_PeerIdentity *pid)
Convert a peer identity to a string (for printing debug messages).
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
@ GNUNET_ERROR_TYPE_DEBUG
#define GNUNET_new(type)
Allocate a struct or union of the given type.
#define max(x, y)
Internal structure used to cache pre-calculated values for DLOG calculation.
struct GNUNET_CONTAINER_MultiPeerMap * map
Map mapping points (here "interpreted" as EdDSA public keys) to a "void * = long" which corresponds t...
unsigned int mem
How much memory should we use (relates to the number of entries in the map).
unsigned int max
Maximum absolute value the calculation supports.
A ECC scalar for use in point multiplications.
The identity of the host (wraps the signing key of the peer).

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, key, GNUNET_CRYPTO_EccDlogContext::map, max, GNUNET_CRYPTO_EccDlogContext::max, GNUNET_CRYPTO_EccDlogContext::mem, and GNUNET_CRYPTO_EccScalar::v.

Referenced by run().

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.

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 }
#define INT_MAX
static int res
static struct GNUNET_REVOCATION_Query * q
Handle for revocation query.
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.
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...

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

Referenced by handle_bobs_cryptodata_message().

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.

196 {
197  crypto_core_ed25519_scalar_random (r->v);
198 }
unsigned char v[256/8]

References GNUNET_CRYPTO_EccScalar::v.

Referenced by GNUNET_CRYPTO_ecc_rnd_mpi(), and send_alices_cryptodata_message().

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.

203 {
205  GNUNET_free (edc);
206 }
void GNUNET_CONTAINER_multipeermap_destroy(struct GNUNET_CONTAINER_MultiPeerMap *map)
Destroy a hash map.
#define GNUNET_free(ptr)
Wrapper around free.

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

Referenced by shutdown_task().

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.

212 {
213  struct GNUNET_CRYPTO_EccScalar fact;
214 
216  &fact);
217  crypto_scalarmult_ed25519_base_noclamp (r->v,
218  fact.v);
219 }

◆ 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 210 of file crypto_ecc_dlog.c.

225 {
226  if (0 ==
227  crypto_scalarmult_ed25519_base_noclamp (r->v,
228  val->v))
229  return GNUNET_OK;
230  return GNUNET_SYSERR;
231 }
@ GNUNET_SYSERR
Definition: gnunet_common.h:93

Referenced by send_alices_cryptodata_message().

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 210 of file crypto_ecc_dlog.c.

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 }

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

Referenced by handle_alices_cryptodata_message(), and handle_bobs_cryptodata_message().

Here is the call graph for this function:
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 210 of file crypto_ecc_dlog.c.

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 }
static struct GNUNET_OS_Process * p
Helper process we started.
Definition: gnunet-qr.c:59

Referenced by handle_alices_cryptodata_message(), and handle_bobs_cryptodata_message().

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 210 of file crypto_ecc_dlog.c.

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 }
void GNUNET_CRYPTO_ecc_random_mod_n(struct GNUNET_CRYPTO_EccScalar *r)
Generate a random value mod n.

◆ 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.

287 {
289  crypto_core_ed25519_scalar_negate (r_neg->v,
290  r->v);
291 }

References GNUNET_CRYPTO_ecc_random_mod_n(), and GNUNET_CRYPTO_EccScalar::v.

Referenced by run().

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.

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 }
uint64_t GNUNET_htonll(uint64_t n)
Convert unsigned 64-bit integer to network byte order.
Definition: common_endian.c:36

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

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

Here is the call graph for this function:
Here is the caller graph for this function: