aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorPedram Fardzadeh <p.fardzadeh@protonmail.com>2023-11-05 22:40:31 +0100
committerPedram Fardzadeh <p.fardzadeh@protonmail.com>2024-02-28 16:13:12 +0100
commit63c366f4428d2ab31d62650febd28caf774805a9 (patch)
treeadff614ef0a7eeebc630c11f3a38b25f64995c42 /src
parent93b049ebd15a2658593fdf5d93672719fb51f4dd (diff)
downloadgnunet-63c366f4428d2ab31d62650febd28caf774805a9.tar.gz
gnunet-63c366f4428d2ab31d62650febd28caf774805a9.zip
util: initial elligator implementation
Diffstat (limited to 'src')
-rw-r--r--src/include/gnunet_crypto_lib.h97
-rw-r--r--src/lib/util/Makefile.am8
-rw-r--r--src/lib/util/crypto_elligator.c702
-rw-r--r--src/lib/util/meson.build11
-rw-r--r--src/lib/util/test_crypto_elligator.c334
5 files changed, 1152 insertions, 0 deletions
diff --git a/src/include/gnunet_crypto_lib.h b/src/include/gnunet_crypto_lib.h
index 2c7e92fbd..5425a18dd 100644
--- a/src/include/gnunet_crypto_lib.h
+++ b/src/include/gnunet_crypto_lib.h
@@ -349,6 +349,18 @@ struct GNUNET_CRYPTO_Edx25519Signature
349}; 349};
350 350
351/** 351/**
352 * Elligator representative (always for Curve25519)
353 */
354struct GNUNET_CRYPTO_ElligatorRepresentative
355{
356 /**
357 * Represents an element of Curve25519 finite field.
358 * Always smaller than 2 ^ 254 - 10 -> Needs to be serialized into a random-looking byte stream before transmission.
359 */
360 unsigned char r[256 / 8];
361};
362
363/**
352 * Key type for the generic public key union 364 * Key type for the generic public key union
353 */ 365 */
354enum GNUNET_CRYPTO_KeyType 366enum GNUNET_CRYPTO_KeyType
@@ -2652,6 +2664,91 @@ GNUNET_CRYPTO_edx25519_public_key_derive (
2652 size_t seedsize, 2664 size_t seedsize,
2653 struct GNUNET_CRYPTO_Edx25519PublicKey *result); 2665 struct GNUNET_CRYPTO_Edx25519PublicKey *result);
2654 2666
2667/**
2668 * Note: Included in header for testing purposes. GNUNET_CRYPTO_ecdhe_elligator_decoding will be the correct API for the direct map.
2669 * TODO: Make static.
2670 * @ingroup crypto
2671 * Encodes an element of the underlying finite field, so called representative, of Curve25519 to a point on the curve
2672 * This transformation is deterministic
2673 *
2674 * @param representative element of the finite field
2675 * @param point destination for the calculated point on the curve
2676 * @param high_y destination set to "True" if corresponding y-coordinate is > 2 ^ 254 - 10
2677 */
2678bool
2679GNUNET_CRYPTO_ecdhe_elligator_direct_map (uint8_t *point, bool *high_y,
2680 uint8_t *representative);
2681
2682
2683/**
2684 * @ingroup crypto
2685 * Clears the most significant bit and second most significant bit to the serialized representaive before applying elligator direct map.
2686 *
2687 * @param serialized_representative serialized version of an element of Curves25519's finite field
2688 * @param point destination for the calculated point on the curve
2689 * @param high_y destination set to "True" if corresponding y-coordinate is > 2 ^ 254 - 10
2690 */
2691bool
2692GNUNET_CRYPTO_ecdhe_elligator_decoding (struct
2693 GNUNET_CRYPTO_EcdhePublicKey *point,
2694 bool *high_y,
2695 struct
2696 GNUNET_CRYPTO_ElligatorRepresentative *
2697 seriliazed_representative);
2698
2699/**
2700 * @ingroup crypto
2701 * Encodes a point on Curve25519 to a an element of the underlying finite field
2702 * This transformation is deterministic
2703 *
2704 * @param point a point on the curve
2705 * @param high_y encodes if y-coordinate is > 2 ^254 - 10, which determines the representative value out of two
2706 * @param representative destination for the calculated element of the finite field
2707 */
2708bool
2709GNUNET_CRYPTO_ecdhe_elligator_inverse_map (uint8_t *representative, const
2710 uint8_t *point,
2711 bool high_y);
2712
2713
2714/**
2715* Initializes the elligator library
2716* THis function is thread safe
2717*/
2718void
2719GNUNET_CRYPTO_ecdhe_elligator_initialize (void);
2720
2721/**
2722 * @ingroup crypto
2723 * Generates a valid public key for elligator's inverse map by adding a lower order point to a prime order point.
2724 *
2725 * @param pub valid public key for elligator inverse map
2726 * @param pk private key for generating valid public key
2727 */
2728int
2729 GNUNET_CRYPTO_ecdhe_elligator_generate_public_key (unsigned char
2730 pub[
2731 crypto_scalarmult_SCALARBYTES
2732 ],
2733 struct
2734 GNUNET_CRYPTO_EcdhePrivateKey
2735 *pk);
2736
2737
2738/**
2739 * @ingroup crypto
2740 * Generates a private key for Curve25519 and the elligator representative of the corresponding public key
2741 *
2742 * @param repr representative of the public key
2743 * @param pk Curve25519 private key
2744 */
2745int
2746GNUNET_CRYPTO_ecdhe_elligator_key_create (struct
2747 GNUNET_CRYPTO_ElligatorRepresentative
2748 *repr,
2749 struct GNUNET_CRYPTO_EcdhePrivateKey
2750 *pk);
2751
2655 2752
2656/** 2753/**
2657 * Output the given MPI value to the given buffer in network 2754 * Output the given MPI value to the given buffer in network
diff --git a/src/lib/util/Makefile.am b/src/lib/util/Makefile.am
index 6facc5921..f7716cd48 100644
--- a/src/lib/util/Makefile.am
+++ b/src/lib/util/Makefile.am
@@ -60,6 +60,7 @@ libgnunetutil_la_SOURCES = \
60 $(DLOG) \ 60 $(DLOG) \
61 crypto_ecc_setup.c \ 61 crypto_ecc_setup.c \
62 crypto_edx25519.c \ 62 crypto_edx25519.c \
63 crypto_elligator.c \
63 crypto_hash.c \ 64 crypto_hash.c \
64 crypto_hash_file.c \ 65 crypto_hash_file.c \
65 crypto_hkdf.c \ 66 crypto_hkdf.c \
@@ -207,6 +208,7 @@ check_PROGRAMS = \
207 test_crypto_ecdh_eddsa \ 208 test_crypto_ecdh_eddsa \
208 test_crypto_ecdh_ecdsa \ 209 test_crypto_ecdh_ecdsa \
209 test_crypto_edx25519 \ 210 test_crypto_edx25519 \
211 test_crypto_elligator \
210 $(DLOG_TEST) \ 212 $(DLOG_TEST) \
211 test_crypto_hash \ 213 test_crypto_hash \
212 test_crypto_hash_context \ 214 test_crypto_hash_context \
@@ -387,6 +389,12 @@ test_crypto_edx25519_LDADD = \
387 libgnunetutil.la \ 389 libgnunetutil.la \
388 $(LIBGCRYPT_LIBS) 390 $(LIBGCRYPT_LIBS)
389 391
392 test_crypto_elligator_SOURCES = \
393 test_crypto_elligator.c
394test_crypto_elligator_LDADD = \
395 libgnunetutil.la \
396 $(LIBGCRYPT_LIBS)
397
390test_crypto_ecc_dlog_SOURCES = \ 398test_crypto_ecc_dlog_SOURCES = \
391 test_crypto_ecc_dlog.c 399 test_crypto_ecc_dlog.c
392test_crypto_ecc_dlog_LDADD = \ 400test_crypto_ecc_dlog_LDADD = \
diff --git a/src/lib/util/crypto_elligator.c b/src/lib/util/crypto_elligator.c
new file mode 100644
index 000000000..142c0782a
--- /dev/null
+++ b/src/lib/util/crypto_elligator.c
@@ -0,0 +1,702 @@
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, 0xff, 0xff, 0xff, 0xff, 0xff,
99 0xff, 0xff, 0xff,
100 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
101 0xff, 0xff, 0x7f
102};
103
104static const unsigned char negative_1_bytes[P_BYTES] = {
105 0xec, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
106 0xff, 0xff, 0xff,
107 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
108 0xff, 0xff, 0x7f
109};
110
111static const unsigned char negative_2_bytes[P_BYTES] = {
112 0xeb, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
113 0xff, 0xff, 0xff,
114 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
115 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, 0xff, 0xff, 0xff, 0xff, 0xff,
120 0xff, 0xff, 0xff,
121 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
122 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, 0xff, 0xff, 0xff, 0xff, 0xff,
127 0xff, 0xff, 0xff,
128 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
129 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, 0xff, 0xff, 0xff, 0xff, 0xff,
134 0xff, 0xff, 0xff,
135 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
136 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, 0x78, 0xe4, 0x2f, 0xad, 0x06,
141 0x18, 0x43, 0x2f,
142 0xa7, 0xd7, 0xfb, 0x3d, 0x99, 0x00, 0x4d, 0x2b, 0x0b, 0xdf, 0xc1, 0x4f, 0x80,
143 0x24, 0x83, 0x2b
144};
145
146static const unsigned char A_bytes[P_BYTES] = {
147 0x06, 0x6d, 0x07, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
148 0x00, 0x00, 0x00,
149 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
150 0x00, 0x00, 0x00
151};
152
153static const unsigned char negative_A_bytes[P_BYTES] = {
154 0xe7, 0x92, 0xf8, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
155 0xff, 0xff, 0xff,
156 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
157 0xff, 0xff, 0x7f
158};
159
160static const unsigned char u_bytes[P_BYTES] = {
161 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
162 0x00, 0x00, 0x00,
163 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
164 0x00, 0x00, 0x00
165};
166
167static const unsigned char inverted_u_bytes[P_BYTES] = {
168 0xf7, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
169 0xff, 0xff, 0xff,
170 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
171 0xff, 0xff, 0x3f
172};
173
174static const unsigned char d_bytes[P_BYTES] = {
175 0xa3, 0x78, 0x59, 0x13, 0xca, 0x4d, 0xeb, 0x75, 0xab, 0xd8, 0x41, 0x41, 0x4d,
176 0x0a, 0x70, 0x00,
177 0x98, 0xe8, 0x79, 0x77, 0x79, 0x40, 0xc7, 0x8c, 0x73, 0xfe, 0x6f, 0x2b, 0xee,
178 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];
187static mp_limb_t square_root_negative_1[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
196static void
197decode_bytes (mp_limb_t *number, const uint8_t *bytes)
198{
199 mp_limb_t scratch_space[1];
200
201 for (size_t i = 0; i < P_BYTES; ++i)
202 {
203 mpn_lshift (number, number, P_LIMBS, 8);
204 mpn_sec_add_1 (number, number, 1, bytes[P_BYTES - i - 1], scratch_space);
205 }
206}
207
208
209// Erases the number
210
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
221void
222GNUNET_CRYPTO_ecdhe_elligator_initialize (void)
223{
224 static bool initialized = false;
225
226 if (initialized)
227 {
228 return;
229 }
230
231 decode_bytes (p, p_bytes);
232 decode_bytes (negative_1, negative_1_bytes);
233 decode_bytes (negative_2, negative_2_bytes);
234 decode_bytes (divide_negative_1_2, divide_negative_1_2_bytes);
235 decode_bytes (divide_plus_p_3_8, divide_plus_p_3_8_bytes);
236 decode_bytes (divide_minus_p_1_2, divide_minus_p_1_2_bytes);
237 decode_bytes (square_root_negative_1, square_root_negative_1_bytes);
238 decode_bytes (A, A_bytes);
239 decode_bytes (negative_A, negative_A_bytes);
240 decode_bytes (u, u_bytes);
241 decode_bytes (inverted_u, inverted_u_bytes);
242 decode_bytes (d, d_bytes);
243
244 mp_size_t scratch_space_lengths[] = {
245 // For least_square_root
246
247 mpn_sec_powm_itch (P_LIMBS, P_BITS - 1, P_LIMBS),
248 mpn_sec_sqr_itch (P_LIMBS),
249 mpn_sec_div_r_itch (P_LIMBS + P_LIMBS, P_LIMBS),
250 mpn_sec_sub_1_itch (P_LIMBS),
251 mpn_sec_mul_itch (P_LIMBS, P_LIMBS),
252
253 // For Elligator_2_Curve25519_encode
254
255 mpn_sec_powm_itch (P_LIMBS, P_BITS - 1, P_LIMBS),
256 mpn_sec_mul_itch (P_LIMBS, P_LIMBS),
257 mpn_sec_div_r_itch (P_LIMBS + P_LIMBS, P_LIMBS),
258 mpn_sec_sqr_itch (P_LIMBS),
259 mpn_sec_sub_1_itch (P_LIMBS),
260
261 // For Elligator_2_Curve25519_decode
262
263 mpn_sec_sqr_itch (P_LIMBS),
264 mpn_sec_div_r_itch (P_LIMBS + P_LIMBS, P_LIMBS),
265 mpn_sec_div_r_itch (P_LIMBS, P_LIMBS),
266 mpn_sec_mul_itch (P_LIMBS, P_LIMBS),
267 mpn_sec_add_1_itch (P_LIMBS),
268 mpn_sec_powm_itch (P_LIMBS, P_BITS - 1, P_LIMBS),
269
270 // For Elligator_2_Curve25519_convert_from_Ed25519
271 /*
272 mpn_sec_sqr_itch (P_LIMBS),
273 mpn_sec_div_r_itch (P_LIMBS + P_LIMBS, P_LIMBS),
274 mpn_sec_mul_itch (P_LIMBS, P_LIMBS),
275 mpn_sec_add_1_itch (P_LIMBS),
276 mpn_sec_powm_itch (P_LIMBS, P_BITS - 1, P_LIMBS),
277 mpn_sec_sub_1_itch (P_LIMBS)
278 */
279 };
280
281 for (size_t i = 0; i < sizeof scratch_space_lengths
282 / sizeof *scratch_space_lengths; ++i)
283 {
284 if (scratch_space_lengths[i] > scratch_space_length)
285 {
286 scratch_space_length = scratch_space_lengths[i];
287 }
288 }
289
290 initialized = true;
291}
292
293
294// Returns trash if the number is a quadratic non-residue
295
296static void
297least_square_root (mp_limb_t *root, const mp_limb_t *number,
298 mp_limb_t *scratch_space)
299{
300 mp_limb_t a[P_LIMBS + P_LIMBS];
301 mp_limb_t b[P_LIMBS];
302
303 // root := number ^ ((p + 3) / 8)
304
305 mpn_add_n (b, number, p, P_LIMBS); // The next function requires a nonzero input
306 mpn_sec_powm (root, b, P_LIMBS, divide_plus_p_3_8, P_BITS - 1, p, P_LIMBS,
307 scratch_space);
308
309 // If root ^ 2 != number, root := root * square_root(-1)
310
311 mpn_sec_sqr (a, root, P_LIMBS, scratch_space);
312 mpn_sec_div_r (a, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
313 mpn_sub_n (b, a, number, P_LIMBS);
314
315 mp_limb_t condition = mpn_sec_sub_1 (b, b, P_LIMBS, 1, scratch_space) ^ 1;
316
317 mpn_sec_mul (a, root, P_LIMBS, square_root_negative_1, P_LIMBS,
318 scratch_space);
319 mpn_sec_div_r (a, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
320
321 mpn_cnd_swap (condition, root, a, P_LIMBS);
322
323 // If root > (p - 1) / 2, root := -root
324
325 condition = mpn_sub_n (a, divide_minus_p_1_2, root, P_LIMBS);
326
327 mpn_sub_n (a, p, root, P_LIMBS); // If root = 0, a := p
328
329 mpn_cnd_swap (condition, root, a, P_LIMBS);
330}
331
332
333bool
334GNUNET_CRYPTO_ecdhe_elligator_inverse_map (uint8_t *representative, const
335 uint8_t *point,
336 bool high_y)
337{
338 mp_limb_t scratch_space[scratch_space_length];
339
340 mp_limb_t a[P_LIMBS + P_LIMBS];
341 mp_limb_t b[P_LIMBS + P_LIMBS];
342 mp_limb_t c[P_LIMBS + P_LIMBS];
343
344 // a := point
345
346 decode_bytes (a, point);
347
348 // b := -a / (a + A), or b := p if a = 0
349
350 mpn_add_n (b, a, A, P_LIMBS);
351 mpn_sec_powm (c, b, P_LIMBS, negative_2, P_BITS - 1, p, P_LIMBS,
352 scratch_space);
353 mpn_sec_mul (b, c, P_LIMBS, a, P_LIMBS, scratch_space);
354 mpn_sec_div_r (b, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
355 mpn_sub_n (b, p, b, P_LIMBS);
356
357 // If high_y = true, b := 1 / b or b := 0 if it was = p
358
359 mpn_sec_powm (c, b, P_LIMBS, negative_2, P_BITS - 1, p, P_LIMBS,
360 scratch_space);
361 mpn_cnd_swap (high_y, b, c, P_LIMBS);
362
363 // c := b / u
364
365 mpn_sec_mul (c, b, P_LIMBS, inverted_u, P_LIMBS, scratch_space);
366 mpn_sec_div_r (c, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
367
368 // If c is a square modulo p, b := least_square_root(c)
369
370 least_square_root (b, c, scratch_space);
371
372 // Determine, whether b ^ 2 = c
373
374 mpn_sec_sqr (a, b, P_LIMBS, scratch_space);
375 mpn_sec_div_r (a, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
376 mpn_sub_n (a, a, c, P_LIMBS);
377
378 bool result = mpn_sec_sub_1 (a, a, P_LIMBS, 1, scratch_space);
379
380 encode_bytes (representative, b);
381
382 return result;
383}
384
385
386bool
387GNUNET_CRYPTO_ecdhe_elligator_direct_map (uint8_t *point, bool *high_y,
388 uint8_t *representative)
389{
390 mp_limb_t scratch_space[scratch_space_length];
391
392 mp_limb_t a[P_LIMBS + P_LIMBS];
393 mp_limb_t b[P_LIMBS + P_LIMBS];
394 mp_limb_t c[P_LIMBS];
395 mp_limb_t e[P_LIMBS + P_LIMBS];
396
397 // a := representative
398
399 decode_bytes (a, representative);
400
401 // Determine whether a < (p - 1) / 2
402
403 bool result = mpn_sub_n (b, divide_minus_p_1_2, a, P_LIMBS) ^ 1;
404
405 // b := -A / (1 + u * a ^ 2)
406
407 mpn_sec_sqr (b, a, P_LIMBS, scratch_space);
408 mpn_sec_div_r (b, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
409 mpn_sec_mul (a, u, P_LIMBS, b, P_LIMBS, scratch_space);
410 mpn_sec_div_r (a, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
411 mpn_sec_add_1 (b, a, P_LIMBS, 1, scratch_space);
412 mpn_sec_powm (a, b, P_LIMBS, negative_2, P_BITS - 1, p, P_LIMBS,
413 scratch_space);
414 mpn_sec_mul (b, a, P_LIMBS, negative_A, P_LIMBS, scratch_space);
415 mpn_sec_div_r (b, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
416
417 // a := b ^ 3 + A * b ^ 2 + b (with 1-bit overflow)
418
419 mpn_sec_sqr (a, b, P_LIMBS, scratch_space);
420 mpn_sec_div_r (a, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
421 mpn_add_n (c, b, A, P_LIMBS);
422 mpn_sec_mul (e, c, P_LIMBS, a, P_LIMBS, scratch_space);
423 mpn_sec_div_r (e, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
424 mpn_add_n (a, e, b, P_LIMBS);
425
426 // If a is a quadratic residue modulo p, point := b and high_y := 1
427 // Otherwise point := -b - A and high_y := 0
428
429 mpn_sub_n (c, p, b, P_LIMBS);
430 mpn_add_n (c, c, negative_A, P_LIMBS);
431 mpn_sec_div_r (c, P_LIMBS, p, P_LIMBS, scratch_space);
432
433 mpn_sec_powm (e, a, P_LIMBS, divide_minus_p_1_2, P_BITS - 1, p, P_LIMBS,
434 scratch_space);
435 *high_y = mpn_sub_n (e, e, divide_minus_p_1_2, P_LIMBS);
436
437 mpn_cnd_swap (*high_y, b, c, P_LIMBS);
438
439 encode_bytes (point, c);
440
441 return result;
442}
443
444
445// Removes most significant bit and second most significant bit before applying elligator direct map
446bool
447GNUNET_CRYPTO_ecdhe_elligator_decoding (struct
448 GNUNET_CRYPTO_EcdhePublicKey *point,
449 bool *high_y,
450 struct
451 GNUNET_CRYPTO_ElligatorRepresentative *
452 representative)
453{
454 representative->r[31] &= 63;
455 return GNUNET_CRYPTO_ecdhe_elligator_direct_map ((uint8_t *) point->q_y,
456 high_y,
457 (uint8_t *) representative->r);
458}
459
460
461static bool
462Elligator_2_Curve25519_convert_from_Ed25519 (uint8_t *point, const
463 uint8_t *source)
464{
465 mp_limb_t scratch_space[scratch_space_length];
466
467 mp_limb_t y[P_LIMBS];
468 mp_limb_t a[P_LIMBS + P_LIMBS];
469 mp_limb_t b[P_LIMBS + P_LIMBS];
470 mp_limb_t c[P_LIMBS + P_LIMBS];
471
472 uint8_t y_bytes[P_BYTES];
473
474 memcpy (y_bytes, source, 31);
475
476 y_bytes[31] = source[31] & 0x7f;
477
478 decode_bytes (y, y_bytes);
479
480 // Check if y < p
481
482 bool result = mpn_sub_n (a, y, p, P_LIMBS);
483
484 // a := (y ^ 2 - 1) / (1 + d * y ^ 2)
485
486 mpn_sec_sqr (a, y, P_LIMBS, scratch_space);
487 mpn_sec_div_r (a, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
488 mpn_sec_mul (b, a, P_LIMBS, d, P_LIMBS, scratch_space);
489 mpn_sec_add_1 (b, b, P_LIMBS, 1, scratch_space);
490 mpn_sec_div_r (b, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
491 mpn_sec_powm (c, b, P_LIMBS, negative_2, P_BITS - 1, p, P_LIMBS,
492 scratch_space);
493 mpn_add_n (b, a, negative_1, P_LIMBS);
494 mpn_sec_mul (a, b, P_LIMBS, c, P_LIMBS, scratch_space);
495 mpn_sec_div_r (a, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
496
497 // Check, whether a is a square modulo p (including a = 0)
498
499 mpn_add_n (a, a, p, P_LIMBS);
500 mpn_sec_powm (b, a, P_LIMBS, divide_negative_1_2, P_BITS - 1, p, P_LIMBS,
501 scratch_space);
502
503 result &= mpn_sub_n (c, b, divide_minus_p_1_2, P_LIMBS);
504
505 // If a = p, the parity bit must be 0
506
507 mpn_sub_n (a, a, p, P_LIMBS);
508
509 result ^= mpn_sec_sub_1 (a, a, P_LIMBS, 1, scratch_space) & source[31] >> 7;
510
511 // If y != 1, c := (1 + y) / (1 - y), otherwise c := 0
512
513 mpn_sub_n (a, p, y, P_LIMBS);
514 mpn_sec_add_1 (a, a, P_LIMBS, 1, scratch_space);
515 mpn_sec_powm (b, a, P_LIMBS, negative_2, P_BITS - 1, p, P_LIMBS,
516 scratch_space);
517 mpn_sec_add_1 (a, y, P_LIMBS, 1, scratch_space);
518 mpn_sec_mul (c, a, P_LIMBS, b, P_LIMBS, scratch_space);
519 mpn_sec_div_r (c, P_LIMBS + P_LIMBS, p, P_LIMBS, scratch_space);
520
521 encode_bytes (point, c);
522
523 return result;
524}
525
526
527// Would call GNUNET_CRYPTO_ecdhe_key_create (struct GNUNET_CRYPTO_EcdhePrivateKey *pk) for pk which is not clamped
528// Following Method 1 in description https://elligator.org/key-exchange section Step 2: Generate a “special” public key
529int
530GNUNET_CRYPTO_ecdhe_elligator_generate_public_key (unsigned char
531 pub[
532 crypto_scalarmult_SCALARBYTES
533 ],
534 struct
535 GNUNET_CRYPTO_EcdhePrivateKey
536 *pk)
537{
538 // eHigh
539 // Note crypto_scalarmult_ed25519_base clamps the scalar (here pk->d). TODO: test this
540 // TODO: if pk-d is zero cryto_scalarmult... return -1, otherwise 0. Problem if 0? Unlikely anyway
541 unsigned char eHigh[crypto_scalarmult_SCALARBYTES] = {0};
542 crypto_scalarmult_ed25519_base (eHigh, pk->d);
543
544 // eLow: choose a random point of low order
545 int sLow = (pk->d)[0] % 8;
546 unsigned char eLow[crypto_scalarmult_SCALARBYTES] = {0};
547 memcpy (eLow, lookupTable[sLow], crypto_scalarmult_SCALARBYTES);
548
549 // eHigh + eLow
550 unsigned char edPub[crypto_scalarmult_SCALARBYTES] = {0};
551 if (crypto_core_ed25519_add (edPub, eLow, eHigh) == -1)
552 {
553 return GNUNET_SYSERR;
554 }
555
556 // Convert point in Ed25519 to Montgomery point
557 // TODO: libsodium convert function doesn't work. Figure out why. Maybe because we work on the whole curve rather than the prime subgroup.
558 /*if (crypto_sign_ed25519_pk_to_curve25519 (pub, edPub) == -1)
559 {
560 return -1;
561 }*/
562
563 if (Elligator_2_Curve25519_convert_from_Ed25519 (pub, edPub) == false)
564 {
565 return GNUNET_SYSERR;
566 }
567 return GNUNET_OK;
568}
569
570
571/**
572Doesn't work because crypto_scalarmult clamps the scalar. We don't want this.
573Unfortunately a "noclamp" version of multiplication is only available for edwards25519 in libsodium.
574We therefore can't implement the second (alternative) method for generate_public_key.
575Keeping this code for discussion. Delete later.
576
577// Curve25519 point (only x-coordinate) which is needed for the alternativ method of
578//GNUNET_CRYPTO_ecdhe_elligator_generate_public_key_alternativ
579static const unsigned char kPoint[] = {
580 0xD8, 0x86, 0x1A, 0xA2, 0x78, 0x7A, 0xD9, 0x26,
581 0x8B, 0x74, 0x74, 0xB6, 0x82, 0xE3, 0xBE, 0xC3,
582 0xCE, 0x36, 0x9A, 0x1E, 0x5E, 0x31, 0x47, 0xA2,
583 0x6D, 0x37, 0x7C, 0xFD, 0x20, 0xB5, 0xDF, 0x75
584};
585
586// Curve25519 order of prime order subgroup
587static const unsigned char L[] = {
588 0xED, 0xD3, 0xF5, 0x5C, 0x1A, 0x63, 0x12, 0x58,
589 0xD6, 0x9C, 0xF7, 0xA2, 0xDE, 0xF9, 0xDE, 0x14,
590 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
591 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10
592};
593
594static void multiplyLittleEndianArray(const unsigned char *input, int multiplier, unsigned char *output, int arraySize) {
595 int carry = 0;
596
597 for (int i = 0; i < arraySize; ++i) {
598 int result = input[i] * multiplier + carry;
599 output[i] = result & 0xFF; // Store the lower 8 bits in the output array
600 carry = result >> 8; // Carry the remaining bits to the next iteration
601 }
602}
603
604static void addLittleEndianArrays(const unsigned char *array1, const unsigned char *array2, unsigned char *result, int arraySize) {
605 int carry = 0;
606
607 for (int i = 0; i < arraySize; ++i) {
608 int sum = array1[i] + array2[i] + carry;
609 result[i] = sum & 0xFF; // Store the lower 8 bits in the result array
610 carry = sum >> 8; // Carry the remaining bits to the next iteration
611 }
612}
613
614Would call GNUNET_CRYPTO_ecdhe_key_create (struct GNUNET_CRYPTO_EcdhePrivateKey *pk) for pk which is not clamped
615Following Method 1 in description https://elligator.org/key-exchange section Step 2: Generate a “special” public key
616int
617GNUNET_CRYPTO_ecdhe_elligator_generate_public_key_alternativ (unsigned char
618 pub[
619 crypto_scalarmult_SCALARBYTES
620 ],
621 struct
622 GNUNET_CRYPTO_EcdhePrivateKey
623 *pk)
624{
625 unsigned char sClamp[crypto_scalarmult_BYTES] = {0};
626 memcpy(sClamp, pk->d, sizeof(sClamp));
627 sClamp[0] &= 248;
628 sClamp[31] &= 127;
629 sClamp[31] |= 64;
630
631 unsigned char sLow[crypto_scalarmult_BYTES] = {0};
632 int multiplier = (pk->d)[0] % 8;
633 multiplyLittleEndianArray(L, multiplier, sLow, 32);
634 unsigned char sDirty[crypto_scalarmult_BYTES] = {0};
635 addLittleEndianArrays(sClamp, sLow, sDirty, 32);
636
637 int check = crypto_scalarmult(pub, sDirty,
638 kPoint);
639
640 if (check == -1)
641 {
642 printf("crypto_scalarmult didn't work\n");
643 return -1;
644 }
645
646 return 0;
647}
648**/
649
650enum GNUNET_GenericReturnValue
651GNUNET_CRYPTO_ecdhe_elligator_key_create (struct
652 GNUNET_CRYPTO_ElligatorRepresentative
653 *
654 repr,
655 struct GNUNET_CRYPTO_EcdhePrivateKey
656 *pk)
657{
658 // inverse map can fail for some public keys generated by GNUNET_CRYPTO_ecdhe_elligator_generate_public_key
659 bool validKey = 0;
660 unsigned char pub[crypto_scalarmult_SCALARBYTES];
661 int8_t random_tweak;
662 bool high_y;
663 bool msb_set;
664 bool smsb_set;
665
666 while (! validKey)
667 {
668 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_NONCE,
669 pk,
670 sizeof (struct GNUNET_CRYPTO_EcdhePrivateKey));
671 if (GNUNET_CRYPTO_ecdhe_elligator_generate_public_key (pub, pk) ==
672 GNUNET_SYSERR)
673 {
674 return GNUNET_SYSERR;
675 }
676
677 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_NONCE,
678 &random_tweak,
679 sizeof(int8_t));
680 high_y = random_tweak & 1;
681
682 validKey = GNUNET_CRYPTO_ecdhe_elligator_inverse_map ((unsigned
683 char*) &(repr->r),
684 (unsigned char*) pub,
685 high_y ?
686 GNUNET_YES :
687 GNUNET_NO);
688 }
689
690 // Setting most significant bit and second most significant bit randomly
691 msb_set = (random_tweak >> 1) & 1;
692 smsb_set = (random_tweak >> 2) & 1;
693 if (msb_set)
694 {
695 repr->r[31] |= 128;
696 }
697 if (smsb_set)
698 {
699 repr->r[31] |= 64;
700 }
701 return GNUNET_OK;
702} \ No newline at end of file
diff --git a/src/lib/util/meson.build b/src/lib/util/meson.build
index c9a73bdd3..828df25fd 100644
--- a/src/lib/util/meson.build
+++ b/src/lib/util/meson.build
@@ -27,6 +27,7 @@ libgnunetutil_src = ['bandwidth.c',
27 'crypto_ecc_dlog.c', 27 'crypto_ecc_dlog.c',
28 'crypto_ecc_setup.c', 28 'crypto_ecc_setup.c',
29 'crypto_edx25519.c', 29 'crypto_edx25519.c',
30 'crypto_elligator.c',
30 'crypto_hash.c', 31 'crypto_hash.c',
31 'crypto_hash_file.c', 32 'crypto_hash_file.c',
32 'crypto_hkdf.c', 33 'crypto_hkdf.c',
@@ -331,6 +332,16 @@ test('test_crypto_ecc_dlog', testcrypto_ecc_dlog,
331 workdir: meson.current_build_dir(), 332 workdir: meson.current_build_dir(),
332 suite: ['util', 'util-crypto']) 333 suite: ['util', 'util-crypto'])
333 334
335testcrypto_elligator = executable ('test_crypto_elligator',
336 ['test_crypto_elligator.c'],
337 dependencies: [gcrypt_dep, libgnunetutil_dep, lgmp_dep, sodium_dep],
338 include_directories: [incdir, configuration_inc],
339 build_by_default: false,
340 install: false)
341test('test_crypto_elligator', testcrypto_elligator,
342 workdir: meson.current_build_dir(),
343 suite: ['util', 'util-crypto'])
344
334testcrypto_hash = executable ('test_crypto_hash', 345testcrypto_hash = executable ('test_crypto_hash',
335 ['test_crypto_hash.c'], 346 ['test_crypto_hash.c'],
336 dependencies: [gcrypt_dep, libgnunetutil_dep], 347 dependencies: [gcrypt_dep, libgnunetutil_dep],
diff --git a/src/lib/util/test_crypto_elligator.c b/src/lib/util/test_crypto_elligator.c
new file mode 100644
index 000000000..fc541887d
--- /dev/null
+++ b/src/lib/util/test_crypto_elligator.c
@@ -0,0 +1,334 @@
1#include "platform.h"
2#include "gnunet_util_lib.h"
3#include "gnunet_signatures.h"
4#include <gcrypt.h>
5#include <stdio.h>
6#include <sodium.h>
7
8#define ITER 25
9
10// For debugging purposes
11static void
12printLittleEndianHex (const unsigned char *arr, size_t length)
13{
14 for (size_t i = 0; i < length; ++i)
15 {
16 printf ("%02X", arr[i]);
17 }
18 printf ("\n");
19}
20
21
22// Test vector from https://github.com/Kleshni/Elligator-2/blob/master/test-vectors.c
23static int
24testDirectMap (void)
25{
26 int ok = GNUNET_OK;
27
28 uint8_t repr1[32] = {
29 0x17, 0x9f, 0x24, 0x73, 0x0d, 0xed, 0x2c, 0xe3, 0x17, 0x39, 0x08, 0xec,
30 0x61, 0x96, 0x46, 0x53,
31 0xb8, 0x02, 0x7e, 0x38, 0x3f, 0x40, 0x34, 0x6c, 0x1c, 0x9b, 0x4d, 0x2b,
32 0xdb, 0x1d, 0xb7, 0x6c
33 };
34
35 uint8_t point1[32] = {
36 0x10, 0x74, 0x54, 0x97, 0xd3, 0x5c, 0x6e, 0xde, 0x6e, 0xa6, 0xb3, 0x30,
37 0x54, 0x6a, 0x6f, 0xcb,
38 0xf1, 0x5c, 0x90, 0x3a, 0x7b, 0xe2, 0x8a, 0xe6, 0x9b, 0x1c, 0xa1, 0x4e,
39 0x0b, 0xf0, 0x9b, 0x60
40 };
41
42 uint8_t pointResult[32];
43 bool highYResult;
44 bool isLeastSqrRoot = GNUNET_CRYPTO_ecdhe_elligator_direct_map (pointResult,
45 &highYResult,
46 repr1);
47
48 if (isLeastSqrRoot == false)
49 {
50 ok = GNUNET_OK;
51 }
52 if (memcmp (point1,pointResult,sizeof(point1)) != 0)
53 {
54 ok = GNUNET_SYSERR;
55 }
56
57 return ok;
58}
59
60
61// Test vector from https://github.com/Kleshni/Elligator-2/blob/master/test-vectors.c
62static int
63testInverseMap (void)
64{
65 int ok = GNUNET_OK;
66 uint8_t point1[32] = {
67 0x33, 0x95, 0x19, 0x64, 0x00, 0x3c, 0x94, 0x08, 0x78, 0x06, 0x3c, 0xcf,
68 0xd0, 0x34, 0x8a, 0xf4,
69 0x21, 0x50, 0xca, 0x16, 0xd2, 0x64,0x6f, 0x2c, 0x58, 0x56, 0xe8, 0x33, 0x83,
70 0x77, 0xd8, 0x00
71 };
72
73 uint8_t repr1[32] = {
74 0x99, 0x9b, 0x59, 0x1b, 0x66, 0x97, 0xd0, 0x74, 0xf2, 0x66, 0x19, 0x22,0x77,
75 0xd5, 0x54, 0xde,
76 0xc3, 0xc2, 0x4c, 0x2e,0xf6, 0x10, 0x81, 0x01, 0xf6, 0x3d, 0x94, 0xf7, 0xff,
77 0xf3, 0xa0, 0x13
78 };
79
80 uint8_t reprResult1[32];
81 bool yHigh1 = false;
82 bool success = GNUNET_CRYPTO_ecdhe_elligator_inverse_map (reprResult1,
83 point1,
84 yHigh1);
85 if (success == false)
86 {
87 ok = GNUNET_SYSERR;
88 }
89 if (memcmp (repr1,reprResult1,sizeof(repr1)) != 0)
90 {
91 ok = GNUNET_SYSERR;
92 }
93
94 return ok;
95}
96
97
98/*
99* Test description: GNUNET_CRYPTO_ecdhe_elligator_generate_public_key() projects a point from the prime subgroup to the whole curve.
100* Both, the original point and the projectes point, should result in the same point when multiplied with a clamped scalar.
101*/
102static int
103testGeneratePkScalarMult (void)
104{
105 struct GNUNET_CRYPTO_EcdhePrivateKey pk;
106 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_NONCE,
107 &pk,
108 sizeof (struct GNUNET_CRYPTO_EcdhePrivateKey));
109
110 unsigned char pubWholeCurve[crypto_scalarmult_SCALARBYTES];
111 unsigned char pubPrimeCurve[crypto_scalarmult_SCALARBYTES];
112
113 if (GNUNET_CRYPTO_ecdhe_elligator_generate_public_key (pubWholeCurve, &pk) ==
114 -1)
115 {
116 return GNUNET_SYSERR;
117 }
118 crypto_scalarmult_base (pubPrimeCurve, pk.d);
119
120 // printf ("pubWholeCurve\n");
121 // printLittleEndianHex (pubWholeCurve,32);
122 // printf ("pubPrimeCurve\n");
123 // printLittleEndianHex (pubPrimeCurve,32);
124 // TODO: Currently utilizing ecdsa function for ecdhe testing, due to clamping. Clean this part later.
125 struct GNUNET_CRYPTO_EcdsaPrivateKey clampedPk;
126 GNUNET_CRYPTO_ecdsa_key_create (&clampedPk);
127 crypto_scalarmult_base (pubWholeCurve, clampedPk.d);
128 crypto_scalarmult_base (pubPrimeCurve, clampedPk.d);
129 if (memcmp (pubWholeCurve, pubPrimeCurve, sizeof(pubWholeCurve)) != 0)
130 {
131 return GNUNET_SYSERR;
132 }
133 return GNUNET_OK;
134}
135
136
137/*
138* Test Description: Simply testing, if function goes through.
139*/
140static int
141testKeyPairEasy (void)
142{
143 struct GNUNET_CRYPTO_ElligatorRepresentative repr;
144 struct GNUNET_CRYPTO_EcdhePrivateKey pk;
145 int i = GNUNET_CRYPTO_ecdhe_elligator_key_create (&repr, &pk);
146 if (i == GNUNET_SYSERR)
147 {
148 return GNUNET_SYSERR;
149 }
150 return GNUNET_OK;
151}
152
153
154/*
155* Test Description: After generating a valid private key and the corresponding representative with
156* GNUNET_CRYPTO_ecdhe_elligator_key_create(), check if using the direct map results in the corresponding public key.
157*/
158static int
159testInverseDirect (void)
160{
161 struct GNUNET_CRYPTO_ElligatorRepresentative repr;
162 struct GNUNET_CRYPTO_EcdhePublicKey point;
163 struct GNUNET_CRYPTO_EcdhePrivateKey pk;
164 int i = GNUNET_CRYPTO_ecdhe_elligator_key_create (&repr, &pk);
165 if (i == -1)
166 {
167 return GNUNET_SYSERR;
168 }
169
170 unsigned char pub[crypto_scalarmult_SCALARBYTES];
171 bool highY;
172 if (GNUNET_CRYPTO_ecdhe_elligator_generate_public_key (pub, &pk) == -1)
173 {
174 return GNUNET_SYSERR;
175 }
176
177 GNUNET_CRYPTO_ecdhe_elligator_decoding (&point, &highY, &repr);
178
179 if (memcmp (pub, point.q_y, sizeof(point.q_y)) != 0)
180 {
181 return GNUNET_SYSERR;
182 }
183
184 return GNUNET_OK;
185}
186
187
188/*
189* Test Description: Measuring the time it takes to generate 25 key pairs (pk, representative).
190* Time value can vary because GNUNET_CRYPTO_ecdhe_elligator_key_create generates internally random
191* public keys which are just valid 50% of the time for elligators inverse map.
192* GNUNET_CRYPTO_ecdhe_elligator_key_create will therefore generate as many public keys needed
193* till a valid public key is generated.
194*/
195static int
196testTimeKeyGenerate (void)
197{
198 struct GNUNET_CRYPTO_ElligatorRepresentative repr;
199 struct GNUNET_CRYPTO_EcdhePrivateKey pk;
200 struct GNUNET_TIME_Absolute start;
201 int ok = GNUNET_OK;
202
203 fprintf (stderr, "%s", "W");
204 start = GNUNET_TIME_absolute_get ();
205
206 for (unsigned int i = 0; i < ITER; i++)
207 {
208 fprintf (stderr, "%s", ".");
209 fflush (stderr);
210 if (GNUNET_SYSERR ==
211 GNUNET_CRYPTO_ecdhe_elligator_key_create (&repr, &pk))
212 {
213 fprintf (stderr,
214 "GNUNET_CRYPTO_ecdhe_elligator_key_create SYSERR\n");
215 ok = GNUNET_SYSERR;
216 }
217 // printLittleEndianHex(repr.r,32);
218 }
219 printf ("%d encoded public keys generated in %s\n",
220 ITER,
221 GNUNET_STRINGS_relative_time_to_string (
222 GNUNET_TIME_absolute_get_duration (start),
223 GNUNET_YES));
224 return ok;
225}
226
227
228static int
229testTimeDecoding (void)
230{
231 struct GNUNET_CRYPTO_EcdhePublicKey point;
232 struct GNUNET_CRYPTO_ElligatorRepresentative repr[ITER];
233 struct GNUNET_CRYPTO_EcdhePrivateKey pk;
234 bool high_y;
235 struct GNUNET_TIME_Absolute start;
236 int ok = GNUNET_OK;
237
238 for (unsigned int i = 0; i < ITER; i++)
239 {
240 if (GNUNET_SYSERR ==
241 GNUNET_CRYPTO_ecdhe_elligator_key_create (&repr[i], &pk))
242 {
243 fprintf (stderr,
244 "GNUNET_CRYPTO_ecdhe_elligator_key_create SYSERR\n");
245 ok = GNUNET_SYSERR;
246 continue;
247 }
248 }
249
250 fprintf (stderr, "%s", "W");
251 start = GNUNET_TIME_absolute_get ();
252
253 for (unsigned int i = 0; i < ITER; i++)
254 {
255 fprintf (stderr, "%s", ".");
256 fflush (stderr);
257 if (false ==
258 GNUNET_CRYPTO_ecdhe_elligator_decoding (&point, &high_y, &repr[i]))
259 {
260 fprintf (stderr,
261 "GNUNET_CRYPTO_ecdhe_elligator_decoding SYSERR\n");
262 ok = GNUNET_SYSERR;
263 continue;
264 }
265 }
266
267 printf ("%d decoded public keys generated in %s\n",
268 ITER,
269 GNUNET_STRINGS_relative_time_to_string (
270 GNUNET_TIME_absolute_get_duration (start),
271 GNUNET_YES));
272 return ok;
273}
274
275
276/*
277*More tests to implement:
278* Adding more test vectors from different sources for inverse and direct map
279 * check if inverse map rightfully fails for points which are not "encodable"
280*/
281
282
283int
284main (int argc, char *argv[])
285{
286 GNUNET_CRYPTO_ecdhe_elligator_initialize ();
287
288 int failure_count = 0;
289
290 if (GNUNET_OK != testInverseMap ())
291 {
292 printf ("inverse failed!");
293 failure_count++;
294 }
295 if (GNUNET_OK != testDirectMap ())
296 {
297 printf ("direct failed!");
298 failure_count++;
299 }
300 if (GNUNET_OK != testGeneratePkScalarMult ())
301 {
302 printf ("generate PK failed!");
303 failure_count++;
304 }
305 if (GNUNET_OK != testKeyPairEasy ())
306 {
307 printf ("key generation doesn't work!");
308 failure_count++;
309 }
310 if (GNUNET_OK != testInverseDirect ())
311 {
312 printf ("Inverse and direct map failed!");
313 failure_count++;
314 }
315 if (GNUNET_OK != testTimeKeyGenerate ())
316 {
317 printf ("Time measurement of key generation failed!");
318 failure_count++;
319 }
320 if (GNUNET_OK != testTimeDecoding ())
321 {
322 printf ("Time measurement of decoding failed!");
323 failure_count++;
324 }
325
326 if (0 != failure_count)
327 {
328 fprintf (stderr,
329 "\n\n%d TESTS FAILED!\n\n",
330 failure_count);
331 return -1;
332 }
333 return 0;
334}
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-01 16:44:18 +0000