aboutsummaryrefslogtreecommitdiff
path: root/src/util/crypto_ecc_dlog.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/util/crypto_ecc_dlog.c')
-rw-r--r--src/util/crypto_ecc_dlog.c336
1 files changed, 0 insertions, 336 deletions
diff --git a/src/util/crypto_ecc_dlog.c b/src/util/crypto_ecc_dlog.c
deleted file mode 100644
index 916acd9dd..000000000
--- a/src/util/crypto_ecc_dlog.c
+++ /dev/null
@@ -1,336 +0,0 @@
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
21/**
22 * @file util/crypto_ecc_dlog.c
23 * @brief ECC addition and discreate logarithm for small values.
24 * Allows us to use ECC for computations as long as the
25 * result is relativey small.
26 * @author Christian Grothoff
27 */
28#include "platform.h"
29#include <gcrypt.h>
30#include "gnunet_crypto_lib.h"
31#include "gnunet_container_lib.h"
32
33
34/**
35 * Internal structure used to cache pre-calculated values for DLOG calculation.
36 */
37struct GNUNET_CRYPTO_EccDlogContext
38{
39 /**
40 * Maximum absolute value the calculation supports.
41 */
42 unsigned int max;
43
44 /**
45 * How much memory should we use (relates to the number of entries in the map).
46 */
47 unsigned int mem;
48
49 /**
50 * Map mapping points (here "interpreted" as EdDSA public keys) to
51 * a "void * = long" which corresponds to the numeric value of the
52 * point. As NULL is used to represent "unknown", the actual value
53 * represented by the entry in the map is the "long" minus @e max.
54 */
55 struct GNUNET_CONTAINER_MultiPeerMap *map;
56
57 /**
58 * Context to use for operations on the elliptic curve.
59 */
60 gcry_ctx_t ctx;
61};
62
63
64struct GNUNET_CRYPTO_EccDlogContext *
65GNUNET_CRYPTO_ecc_dlog_prepare (unsigned int max,
66 unsigned int mem)
67{
68 struct GNUNET_CRYPTO_EccDlogContext *edc;
69 int K = ((max + (mem - 1)) / mem);
70
71 GNUNET_assert (max < INT32_MAX);
72 edc = GNUNET_new (struct GNUNET_CRYPTO_EccDlogContext);
73 edc->max = max;
74 edc->mem = mem;
75 edc->map = GNUNET_CONTAINER_multipeermap_create (mem * 2,
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
82 GNUNET_CRYPTO_ecc_scalar_from_int (K * i,
83 &Ki);
84 if (0 == i) /* libsodium does not like to multiply with zero */
85 GNUNET_assert (
86 0 ==
87 crypto_core_ed25519_sub ((unsigned char *) &key,
88 (unsigned char *) &key,
89 (unsigned char *) &key));
90 else
91 GNUNET_assert (
92 0 ==
93 crypto_scalarmult_ed25519_base_noclamp ((unsigned char*) &key,
94 Ki.v));
95 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
96 "K*i: %d (mem=%u, i=%d) => %s\n",
97 K * i,
98 mem,
99 i,
100 GNUNET_i2s (&key));
101 GNUNET_assert (GNUNET_OK ==
102 GNUNET_CONTAINER_multipeermap_put (edc->map,
103 &key,
104 (void *) (long) i + max,
105 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
106 }
107 return edc;
108}
109
110
111int
112GNUNET_CRYPTO_ecc_dlog (struct GNUNET_CRYPTO_EccDlogContext *edc,
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 }
159 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
160 "Trying offset i=%u): %s\n",
161 i,
162 GNUNET_i2s (&key));
163 retp = GNUNET_CONTAINER_multipeermap_get (edc->map,
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
194void
195GNUNET_CRYPTO_ecc_random_mod_n (struct GNUNET_CRYPTO_EccScalar *r)
196{
197 crypto_core_ed25519_scalar_random (r->v);
198}
199
200
201void
202GNUNET_CRYPTO_ecc_dlog_release (struct GNUNET_CRYPTO_EccDlogContext *edc)
203{
204 GNUNET_CONTAINER_multipeermap_destroy (edc->map);
205 GNUNET_free (edc);
206}
207
208
209void
210GNUNET_CRYPTO_ecc_dexp (int val,
211 struct GNUNET_CRYPTO_EccPoint *r)
212{
213 struct GNUNET_CRYPTO_EccScalar fact;
214
215 GNUNET_CRYPTO_ecc_scalar_from_int (val,
216 &fact);
217 crypto_scalarmult_ed25519_base_noclamp (r->v,
218 fact.v);
219}
220
221
222enum GNUNET_GenericReturnValue
223GNUNET_CRYPTO_ecc_dexp_mpi (const struct GNUNET_CRYPTO_EccScalar *val,
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
234enum GNUNET_GenericReturnValue
235GNUNET_CRYPTO_ecc_add (const struct GNUNET_CRYPTO_EccPoint *a,
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
248enum GNUNET_GenericReturnValue
249GNUNET_CRYPTO_ecc_pmul_mpi (const struct GNUNET_CRYPTO_EccPoint *p,
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
262enum GNUNET_GenericReturnValue
263GNUNET_CRYPTO_ecc_rnd (struct GNUNET_CRYPTO_EccPoint *r,
264 struct GNUNET_CRYPTO_EccPoint *r_inv)
265{
266 struct GNUNET_CRYPTO_EccScalar s;
267 unsigned char inv_s[crypto_scalarmult_ed25519_SCALARBYTES];
268
269 GNUNET_CRYPTO_ecc_random_mod_n (&s);
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
284void
285GNUNET_CRYPTO_ecc_rnd_mpi (struct GNUNET_CRYPTO_EccScalar *r,
286 struct GNUNET_CRYPTO_EccScalar *r_neg)
287{
288 GNUNET_CRYPTO_ecc_random_mod_n (r);
289 crypto_core_ed25519_scalar_negate (r_neg->v,
290 r->v);
291}
292
293
294void
295GNUNET_CRYPTO_ecc_scalar_from_int (int64_t val,
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 */