diff options
Diffstat (limited to 'src/util/crypto_ecc_dlog.c')
-rw-r--r-- | src/util/crypto_ecc_dlog.c | 336 |
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 | */ | ||
37 | struct 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 | |||
64 | struct GNUNET_CRYPTO_EccDlogContext * | ||
65 | GNUNET_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 | |||
111 | int | ||
112 | GNUNET_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 | |||
194 | void | ||
195 | GNUNET_CRYPTO_ecc_random_mod_n (struct GNUNET_CRYPTO_EccScalar *r) | ||
196 | { | ||
197 | crypto_core_ed25519_scalar_random (r->v); | ||
198 | } | ||
199 | |||
200 | |||
201 | void | ||
202 | GNUNET_CRYPTO_ecc_dlog_release (struct GNUNET_CRYPTO_EccDlogContext *edc) | ||
203 | { | ||
204 | GNUNET_CONTAINER_multipeermap_destroy (edc->map); | ||
205 | GNUNET_free (edc); | ||
206 | } | ||
207 | |||
208 | |||
209 | void | ||
210 | GNUNET_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 | |||
222 | enum GNUNET_GenericReturnValue | ||
223 | GNUNET_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 | |||
234 | enum GNUNET_GenericReturnValue | ||
235 | GNUNET_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 | |||
248 | enum GNUNET_GenericReturnValue | ||
249 | GNUNET_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 | |||
262 | enum GNUNET_GenericReturnValue | ||
263 | GNUNET_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 | |||
284 | void | ||
285 | GNUNET_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 | |||
294 | void | ||
295 | GNUNET_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 */ | ||