GNUnet 0.22.1
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 "gnunet_common.h"
31#include <gcrypt.h>
32#include <sodium.h>
33#include "gnunet_util_lib.h"
34#include "benchmark.h"
35
36#include <stdint.h>
37#include <stdbool.h>
38#include <string.h>
39#include <gmp.h>
40
41// Ed25519 subgroup of points with a low order
42static const uint8_t lookupTable[8][crypto_scalarmult_SCALARBYTES] = {
43 {
44 0x26, 0xE8, 0x95, 0x8F, 0xC2, 0xB2, 0x27, 0xB0,
45 0x45, 0xC3, 0xF4, 0x89, 0xF2, 0xEF, 0x98, 0xF0,
46 0xD5, 0xDF, 0xAC, 0x05, 0xD3, 0xC6, 0x33, 0x39,
47 0xB1, 0x38, 0x02, 0x88, 0x6D, 0x53, 0xFC, 0x05
48 },
49 {
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 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
54 },
55 {
56 0xC7, 0x17, 0x6A, 0x70, 0x3D, 0x4D, 0xD8, 0x4F,
57 0xBA, 0x3C, 0x0B, 0x76, 0x0D, 0x10, 0x67, 0x0F,
58 0x2A, 0x20, 0x53, 0xFA, 0x2C, 0x39, 0xCC, 0xC6,
59 0x4E, 0xC7, 0xFD, 0x77, 0x92, 0xAC, 0x03, 0x7A
60 },
61 {
62 0xEC, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
63 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
64 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
65 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x7F
66 }, {
67 0xC7, 0x17, 0x6A, 0x70, 0x3D, 0x4D, 0xD8, 0x4F,
68 0xBA, 0x3C, 0x0B, 0x76, 0x0D, 0x10, 0x67, 0x0F,
69 0x2A, 0x20, 0x53, 0xFA, 0x2C, 0x39, 0xCC, 0xC6,
70 0x4E, 0xC7, 0xFD, 0x77, 0x92, 0xAC, 0x03, 0xFA
71 }, {
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, 0x00,
75 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80
76 }, {
77 0x26, 0xE8, 0x95, 0x8F, 0xC2, 0xB2, 0x27, 0xB0,
78 0x45, 0xC3, 0xF4, 0x89, 0xF2, 0xEF, 0x98, 0xF0,
79 0xD5, 0xDF, 0xAC, 0x05, 0xD3, 0xC6, 0x33, 0x39,
80 0xB1, 0x38, 0x02, 0x88, 0x6D, 0x53, 0xFC, 0x85
81 },{
82 0x01, 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 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
86 }
87};
88
89// main.h from Kleshnis's elligator implementation
90#include <limits.h>
91
92#define P_BITS (256) // 255 significant bits + 1 for carry
93#define P_BYTES ((P_BITS + CHAR_BIT - 1) / CHAR_BIT)
94#define P_LIMBS ((P_BITS + GMP_NUMB_BITS - 1) / GMP_NUMB_BITS)
95
96
97// main.c from Kleshnis's elligator implementation
98static const unsigned char p_bytes[P_BYTES] = {
99 0xed, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
100 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
101 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
102 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f
103};
104
105static const unsigned char negative_1_bytes[P_BYTES] = {
106 0xec, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
107 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
108 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
109 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f
110};
111
112static const unsigned char negative_2_bytes[P_BYTES] = {
113 0xeb, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
114 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
115 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
116 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f
117};
118
119static const unsigned char divide_negative_1_2_bytes[P_BYTES] = {
120 0xf6, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
121 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
122 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
123 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x3f
124};
125
126static const unsigned char divide_plus_p_3_8_bytes[P_BYTES] = {
127 0xfe, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
128 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
129 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
130 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x0f
131};
132
133static const unsigned char divide_minus_p_1_2_bytes[P_BYTES] = {
134 0xf6, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
135 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
136 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
137 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x3f
138};
139
140static const unsigned char square_root_negative_1_bytes[P_BYTES] = {
141 0xb0, 0xa0, 0x0e, 0x4a, 0x27, 0x1b, 0xee, 0xc4,
142 0x78, 0xe4, 0x2f, 0xad, 0x06, 0x18, 0x43, 0x2f,
143 0xa7, 0xd7, 0xfb, 0x3d, 0x99, 0x00, 0x4d, 0x2b,
144 0x0b, 0xdf, 0xc1, 0x4f, 0x80, 0x24, 0x83, 0x2b
145};
146
147static const unsigned char A_bytes[P_BYTES] = {
148 0x06, 0x6d, 0x07, 0x00, 0x00, 0x00, 0x00, 0x00,
149 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
150 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
151 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
152};
153
154static const unsigned char negative_A_bytes[P_BYTES] = {
155 0xe7, 0x92, 0xf8, 0xff, 0xff, 0xff, 0xff, 0xff,
156 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
157 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
158 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f
159};
160
161static const unsigned char u_bytes[P_BYTES] = {
162 0x02, 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 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
166};
167
168static const unsigned char inverted_u_bytes[P_BYTES] = {
169 0xf7, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
170 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
171 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
172 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x3f
173};
174
175static const unsigned char d_bytes[P_BYTES] = {
176 0xa3, 0x78, 0x59, 0x13, 0xca, 0x4d, 0xeb, 0x75,
177 0xab, 0xd8, 0x41, 0x41, 0x4d, 0x0a, 0x70, 0x00,
178 0x98, 0xe8, 0x79, 0x77, 0x79, 0x40, 0xc7, 0x8c,
179 0x73, 0xfe, 0x6f, 0x2b, 0xee, 0x6c, 0x03, 0x52
180};
181
182static mp_limb_t p[P_LIMBS];
183static mp_limb_t negative_1[P_LIMBS];
184static mp_limb_t negative_2[P_LIMBS];
185static mp_limb_t divide_negative_1_2[P_LIMBS];
186static mp_limb_t divide_plus_p_3_8[P_LIMBS];
187static mp_limb_t divide_minus_p_1_2[P_LIMBS];
189static mp_limb_t A[P_LIMBS];
190static mp_limb_t negative_A[P_LIMBS];
191static mp_limb_t u[P_LIMBS];
192static mp_limb_t inverted_u[P_LIMBS];
193static mp_limb_t d[P_LIMBS];
194
195static mp_size_t scratch_space_length;
196
197// TODO
198static void
199decode_bytes (mp_limb_t *number, const uint8_t *bytes)
200{
201 mp_limb_t scratch_space[1];
202
203 for (size_t i = 0; i < P_BYTES; ++i)
204 {
205 mpn_lshift (number, number, P_LIMBS, 8);
206 mpn_sec_add_1 (number, number, 1, bytes[P_BYTES - i - 1], scratch_space);
207 }
208}
209
210
211// TODO
212static void
213encode_bytes (uint8_t *bytes, mp_limb_t *number)
214{
215 for (size_t i = 0; i < P_BYTES; ++i)
216 {
217 bytes[P_BYTES - i - 1] = mpn_lshift (number, number, P_LIMBS, 8);
218 }
219}
220
221void
223
227void __attribute__ ((constructor))
229{
230 static bool initialized = false;
231
232 mp_size_t scratch_space_lengths[] = {
233 // For least_square_root
234
235 mpn_sec_powm_itch (P_LIMBS, P_BITS - 1, P_LIMBS),
236 mpn_sec_sqr_itch (P_LIMBS),
237 mpn_sec_div_r_itch (P_LIMBS + P_LIMBS, P_LIMBS),
238 mpn_sec_sub_1_itch (P_LIMBS),
239 mpn_sec_mul_itch (P_LIMBS, P_LIMBS),
240
241 // For Elligator_2_Curve25519_encode
242
243 mpn_sec_powm_itch (P_LIMBS, P_BITS - 1, P_LIMBS),
244 mpn_sec_mul_itch (P_LIMBS, P_LIMBS),
245 mpn_sec_div_r_itch (P_LIMBS + P_LIMBS, P_LIMBS),
246 mpn_sec_sqr_itch (P_LIMBS),
247 mpn_sec_sub_1_itch (P_LIMBS),
248
249 // For Elligator_2_Curve25519_decode
250
251 mpn_sec_sqr_itch (P_LIMBS),
252 mpn_sec_div_r_itch (P_LIMBS + P_LIMBS, P_LIMBS),
253 mpn_sec_div_r_itch (P_LIMBS, P_LIMBS),
254 mpn_sec_mul_itch (P_LIMBS, P_LIMBS),
255 mpn_sec_add_1_itch (P_LIMBS),
256 mpn_sec_powm_itch (P_LIMBS, P_BITS - 1, P_LIMBS),
257
258 // For Elligator_2_Curve25519_convert_from_Ed25519
259 mpn_sec_sqr_itch (P_LIMBS),
260 mpn_sec_div_r_itch (P_LIMBS + P_LIMBS, P_LIMBS),
261 mpn_sec_mul_itch (P_LIMBS, P_LIMBS),
262 mpn_sec_add_1_itch (P_LIMBS),
263 mpn_sec_powm_itch (P_LIMBS, P_BITS - 1, P_LIMBS),
264 mpn_sec_sub_1_itch (P_LIMBS)
265 };
266
267 if (initialized)
268 {
269 return;
270 }
271
284
285
286 for (size_t i = 0; i < sizeof scratch_space_lengths
287 / sizeof *scratch_space_lengths; ++i)
288 {
289 if (scratch_space_lengths[i] > scratch_space_length)
290 {
291 scratch_space_length = scratch_space_lengths[i];
292 }
293 }
294
295 initialized = true;
296}
297
298
307static void
308least_square_root (mp_limb_t *root,
309 const mp_limb_t *number,
310 mp_limb_t *scratch_space)
311{
312 mp_limb_t a[P_LIMBS + P_LIMBS];
313 mp_limb_t b[P_LIMBS];
314 mp_limb_t condition;
315
316 // root := number ^ ((p + 3) / 8)
317
318 mpn_add_n (b, number, p, P_LIMBS); // The next function requires a nonzero input
319 mpn_sec_powm (root, b, P_LIMBS, divide_plus_p_3_8, P_BITS - 1, p, P_LIMBS,
320 scratch_space);
321
322 // If root ^ 2 != number, root := root * square_root(-1)
323
324 mpn_sec_sqr (a, root, P_LIMBS, scratch_space);
325 mpn_sec_div_r (a, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
326 mpn_sub_n (b, a, number, P_LIMBS);
327
328 condition = mpn_sec_sub_1 (b, b, P_LIMBS, 1, scratch_space) ^ 1;
329
330 mpn_sec_mul (a, root, P_LIMBS, square_root_negative_1, P_LIMBS,
331 scratch_space);
332 mpn_sec_div_r (a, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
333
334 mpn_cnd_swap (condition, root, a, P_LIMBS);
335
336 // If root > (p - 1) / 2, root := -root
337
338 condition = mpn_sub_n (a, divide_minus_p_1_2, root, P_LIMBS);
339
340 mpn_sub_n (a, p, root, P_LIMBS); // If root = 0, a := p
341
342 mpn_cnd_swap (condition, root, a, P_LIMBS);
343}
344
345
346bool
348 uint8_t random_tweak,
350 const struct GNUNET_CRYPTO_EcdhePublicKey *pub)
351{
352 bool high_y;
353 bool msb_set;
354 bool smsb_set;
355
356
357 uint8_t *representative = r->r;
358 uint8_t *point = (uint8_t *) pub->q_y;
359
360 mp_limb_t scratch_space[scratch_space_length];
361
362 mp_limb_t a[P_LIMBS + P_LIMBS];
363 mp_limb_t b[P_LIMBS + P_LIMBS];
364 mp_limb_t c[P_LIMBS + P_LIMBS];
365
366 high_y = random_tweak & 1;
367
368 // a := point
369
370 decode_bytes (a, point);
371
372 // b := -a / (a + A), or b := p if a = 0
373
374 mpn_add_n (b, a, A, P_LIMBS);
375 mpn_sec_powm (c, b, P_LIMBS, negative_2, P_BITS - 1, p, P_LIMBS,
376 scratch_space);
377 mpn_sec_mul (b, c, P_LIMBS, a, P_LIMBS, scratch_space);
378 mpn_sec_div_r (b, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
379 mpn_sub_n (b, p, b, P_LIMBS);
380
381 // If high_y = true, b := 1 / b or b := 0 if it was = p
382
383 mpn_sec_powm (c, b, P_LIMBS, negative_2, P_BITS - 1, p, P_LIMBS,
384 scratch_space);
385 mpn_cnd_swap (high_y, b, c, P_LIMBS);
386
387 // c := b / u
388
389 mpn_sec_mul (c, b, P_LIMBS, inverted_u, P_LIMBS, scratch_space);
390 mpn_sec_div_r (c, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
391
392 // If c is a square modulo p, b := least_square_root(c)
393
394 least_square_root (b, c, scratch_space);
395
396 // Determine, whether b ^ 2 = c
397
398 mpn_sec_sqr (a, b, P_LIMBS, scratch_space);
399 mpn_sec_div_r (a, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
400 mpn_sub_n (a, a, c, P_LIMBS);
401
402 {
403 bool result = mpn_sec_sub_1 (a, a, P_LIMBS, 1, scratch_space);
404
405 encode_bytes (representative, b);
406
407 // Setting most significant bit and second most significant bit randomly
408 msb_set = (random_tweak >> 1) & 1;
409 smsb_set = (random_tweak >> 2) & 1;
410 if (msb_set)
411 {
412 r->r[31] |= 128;
413 }
414 if (smsb_set)
415 {
416 r->r[31] |= 64;
417 }
418 return result;
419 }
420}
421
422
434static bool
435elligator_direct_map (uint8_t *point,
436 bool *high_y,
437 uint8_t *representative)
438{
439 mp_limb_t scratch_space[scratch_space_length];
440
441 mp_limb_t a[P_LIMBS + P_LIMBS];
442 mp_limb_t b[P_LIMBS + P_LIMBS];
443 mp_limb_t c[P_LIMBS];
444 mp_limb_t e[P_LIMBS + P_LIMBS];
445 bool result;
446
447 // a := representative
448
449 decode_bytes (a, representative);
450
451 // Determine whether a < (p - 1) / 2
452
453 result = mpn_sub_n (b, divide_minus_p_1_2, a, P_LIMBS) ^ 1;
454
455 // b := -A / (1 + u * a ^ 2)
456
457 mpn_sec_sqr (b, a, P_LIMBS, scratch_space);
458 mpn_sec_div_r (b, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
459 mpn_sec_mul (a, u, P_LIMBS, b, P_LIMBS, scratch_space);
460 mpn_sec_div_r (a, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
461 mpn_sec_add_1 (b, a, P_LIMBS, 1, scratch_space);
462 mpn_sec_powm (a, b, P_LIMBS, negative_2, P_BITS - 1, p, P_LIMBS,
463 scratch_space);
464 mpn_sec_mul (b, a, P_LIMBS, negative_A, P_LIMBS, scratch_space);
465 mpn_sec_div_r (b, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
466
467 // a := b ^ 3 + A * b ^ 2 + b (with 1-bit overflow)
468
469 mpn_sec_sqr (a, b, P_LIMBS, scratch_space);
470 mpn_sec_div_r (a, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
471 mpn_add_n (c, b, A, P_LIMBS);
472 mpn_sec_mul (e, c, P_LIMBS, a, P_LIMBS, scratch_space);
473 mpn_sec_div_r (e, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
474 mpn_add_n (a, e, b, P_LIMBS);
475
476 // If a is a quadratic residue modulo p, point := b and high_y := 1
477 // Otherwise point := -b - A and high_y := 0
478
479 mpn_sub_n (c, p, b, P_LIMBS);
480 mpn_add_n (c, c, negative_A, P_LIMBS);
481 mpn_sec_div_r (c, P_LIMBS, p, P_LIMBS, scratch_space);
482
483 mpn_sec_powm (e, a, P_LIMBS, divide_minus_p_1_2, P_BITS - 1, p, P_LIMBS,
484 scratch_space);
485 *high_y = mpn_sub_n (e, e, divide_minus_p_1_2, P_LIMBS);
486
487 mpn_cnd_swap (*high_y, b, c, P_LIMBS);
488
489 encode_bytes (point, c);
490
491 return result;
492}
493
494
495void
497 struct GNUNET_CRYPTO_EcdhePublicKey *point,
498 bool *high_y,
499 const struct GNUNET_CRYPTO_ElligatorRepresentative *representative)
500{
501 // if sign of direct map transformation not needed throw it away
503 bool high_y_local;
504 bool *high_y_ptr;
505 if (NULL == high_y)
506 high_y_ptr = &high_y_local;
507 else
508 high_y_ptr = high_y;
509
510 memcpy (&r_tmp.r, &representative->r, sizeof(r_tmp.r));
511 r_tmp.r[31] &= 63;
512 // GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,"Print high_y\n");
513 elligator_direct_map ((uint8_t *) point->q_y,
514 high_y_ptr,
515 (uint8_t *) r_tmp.r);
516}
517
518
529static bool
531 const uint8_t *source)
532{
533 mp_limb_t scratch_space[scratch_space_length];
534
535 mp_limb_t y[P_LIMBS];
536 mp_limb_t a[P_LIMBS + P_LIMBS];
537 mp_limb_t b[P_LIMBS + P_LIMBS];
538 mp_limb_t c[P_LIMBS + P_LIMBS];
539
540 uint8_t y_bytes[P_BYTES];
541 bool result;
542
543 memcpy (y_bytes, source, 31);
544
545 y_bytes[31] = source[31] & 0x7f;
546
547 decode_bytes (y, y_bytes);
548
549 // Check if y < p
550
551 result = mpn_sub_n (a, y, p, P_LIMBS);
552
553 // a := (y ^ 2 - 1) / (1 + d * y ^ 2)
554
555 mpn_sec_sqr (a, y, P_LIMBS, scratch_space);
556 mpn_sec_div_r (a, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
557 mpn_sec_mul (b, a, P_LIMBS, d, P_LIMBS, scratch_space);
558 mpn_sec_add_1 (b, b, P_LIMBS, 1, scratch_space);
559 mpn_sec_div_r (b, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
560 mpn_sec_powm (c, b, P_LIMBS, negative_2, P_BITS - 1, p, P_LIMBS,
561 scratch_space);
562 mpn_add_n (b, a, negative_1, P_LIMBS);
563 mpn_sec_mul (a, b, P_LIMBS, c, P_LIMBS, scratch_space);
564 mpn_sec_div_r (a, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
565
566 // Check, whether a is a square modulo p (including a = 0)
567
568 mpn_add_n (a, a, p, P_LIMBS);
569 mpn_sec_powm (b, a, P_LIMBS, divide_negative_1_2, P_BITS - 1, p, P_LIMBS,
570 scratch_space);
571
572 result &= mpn_sub_n (c, b, divide_minus_p_1_2, P_LIMBS);
573
574 // If a = p, the parity bit must be 0
575
576 mpn_sub_n (a, a, p, P_LIMBS);
577
578 result ^= mpn_sec_sub_1 (a, a, P_LIMBS, 1, scratch_space) & source[31] >> 7;
579
580 // If y != 1, c := (1 + y) / (1 - y), otherwise c := 0
581
582 mpn_sub_n (a, p, y, P_LIMBS);
583 mpn_sec_add_1 (a, a, P_LIMBS, 1, scratch_space);
584 mpn_sec_powm (b, a, P_LIMBS, negative_2, P_BITS - 1, p, P_LIMBS,
585 scratch_space);
586 mpn_sec_add_1 (a, y, P_LIMBS, 1, scratch_space);
587 mpn_sec_mul (c, a, P_LIMBS, b, P_LIMBS, scratch_space);
588 mpn_sec_div_r (c, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
589
590 encode_bytes (point, c);
591
592 return result;
593}
594
595
600{
601 // eHigh
602 // crypto_scalarmult_ed25519_base clamps the scalar pk->d and return only 0 if pk->d is zero
603 unsigned char eHigh[crypto_scalarmult_SCALARBYTES] = {0};
604 int sLow = (pk->d)[0] % 8;
605 unsigned char eLow[crypto_scalarmult_SCALARBYTES] = {0};
606 unsigned char edPub[crypto_scalarmult_SCALARBYTES] = {0};
607 GNUNET_assert (0 == crypto_scalarmult_ed25519_base (eHigh, pk->d));
608
609 // eLow: choose a random point of low order
610 memcpy (eLow, lookupTable[sLow], crypto_scalarmult_SCALARBYTES);
611
612 // eHigh + eLow
613 if (crypto_core_ed25519_add (edPub, eLow, eHigh) == -1)
614 {
615 return GNUNET_SYSERR;
616 }
617
618 if (convert_from_ed_to_curve (pub->q_y, edPub) == false)
619 {
620 return GNUNET_SYSERR;
621 }
622 return GNUNET_OK;
623}
624
625
628 uint8_t random_tweak,
632{
634 // Continue if generate_public_key fails
635 if (GNUNET_SYSERR ==
637 return GNUNET_SYSERR;
638
639 if (NULL == repr)
640 return GNUNET_OK;
641 if (! GNUNET_CRYPTO_ecdhe_elligator_encoding (random_tweak,
642 repr,
643 &pub))
644 return GNUNET_SYSERR;
645 memcpy (pk->q_y, pub.q_y, sizeof(pk->q_y));
646 return GNUNET_OK;
647}
648
649
655{
656 uint8_t random_tweak;
658 &random_tweak,
659 sizeof(uint8_t));
660
662 sk,
663 pk,
664 repr);
665}
666
667
668void
671{
674 // inverse map can fail for some public keys generated by GNUNET_CRYPTO_ecdhe_elligator_generate_public_key
675 while (true)
676 {
678 sk,
679 sizeof (struct
681 ;
683 &repr))
684 break;
685 }
686
687}
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 enum GNUNET_GenericReturnValue elligator_generate_public_key(const struct GNUNET_CRYPTO_ElligatorEcdhePrivateKey *pk, struct GNUNET_CRYPTO_EcdhePublicKey *pub)
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)]
void GNUNET_CRYPTO_ecdhe_elligator_initialize(void)
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
commonly used definitions; globals in this file are exempt from the rule that the module name ("commo...
bool GNUNET_CRYPTO_ecdhe_elligator_encoding(uint8_t random_tweak, struct GNUNET_CRYPTO_ElligatorRepresentative *r, const struct GNUNET_CRYPTO_EcdhePublicKey *pub)
Encodes a point on Curve25519 to a an element of the underlying finite field.
enum GNUNET_GenericReturnValue GNUNET_CRYPTO_ecdhe_elligator_key_get_public(const struct GNUNET_CRYPTO_ElligatorEcdhePrivateKey *sk, struct GNUNET_CRYPTO_EcdhePublicKey *pk, struct GNUNET_CRYPTO_ElligatorRepresentative *repr)
Generates a valid public key for elligator's inverse map by adding a lower order point to a prime ord...
void GNUNET_CRYPTO_ecdhe_elligator_key_create(struct GNUNET_CRYPTO_ElligatorEcdhePrivateKey *sk)
Generates a private key for Curve25519.
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...
enum GNUNET_GenericReturnValue GNUNET_CRYPTO_ecdhe_elligator_key_get_public_norand(uint8_t random_tweak, const struct GNUNET_CRYPTO_ElligatorEcdhePrivateKey *sk, struct GNUNET_CRYPTO_EcdhePublicKey *pk, struct GNUNET_CRYPTO_ElligatorRepresentative *repr)
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_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
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...
unsigned char q_y[256/8]
Point Q consists of a y-value mod p (256 bits); the x-value is always positive.
Special private ECC key generated by GNUNET_CRYPTO_ecdhe_elligator_key_create.
Elligator representative (always for Curve25519)
uint8_t r[256/8]
Represents an element of Curve25519 finite field.