GNUnet  0.11.x
crypto_ecc_dlog.c
Go to the documentation of this file.
1 /*
2  This file is part of GNUnet.
3  Copyright (C) 2012, 2013, 2015 GNUnet e.V.
4 
5  GNUnet is free software: you can redistribute it and/or modify it
6  under the terms of the GNU Affero General Public License as published
7  by the Free Software Foundation, either version 3 of the License,
8  or (at your 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  Affero General Public License for more details.
14 
15  You should have received a copy of the GNU Affero General Public License
16  along with this program. If not, see <http://www.gnu.org/licenses/>.
17 
18  SPDX-License-Identifier: AGPL3.0-or-later
19  */
20 
28 #include "platform.h"
29 #include <gcrypt.h>
30 #include "gnunet_crypto_lib.h"
31 #include "gnunet_container_lib.h"
32 
33 
38 {
42  unsigned int max;
43 
47  unsigned int mem;
48 
56 
60  gcry_ctx_t ctx;
61 };
62 
63 
66  unsigned int mem)
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 }
109 
110 
111 int
113  const struct GNUNET_CRYPTO_EccPoint *input)
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 }
192 
193 
194 void
196 {
197  crypto_core_ed25519_scalar_random (r->v);
198 }
199 
200 
201 void
203 {
205  GNUNET_free (edc);
206 }
207 
208 
209 void
211  struct GNUNET_CRYPTO_EccPoint *r)
212 {
213  struct GNUNET_CRYPTO_EccScalar fact;
214 
216  &fact);
217  crypto_scalarmult_ed25519_base_noclamp (r->v,
218  fact.v);
219 }
220 
221 
224  struct GNUNET_CRYPTO_EccPoint *r)
225 {
226  if (0 ==
227  crypto_scalarmult_ed25519_base_noclamp (r->v,
228  val->v))
229  return GNUNET_OK;
230  return GNUNET_SYSERR;
231 }
232 
233 
236  const struct GNUNET_CRYPTO_EccPoint *b,
237  struct GNUNET_CRYPTO_EccPoint *r)
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 }
246 
247 
250  const struct GNUNET_CRYPTO_EccScalar *val,
251  struct GNUNET_CRYPTO_EccPoint *r)
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 }
260 
261 
264  struct GNUNET_CRYPTO_EccPoint *r_inv)
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 }
282 
283 
284 void
286  struct GNUNET_CRYPTO_EccScalar *r_neg)
287 {
289  crypto_core_ed25519_scalar_negate (r_neg->v,
290  r->v);
291 }
292 
293 
294 void
296  struct GNUNET_CRYPTO_EccScalar *r)
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 }
334 
335 
336 /* end of crypto_ecc_dlog.c */
Point on a curve (always for Curve25519) encoded in a format suitable for network transmission (ECDH)...
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...
#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...
GNUNET_GenericReturnValue
Named constants for return values.
Definition: gnunet_common.h:83
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.
gcry_ctx_t ctx
Context to use for operations on the elliptic curve.
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.
#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).
void GNUNET_CONTAINER_multipeermap_destroy(struct GNUNET_CONTAINER_MultiPeerMap *map)
Destroy a hash map.
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 v...
#define INT_MAX
cryptographic primitives for GNUnet
static struct GNUNET_CRYPTO_EccDlogContext * edc
Context for DLOG operations on a curve.
static struct GNUNET_OS_Process * p
Helper process we started.
Definition: gnunet-qr.c:59
void GNUNET_CRYPTO_ecc_random_mod_n(struct GNUNET_CRYPTO_EccScalar *r)
Generate a random value mod n.
Internal representation of the hash map.
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.
int GNUNET_CRYPTO_ecc_dlog(struct GNUNET_CRYPTO_EccDlogContext *edc, const struct GNUNET_CRYPTO_EccPoint *input)
Calculate ECC discrete logarithm for small factors.
static int res
void GNUNET_CRYPTO_ecc_dlog_release(struct GNUNET_CRYPTO_EccDlogContext *edc)
Release precalculated values.
uint64_t GNUNET_htonll(uint64_t n)
Convert unsigned 64-bit integer to network byte order.
Definition: common_endian.c:36
There must only be one value per key; storing a value should fail if a value under the same key alrea...
unsigned char v[256/8]
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.
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 v...
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.
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,...)
Internal structure used to cache pre-calculated values for DLOG calculation.
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.
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.
#define GNUNET_free(ptr)
Wrapper around free.
unsigned int mem
How much memory should we use (relates to the number of entries in the map).