GNUnet 0.21.2
crypto_elligator.c
Go to the documentation of this file.
1/*
2 This file is part of GNUnet.
3 Copyright (C) 2002-2013 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 Portions of this code are derived from the Elligator-2 project,
22 which is licensed under the Creative Commons CC0 1.0 Universal Public Domain Dedication.
23 The Elligator-2 project can be found at: https://github.com/Kleshni/Elligator-2
24
25 Note that gmp is already a dependency of GnuTLS
26
27*/
28
29#include "platform.h"
30#include <gcrypt.h>
31#include <sodium.h>
32#include "gnunet_util_lib.h"
33#include "benchmark.h"
34
35#include <stdint.h>
36#include <stdbool.h>
37#include <string.h>
38#include <gmp.h>
39
40// Ed25519 subgroup of points with a low order
41static const uint8_t lookupTable[8][crypto_scalarmult_SCALARBYTES] = {
42 {
43 0x26, 0xE8, 0x95, 0x8F, 0xC2, 0xB2, 0x27, 0xB0,
44 0x45, 0xC3, 0xF4, 0x89, 0xF2, 0xEF, 0x98, 0xF0,
45 0xD5, 0xDF, 0xAC, 0x05, 0xD3, 0xC6, 0x33, 0x39,
46 0xB1, 0x38, 0x02, 0x88, 0x6D, 0x53, 0xFC, 0x05
47 },
48 {
49 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
50 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
51 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
52 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
53 },
54 {
55 0xC7, 0x17, 0x6A, 0x70, 0x3D, 0x4D, 0xD8, 0x4F,
56 0xBA, 0x3C, 0x0B, 0x76, 0x0D, 0x10, 0x67, 0x0F,
57 0x2A, 0x20, 0x53, 0xFA, 0x2C, 0x39, 0xCC, 0xC6,
58 0x4E, 0xC7, 0xFD, 0x77, 0x92, 0xAC, 0x03, 0x7A
59 },
60 {
61 0xEC, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
62 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
63 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
64 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x7F
65 }, {
66 0xC7, 0x17, 0x6A, 0x70, 0x3D, 0x4D, 0xD8, 0x4F,
67 0xBA, 0x3C, 0x0B, 0x76, 0x0D, 0x10, 0x67, 0x0F,
68 0x2A, 0x20, 0x53, 0xFA, 0x2C, 0x39, 0xCC, 0xC6,
69 0x4E, 0xC7, 0xFD, 0x77, 0x92, 0xAC, 0x03, 0xFA
70 }, {
71 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
72 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
73 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
74 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80
75 }, {
76 0x26, 0xE8, 0x95, 0x8F, 0xC2, 0xB2, 0x27, 0xB0,
77 0x45, 0xC3, 0xF4, 0x89, 0xF2, 0xEF, 0x98, 0xF0,
78 0xD5, 0xDF, 0xAC, 0x05, 0xD3, 0xC6, 0x33, 0x39,
79 0xB1, 0x38, 0x02, 0x88, 0x6D, 0x53, 0xFC, 0x85
80 },{
81 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
82 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
83 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
84 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
85 }
86};
87
88// main.h from Kleshnis's elligator implementation
89#include <limits.h>
90
91#define P_BITS (256) // 255 significant bits + 1 for carry
92#define P_BYTES ((P_BITS + CHAR_BIT - 1) / CHAR_BIT)
93#define P_LIMBS ((P_BITS + GMP_NUMB_BITS - 1) / GMP_NUMB_BITS)
94
95
96// main.c from Kleshnis's elligator implementation
97static const unsigned char p_bytes[P_BYTES] = {
98 0xed, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
99 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
100 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
101 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f
102};
103
104static const unsigned char negative_1_bytes[P_BYTES] = {
105 0xec, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
106 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
107 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
108 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f
109};
110
111static const unsigned char negative_2_bytes[P_BYTES] = {
112 0xeb, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
113 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
114 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
115 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f
116};
117
118static const unsigned char divide_negative_1_2_bytes[P_BYTES] = {
119 0xf6, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
120 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
121 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
122 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x3f
123};
124
125static const unsigned char divide_plus_p_3_8_bytes[P_BYTES] = {
126 0xfe, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
127 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
128 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
129 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x0f
130};
131
132static const unsigned char divide_minus_p_1_2_bytes[P_BYTES] = {
133 0xf6, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
134 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
135 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
136 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x3f
137};
138
139static const unsigned char square_root_negative_1_bytes[P_BYTES] = {
140 0xb0, 0xa0, 0x0e, 0x4a, 0x27, 0x1b, 0xee, 0xc4,
141 0x78, 0xe4, 0x2f, 0xad, 0x06, 0x18, 0x43, 0x2f,
142 0xa7, 0xd7, 0xfb, 0x3d, 0x99, 0x00, 0x4d, 0x2b,
143 0x0b, 0xdf, 0xc1, 0x4f, 0x80, 0x24, 0x83, 0x2b
144};
145
146static const unsigned char A_bytes[P_BYTES] = {
147 0x06, 0x6d, 0x07, 0x00, 0x00, 0x00, 0x00, 0x00,
148 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
149 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
150 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
151};
152
153static const unsigned char negative_A_bytes[P_BYTES] = {
154 0xe7, 0x92, 0xf8, 0xff, 0xff, 0xff, 0xff, 0xff,
155 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
156 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
157 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f
158};
159
160static const unsigned char u_bytes[P_BYTES] = {
161 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
162 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
163 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
164 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
165};
166
167static const unsigned char inverted_u_bytes[P_BYTES] = {
168 0xf7, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
169 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
170 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
171 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x3f
172};
173
174static const unsigned char d_bytes[P_BYTES] = {
175 0xa3, 0x78, 0x59, 0x13, 0xca, 0x4d, 0xeb, 0x75,
176 0xab, 0xd8, 0x41, 0x41, 0x4d, 0x0a, 0x70, 0x00,
177 0x98, 0xe8, 0x79, 0x77, 0x79, 0x40, 0xc7, 0x8c,
178 0x73, 0xfe, 0x6f, 0x2b, 0xee, 0x6c, 0x03, 0x52
179};
180
181static mp_limb_t p[P_LIMBS];
182static mp_limb_t negative_1[P_LIMBS];
183static mp_limb_t negative_2[P_LIMBS];
184static mp_limb_t divide_negative_1_2[P_LIMBS];
185static mp_limb_t divide_plus_p_3_8[P_LIMBS];
186static mp_limb_t divide_minus_p_1_2[P_LIMBS];
188static mp_limb_t A[P_LIMBS];
189static mp_limb_t negative_A[P_LIMBS];
190static mp_limb_t u[P_LIMBS];
191static mp_limb_t inverted_u[P_LIMBS];
192static mp_limb_t d[P_LIMBS];
193
194static mp_size_t scratch_space_length;
195
196// TODO
197static void
198decode_bytes (mp_limb_t *number, const uint8_t *bytes)
199{
200 mp_limb_t scratch_space[1];
201
202 for (size_t i = 0; i < P_BYTES; ++i)
203 {
204 mpn_lshift (number, number, P_LIMBS, 8);
205 mpn_sec_add_1 (number, number, 1, bytes[P_BYTES - i - 1], scratch_space);
206 }
207}
208
209
210// TODO
211static void
212encode_bytes (uint8_t *bytes, mp_limb_t *number)
213{
214 for (size_t i = 0; i < P_BYTES; ++i)
215 {
216 bytes[P_BYTES - i - 1] = mpn_lshift (number, number, P_LIMBS, 8);
217 }
218}
219
220
224void __attribute__ ((constructor))
225GNUNET_CRYPTO_ecdhe_elligator_initialize ()
226{
227 static bool initialized = false;
228
229 if (initialized)
230 {
231 return;
232 }
233
246
247 mp_size_t scratch_space_lengths[] = {
248 // For least_square_root
249
250 mpn_sec_powm_itch (P_LIMBS, P_BITS - 1, P_LIMBS),
251 mpn_sec_sqr_itch (P_LIMBS),
252 mpn_sec_div_r_itch (P_LIMBS + P_LIMBS, P_LIMBS),
253 mpn_sec_sub_1_itch (P_LIMBS),
254 mpn_sec_mul_itch (P_LIMBS, P_LIMBS),
255
256 // For Elligator_2_Curve25519_encode
257
258 mpn_sec_powm_itch (P_LIMBS, P_BITS - 1, P_LIMBS),
259 mpn_sec_mul_itch (P_LIMBS, P_LIMBS),
260 mpn_sec_div_r_itch (P_LIMBS + P_LIMBS, P_LIMBS),
261 mpn_sec_sqr_itch (P_LIMBS),
262 mpn_sec_sub_1_itch (P_LIMBS),
263
264 // For Elligator_2_Curve25519_decode
265
266 mpn_sec_sqr_itch (P_LIMBS),
267 mpn_sec_div_r_itch (P_LIMBS + P_LIMBS, P_LIMBS),
268 mpn_sec_div_r_itch (P_LIMBS, P_LIMBS),
269 mpn_sec_mul_itch (P_LIMBS, P_LIMBS),
270 mpn_sec_add_1_itch (P_LIMBS),
271 mpn_sec_powm_itch (P_LIMBS, P_BITS - 1, P_LIMBS),
272
273 // For Elligator_2_Curve25519_convert_from_Ed25519
274 mpn_sec_sqr_itch (P_LIMBS),
275 mpn_sec_div_r_itch (P_LIMBS + P_LIMBS, P_LIMBS),
276 mpn_sec_mul_itch (P_LIMBS, P_LIMBS),
277 mpn_sec_add_1_itch (P_LIMBS),
278 mpn_sec_powm_itch (P_LIMBS, P_BITS - 1, P_LIMBS),
279 mpn_sec_sub_1_itch (P_LIMBS)
280 };
281
282 for (size_t i = 0; i < sizeof scratch_space_lengths
283 / sizeof *scratch_space_lengths; ++i)
284 {
285 if (scratch_space_lengths[i] > scratch_space_length)
286 {
287 scratch_space_length = scratch_space_lengths[i];
288 }
289 }
290
291 initialized = true;
292}
293
294
303static void
304least_square_root (mp_limb_t *root,
305 const mp_limb_t *number,
306 mp_limb_t *scratch_space)
307{
308 mp_limb_t a[P_LIMBS + P_LIMBS];
309 mp_limb_t b[P_LIMBS];
310
311 // root := number ^ ((p + 3) / 8)
312
313 mpn_add_n (b, number, p, P_LIMBS); // The next function requires a nonzero input
314 mpn_sec_powm (root, b, P_LIMBS, divide_plus_p_3_8, P_BITS - 1, p, P_LIMBS,
315 scratch_space);
316
317 // If root ^ 2 != number, root := root * square_root(-1)
318
319 mpn_sec_sqr (a, root, P_LIMBS, scratch_space);
320 mpn_sec_div_r (a, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
321 mpn_sub_n (b, a, number, P_LIMBS);
322
323 mp_limb_t condition = mpn_sec_sub_1 (b, b, P_LIMBS, 1, scratch_space) ^ 1;
324
325 mpn_sec_mul (a, root, P_LIMBS, square_root_negative_1, P_LIMBS,
326 scratch_space);
327 mpn_sec_div_r (a, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
328
329 mpn_cnd_swap (condition, root, a, P_LIMBS);
330
331 // If root > (p - 1) / 2, root := -root
332
333 condition = mpn_sub_n (a, divide_minus_p_1_2, root, P_LIMBS);
334
335 mpn_sub_n (a, p, root, P_LIMBS); // If root = 0, a := p
336
337 mpn_cnd_swap (condition, root, a, P_LIMBS);
338}
339
340
341bool
344 const struct GNUNET_CRYPTO_EcdhePublicKey *pub,
345 bool high_y)
346{
347 uint8_t *representative = (uint8_t *) r->r;
348 uint8_t *point = (uint8_t *) pub->q_y;
349
350 mp_limb_t scratch_space[scratch_space_length];
351
352 mp_limb_t a[P_LIMBS + P_LIMBS];
353 mp_limb_t b[P_LIMBS + P_LIMBS];
354 mp_limb_t c[P_LIMBS + P_LIMBS];
355
356 // a := point
357
358 decode_bytes (a, point);
359
360 // b := -a / (a + A), or b := p if a = 0
361
362 mpn_add_n (b, a, A, P_LIMBS);
363 mpn_sec_powm (c, b, P_LIMBS, negative_2, P_BITS - 1, p, P_LIMBS,
364 scratch_space);
365 mpn_sec_mul (b, c, P_LIMBS, a, P_LIMBS, scratch_space);
366 mpn_sec_div_r (b, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
367 mpn_sub_n (b, p, b, P_LIMBS);
368
369 // If high_y = true, b := 1 / b or b := 0 if it was = p
370
371 mpn_sec_powm (c, b, P_LIMBS, negative_2, P_BITS - 1, p, P_LIMBS,
372 scratch_space);
373 mpn_cnd_swap (high_y, b, c, P_LIMBS);
374
375 // c := b / u
376
377 mpn_sec_mul (c, b, P_LIMBS, inverted_u, P_LIMBS, scratch_space);
378 mpn_sec_div_r (c, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
379
380 // If c is a square modulo p, b := least_square_root(c)
381
382 least_square_root (b, c, scratch_space);
383
384 // Determine, whether b ^ 2 = c
385
386 mpn_sec_sqr (a, b, P_LIMBS, scratch_space);
387 mpn_sec_div_r (a, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
388 mpn_sub_n (a, a, c, P_LIMBS);
389
390 bool result = mpn_sec_sub_1 (a, a, P_LIMBS, 1, scratch_space);
391
392 encode_bytes (representative, b);
393
394 return result;
395}
396
397
409static bool
410elligator_direct_map (uint8_t *point,
411 bool *high_y,
412 uint8_t *representative)
413{
414 mp_limb_t scratch_space[scratch_space_length];
415
416 mp_limb_t a[P_LIMBS + P_LIMBS];
417 mp_limb_t b[P_LIMBS + P_LIMBS];
418 mp_limb_t c[P_LIMBS];
419 mp_limb_t e[P_LIMBS + P_LIMBS];
420
421 // a := representative
422
423 decode_bytes (a, representative);
424
425 // Determine whether a < (p - 1) / 2
426
427 bool result = mpn_sub_n (b, divide_minus_p_1_2, a, P_LIMBS) ^ 1;
428
429 // b := -A / (1 + u * a ^ 2)
430
431 mpn_sec_sqr (b, a, P_LIMBS, scratch_space);
432 mpn_sec_div_r (b, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
433 mpn_sec_mul (a, u, P_LIMBS, b, P_LIMBS, scratch_space);
434 mpn_sec_div_r (a, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
435 mpn_sec_add_1 (b, a, P_LIMBS, 1, scratch_space);
436 mpn_sec_powm (a, b, P_LIMBS, negative_2, P_BITS - 1, p, P_LIMBS,
437 scratch_space);
438 mpn_sec_mul (b, a, P_LIMBS, negative_A, P_LIMBS, scratch_space);
439 mpn_sec_div_r (b, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
440
441 // a := b ^ 3 + A * b ^ 2 + b (with 1-bit overflow)
442
443 mpn_sec_sqr (a, b, P_LIMBS, scratch_space);
444 mpn_sec_div_r (a, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
445 mpn_add_n (c, b, A, P_LIMBS);
446 mpn_sec_mul (e, c, P_LIMBS, a, P_LIMBS, scratch_space);
447 mpn_sec_div_r (e, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
448 mpn_add_n (a, e, b, P_LIMBS);
449
450 // If a is a quadratic residue modulo p, point := b and high_y := 1
451 // Otherwise point := -b - A and high_y := 0
452
453 mpn_sub_n (c, p, b, P_LIMBS);
454 mpn_add_n (c, c, negative_A, P_LIMBS);
455 mpn_sec_div_r (c, P_LIMBS, p, P_LIMBS, scratch_space);
456
457 mpn_sec_powm (e, a, P_LIMBS, divide_minus_p_1_2, P_BITS - 1, p, P_LIMBS,
458 scratch_space);
459 *high_y = mpn_sub_n (e, e, divide_minus_p_1_2, P_LIMBS);
460
461 mpn_cnd_swap (*high_y, b, c, P_LIMBS);
462
463 encode_bytes (point, c);
464
465 return result;
466}
467
468
469void
471 struct GNUNET_CRYPTO_EcdhePublicKey *point,
472 bool *high_y,
473 const struct GNUNET_CRYPTO_ElligatorRepresentative *representative)
474{
475 // if sign of direct map transformation not needed throw it away
476 bool high_y_local;
477 bool *high_y_ptr;
478 if (NULL == high_y)
479 high_y_ptr = &high_y_local;
480 else
481 high_y_ptr = high_y;
482
484 memcpy (&r_tmp.r, &representative->r, sizeof(r_tmp.r));
485 r_tmp.r[31] &= 63;
486 // GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,"Print high_y\n");
487 elligator_direct_map ((uint8_t *) point->q_y,
488 high_y_ptr,
489 (uint8_t *) r_tmp.r);
490}
491
492
503static bool
505 const uint8_t *source)
506{
507 mp_limb_t scratch_space[scratch_space_length];
508
509 mp_limb_t y[P_LIMBS];
510 mp_limb_t a[P_LIMBS + P_LIMBS];
511 mp_limb_t b[P_LIMBS + P_LIMBS];
512 mp_limb_t c[P_LIMBS + P_LIMBS];
513
514 uint8_t y_bytes[P_BYTES];
515
516 memcpy (y_bytes, source, 31);
517
518 y_bytes[31] = source[31] & 0x7f;
519
520 decode_bytes (y, y_bytes);
521
522 // Check if y < p
523
524 bool result = mpn_sub_n (a, y, p, P_LIMBS);
525
526 // a := (y ^ 2 - 1) / (1 + d * y ^ 2)
527
528 mpn_sec_sqr (a, y, P_LIMBS, scratch_space);
529 mpn_sec_div_r (a, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
530 mpn_sec_mul (b, a, P_LIMBS, d, P_LIMBS, scratch_space);
531 mpn_sec_add_1 (b, b, P_LIMBS, 1, scratch_space);
532 mpn_sec_div_r (b, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
533 mpn_sec_powm (c, b, P_LIMBS, negative_2, P_BITS - 1, p, P_LIMBS,
534 scratch_space);
535 mpn_add_n (b, a, negative_1, P_LIMBS);
536 mpn_sec_mul (a, b, P_LIMBS, c, P_LIMBS, scratch_space);
537 mpn_sec_div_r (a, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
538
539 // Check, whether a is a square modulo p (including a = 0)
540
541 mpn_add_n (a, a, p, P_LIMBS);
542 mpn_sec_powm (b, a, P_LIMBS, divide_negative_1_2, P_BITS - 1, p, P_LIMBS,
543 scratch_space);
544
545 result &= mpn_sub_n (c, b, divide_minus_p_1_2, P_LIMBS);
546
547 // If a = p, the parity bit must be 0
548
549 mpn_sub_n (a, a, p, P_LIMBS);
550
551 result ^= mpn_sec_sub_1 (a, a, P_LIMBS, 1, scratch_space) & source[31] >> 7;
552
553 // If y != 1, c := (1 + y) / (1 - y), otherwise c := 0
554
555 mpn_sub_n (a, p, y, P_LIMBS);
556 mpn_sec_add_1 (a, a, P_LIMBS, 1, scratch_space);
557 mpn_sec_powm (b, a, P_LIMBS, negative_2, P_BITS - 1, p, P_LIMBS,
558 scratch_space);
559 mpn_sec_add_1 (a, y, P_LIMBS, 1, scratch_space);
560 mpn_sec_mul (c, a, P_LIMBS, b, P_LIMBS, scratch_space);
561 mpn_sec_div_r (c, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
562
563 encode_bytes (point, c);
564
565 return result;
566}
567
568
573{
574 // eHigh
575 // crypto_scalarmult_ed25519_base clamps the scalar pk->d and return only 0 if pk->d is zero
576 unsigned char eHigh[crypto_scalarmult_SCALARBYTES] = {0};
577 GNUNET_assert (0 == crypto_scalarmult_ed25519_base (eHigh, pk->d));
578
579 // eLow: choose a random point of low order
580 int sLow = (pk->d)[0] % 8;
581 unsigned char eLow[crypto_scalarmult_SCALARBYTES] = {0};
582 memcpy (eLow, lookupTable[sLow], crypto_scalarmult_SCALARBYTES);
583
584 // eHigh + eLow
585 unsigned char edPub[crypto_scalarmult_SCALARBYTES] = {0};
586 if (crypto_core_ed25519_add (edPub, eLow, eHigh) == -1)
587 {
588 return GNUNET_SYSERR;
589 }
590
591 if (convert_from_ed_to_curve (pub->q_y, edPub) == false)
592 {
593 return GNUNET_SYSERR;
594 }
595 return GNUNET_OK;
596}
597
598
599void
603{
604 // inverse map can fail for some public keys generated by GNUNET_CRYPTO_ecdhe_elligator_generate_public_key
605 bool validKey = 0;
607 int8_t random_tweak;
608 bool high_y;
609 bool msb_set;
610 bool smsb_set;
611
612 while (! validKey)
613 {
615 pk,
616 sizeof (struct GNUNET_CRYPTO_EcdhePrivateKey));
617
618 // Continue if generate_public_key fails
619 if (GNUNET_SYSERR ==
621 {
622 continue;
623 }
624
626 &random_tweak,
627 sizeof(int8_t));
628 high_y = random_tweak & 1;
629
631 &pub,
632 high_y ?
633 GNUNET_YES :
634 GNUNET_NO);
635 }
636
637 // Setting most significant bit and second most significant bit randomly
638 msb_set = (random_tweak >> 1) & 1;
639 smsb_set = (random_tweak >> 2) & 1;
640 if (msb_set)
641 {
642 repr->r[31] |= 128;
643 }
644 if (smsb_set)
645 {
646 repr->r[31] |= 64;
647 }
648}
649
650
653 const struct GNUNET_CRYPTO_EddsaPublicKey *pub,
655 struct GNUNET_HashCode *key_material)
656{
658
660
661 return GNUNET_CRYPTO_ecdh_eddsa_kdf (&sk, pub, key_material);
662}
663
664
667 const struct GNUNET_CRYPTO_EddsaPrivateKey *priv,
669 struct GNUNET_HashCode *key_material)
670{
673 return GNUNET_CRYPTO_eddsa_ecdh_kdf (priv, &pub, key_material);
674}
benchmarking for various operations
static bool elligator_direct_map(uint8_t *point, bool *high_y, uint8_t *representative)
Takes a number of the underlying finite field of Curve25519 and projects it into a valid point on tha...
static void decode_bytes(mp_limb_t *number, const uint8_t *bytes)
static void encode_bytes(uint8_t *bytes, mp_limb_t *number)
static mp_limb_t divide_minus_p_1_2[(((256)+GMP_NUMB_BITS - 1)/GMP_NUMB_BITS)]
static mp_limb_t negative_A[(((256)+GMP_NUMB_BITS - 1)/GMP_NUMB_BITS)]
static mp_limb_t negative_2[(((256)+GMP_NUMB_BITS - 1)/GMP_NUMB_BITS)]
static const uint8_t lookupTable[8][crypto_scalarmult_SCALARBYTES]
#define P_BITS
static mp_limb_t square_root_negative_1[(((256)+GMP_NUMB_BITS - 1)/GMP_NUMB_BITS)]
static mp_limb_t p[(((256)+GMP_NUMB_BITS - 1)/GMP_NUMB_BITS)]
static const unsigned char divide_minus_p_1_2_bytes[(((256)+CHAR_BIT - 1)/CHAR_BIT)]
static const unsigned char negative_A_bytes[(((256)+CHAR_BIT - 1)/CHAR_BIT)]
static mp_limb_t d[(((256)+GMP_NUMB_BITS - 1)/GMP_NUMB_BITS)]
static const unsigned char u_bytes[(((256)+CHAR_BIT - 1)/CHAR_BIT)]
#define P_BYTES
#define P_LIMBS
static const unsigned char p_bytes[(((256)+CHAR_BIT - 1)/CHAR_BIT)]
static const unsigned char negative_1_bytes[(((256)+CHAR_BIT - 1)/CHAR_BIT)]
static void least_square_root(mp_limb_t *root, const mp_limb_t *number, mp_limb_t *scratch_space)
Calculates the root of a given number.
static bool convert_from_ed_to_curve(uint8_t *point, const uint8_t *source)
Takes a number of the underlying finite field of Curve25519 and projects it into a valid point on tha...
static const unsigned char negative_2_bytes[(((256)+CHAR_BIT - 1)/CHAR_BIT)]
static mp_size_t scratch_space_length
static const unsigned char A_bytes[(((256)+CHAR_BIT - 1)/CHAR_BIT)]
static const unsigned char square_root_negative_1_bytes[(((256)+CHAR_BIT - 1)/CHAR_BIT)]
static const unsigned char d_bytes[(((256)+CHAR_BIT - 1)/CHAR_BIT)]
static mp_limb_t negative_1[(((256)+GMP_NUMB_BITS - 1)/GMP_NUMB_BITS)]
static const unsigned char divide_plus_p_3_8_bytes[(((256)+CHAR_BIT - 1)/CHAR_BIT)]
static const unsigned char divide_negative_1_2_bytes[(((256)+CHAR_BIT - 1)/CHAR_BIT)]
static mp_limb_t A[(((256)+GMP_NUMB_BITS - 1)/GMP_NUMB_BITS)]
static mp_limb_t inverted_u[(((256)+GMP_NUMB_BITS - 1)/GMP_NUMB_BITS)]
static mp_limb_t divide_plus_p_3_8[(((256)+GMP_NUMB_BITS - 1)/GMP_NUMB_BITS)]
static mp_limb_t u[(((256)+GMP_NUMB_BITS - 1)/GMP_NUMB_BITS)]
static const unsigned char inverted_u_bytes[(((256)+CHAR_BIT - 1)/CHAR_BIT)]
void __attribute__((constructor))
Initialize elligator scratch space.
static mp_limb_t divide_negative_1_2[(((256)+GMP_NUMB_BITS - 1)/GMP_NUMB_BITS)]
static GstElement * source
Appsrc instance into which we write data for the pipeline.
struct GNUNET_CRYPTO_PrivateKey pk
Private key from command line option, or NULL.
static int result
Global testing status.
static struct GNUNET_CRYPTO_EddsaPublicKey pub
Definition: gnunet-scrypt.c:47
enum GNUNET_GenericReturnValue GNUNET_CRYPTO_eddsa_ecdh_kdf(const struct GNUNET_CRYPTO_EddsaPrivateKey *priv, const struct GNUNET_CRYPTO_EcdhePublicKey *pub, struct GNUNET_HashCode *key_material)
Derive key material from a ECDH public key and a private EdDSA key.
Definition: crypto_ecc.c:766
bool GNUNET_CRYPTO_ecdhe_elligator_encoding(struct GNUNET_CRYPTO_ElligatorRepresentative *r, const struct GNUNET_CRYPTO_EcdhePublicKey *pub, bool high_y)
Encodes a point on Curve25519 to a an element of the underlying finite field.
enum GNUNET_GenericReturnValue GNUNET_CRYPTO_eddsa_elligator_kem_encaps(const struct GNUNET_CRYPTO_EddsaPublicKey *pub, struct GNUNET_CRYPTO_ElligatorRepresentative *r, struct GNUNET_HashCode *key_material)
Carries out ecdh encapsulation with given public key and the private key from a freshly created ephem...
void GNUNET_CRYPTO_random_block(enum GNUNET_CRYPTO_Quality mode, void *buffer, size_t length)
Fill block with a random values.
void GNUNET_CRYPTO_ecdhe_elligator_decoding(struct GNUNET_CRYPTO_EcdhePublicKey *point, bool *high_y, const struct GNUNET_CRYPTO_ElligatorRepresentative *representative)
Clears the most significant bit and second most significant bit of the serialized representaive befor...
void GNUNET_CRYPTO_ecdhe_elligator_key_create(struct GNUNET_CRYPTO_ElligatorRepresentative *repr, struct GNUNET_CRYPTO_EcdhePrivateKey *pk)
Generates a private key for Curve25519 and the elligator representative of the corresponding public k...
enum GNUNET_GenericReturnValue GNUNET_CRYPTO_ecdh_eddsa_kdf(const struct GNUNET_CRYPTO_EcdhePrivateKey *priv, const struct GNUNET_CRYPTO_EddsaPublicKey *pub, struct GNUNET_HashCode *key_material)
Derive key material from a EdDSA public key and a private ECDH key.
Definition: crypto_ecc.c:798
enum GNUNET_GenericReturnValue GNUNET_CRYPTO_eddsa_elligator_kem_decaps(const struct GNUNET_CRYPTO_EddsaPrivateKey *priv, const struct GNUNET_CRYPTO_ElligatorRepresentative *r, struct GNUNET_HashCode *key_material)
Carries out ecdh decapsulation with own private key and the representative of the received public key...
enum GNUNET_GenericReturnValue GNUNET_CRYPTO_ecdhe_elligator_generate_public_key(struct GNUNET_CRYPTO_EcdhePublicKey *pub, struct GNUNET_CRYPTO_EcdhePrivateKey *pk)
Generates a valid public key for elligator's inverse map by adding a lower order point to a prime ord...
@ GNUNET_CRYPTO_QUALITY_NONCE
Randomness for IVs etc.
GNUNET_GenericReturnValue
Named constants for return values.
@ GNUNET_OK
@ GNUNET_YES
@ GNUNET_NO
@ GNUNET_SYSERR
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
static int initialized
Have we been initialized?
Definition: plugin.c:59
uint32_t number
Private ECC key encoded for transmission.
Public ECC key (always for Curve25519) encoded in a format suitable for network transmission and encr...
unsigned char q_y[256/8]
Q consists of an x- and a y-value, each mod p (256 bits), given here in affine coordinates and Ed2551...
Private ECC key encoded for transmission.
Public ECC key (always for curve Ed25519) encoded in a format suitable for network transmission and E...
unsigned char q_y[256/8]
Point Q consists of a y-value mod p (256 bits); the x-value is always positive.
Elligator representative (always for Curve25519)
unsigned char r[256/8]
Represents an element of Curve25519 finite field.
A 512-bit hashcode.