GNUnet  0.20.0
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 
29 #include "platform.h"
30 #include <gcrypt.h>
31 #include "gnunet_util_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 */
#define INT_MAX
static int res
struct GNUNET_HashCode key
The key used in the DHT.
static struct GNUNET_REVOCATION_Query * q
Handle for revocation query.
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-uri.c:38
void GNUNET_CONTAINER_multipeermap_destroy(struct GNUNET_CONTAINER_MultiPeerMap *map)
Destroy a hash map.
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_get(const struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key)
Given a key find a value in the map matching the key.
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...
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.
#define GNUNET_log(kind,...)
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...
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.
int GNUNET_CRYPTO_ecc_dlog(struct GNUNET_CRYPTO_EccDlogContext *edc, const struct GNUNET_CRYPTO_EccPoint *input)
Calculate ECC discrete logarithm for small factors.
void GNUNET_CRYPTO_ecc_scalar_from_int(int64_t val, struct GNUNET_CRYPTO_EccScalar *r)
Create a scalar from int value.
uint64_t GNUNET_htonll(uint64_t n)
Convert unsigned 64-bit integer to network byte order.
Definition: common_endian.c:37
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.
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...
void GNUNET_CRYPTO_ecc_dlog_release(struct GNUNET_CRYPTO_EccDlogContext *edc)
Release precalculated values.
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.
void GNUNET_CRYPTO_ecc_random_mod_n(struct GNUNET_CRYPTO_EccScalar *r)
Generate a random value mod n.
GNUNET_GenericReturnValue
Named constants for return values.
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.
@ GNUNET_OK
@ GNUNET_NO
@ GNUNET_SYSERR
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 GNUNET_free(ptr)
Wrapper around free.
#define max(x, y)
Internal representation of the hash map.
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.
gcry_ctx_t ctx
Context to use for operations on the elliptic curve.
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...
A ECC scalar for use in point multiplications.
unsigned char v[256/8]
The identity of the host (wraps the signing key of the peer).