Commit | Line | Data |
---|---|---|
d56fd9d1 MW |
1 | /* -*-c-*- |
2 | * | |
3 | * The Ed25519 signature scheme | |
4 | * | |
5 | * (c) 2017 Straylight/Edgeware | |
6 | */ | |
7 | ||
8 | /*----- Licensing notice --------------------------------------------------* | |
9 | * | |
10 | * This file is part of Catacomb. | |
11 | * | |
12 | * Catacomb is free software; you can redistribute it and/or modify | |
13 | * it under the terms of the GNU Library General Public License as | |
14 | * published by the Free Software Foundation; either version 2 of the | |
15 | * License, or (at your option) any later version. | |
16 | * | |
17 | * Catacomb is distributed in the hope that it will be useful, | |
18 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
19 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
20 | * GNU Library General Public License for more details. | |
21 | * | |
22 | * You should have received a copy of the GNU Library General Public | |
23 | * License along with Catacomb; if not, write to the Free | |
24 | * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, | |
25 | * MA 02111-1307, USA. | |
26 | */ | |
27 | ||
28 | /*----- Header files ------------------------------------------------------*/ | |
29 | ||
30 | #include <string.h> | |
31 | ||
32 | #include "f25519.h" | |
33 | #include "ed25519.h" | |
34 | #include "scaf.h" | |
35 | #include "sha512.h" | |
36 | ||
37 | /*----- Key fetching ------------------------------------------------------*/ | |
38 | ||
39 | const key_fetchdef ed25519_pubfetch[] = { | |
40 | { "pub", offsetof(ed25519_pub, pub), KENC_BINARY, 0 }, | |
41 | { 0, 0, 0, 0 } | |
42 | }; | |
43 | ||
44 | static const key_fetchdef priv[] = { | |
45 | { "priv", offsetof(ed25519_priv, priv), KENC_BINARY, 0 }, | |
46 | { 0, 0, 0, 0 } | |
47 | }; | |
48 | ||
49 | const key_fetchdef ed25519_privfetch[] = { | |
50 | { "pub", offsetof(ed25519_priv, pub), KENC_BINARY, 0 }, | |
51 | { "private", 0, KENC_STRUCT, priv }, | |
52 | { 0, 0, 0, 0 } | |
53 | }; | |
54 | ||
55 | /*----- A number of magic numbers -----------------------------------------*/ | |
56 | ||
57 | #if SCAF_IMPL == 32 | |
58 | # define PIECEWD 24 | |
59 | static const scaf_piece l[] = { | |
60 | 0xf5d3ed, 0x631a5c, 0xd65812, 0xa2f79c, 0xdef9de, 0x000014, | |
61 | 0x000000, 0x000000, 0x000000, 0x000000, 0x001000 | |
62 | }; | |
63 | static const scaf_piece mu[] = { | |
64 | 0x1b3994, 0x0a2c13, 0x9ce5a3, 0x29a7ed, 0x5d0863, 0x210621, | |
65 | 0xffffeb, 0xffffff, 0xffffff, 0xffffff, 0xffffff, 0x000fff | |
66 | }; | |
67 | #endif | |
68 | ||
69 | #if SCAF_IMPL == 16 | |
70 | # define PIECEWD 12 | |
71 | static const scaf_piece l[] = { | |
72 | 0x3ed, 0xf5d, 0xa5c, 0x631, 0x812, 0xd65, | |
73 | 0x79c, 0xa2f, 0x9de, 0xdef, 0x014, 0x000, | |
74 | 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, | |
75 | 0x000, 0x000, 0x000, 0x001 | |
76 | }; | |
77 | static const scaf_piece mu[] = { | |
78 | 0x994, 0x1b3, 0xc13, 0x0a2, 0x5a3, 0x9ce, | |
79 | 0x7ed, 0x29a, 0x863, 0x5d0, 0x621, 0x210, | |
80 | 0xfeb, 0xfff, 0xfff, 0xfff, 0xfff, 0xfff, | |
81 | 0xfff, 0xfff, 0xfff, 0xfff, 0xfff | |
82 | }; | |
83 | #endif | |
84 | ||
85 | #define NPIECE SCAF_NPIECE(255, PIECEWD) | |
86 | ||
87 | #if F25519_IMPL == 26 | |
88 | # define P p26 | |
89 | static const int32 bx_pieces[] = { | |
90 | -14297830, -7645148, 16144683, -16471763, 27570974, | |
91 | -2696100, -26142465, 8378389, 20764389, 8758491 | |
92 | }, by_pieces[] = { | |
93 | -26843560, -6710886, 13421773, -13421773, 26843546, | |
94 | 6710886, -13421773, 13421773, -26843546, 26843546 | |
95 | }, d_pieces[] = { | |
96 | -10913629, 13857413, -15372611, 6949391, 114729, | |
97 | -8787816, -6275908, -3247719, -18696448, 21499316 | |
98 | }; | |
99 | #endif | |
100 | #if F25519_IMPL == 10 | |
101 | # define P p10 | |
102 | static const int16 bx_pieces[] = { | |
103 | 282, 373, 242, 386, -467, 86, -423, 318, -437, | |
104 | 75, 236, -308, 421, 92, 439, -35, 400, 452, | |
105 | 82, -40, 160, 441, -51, 437, -365, 134 | |
106 | }, by_pieces[] = { | |
107 | -424, 410, -410, 410, -410, -102, 205, -205, 205, | |
108 | -205, 205, -410, 410, -410, 410, 102, -205, 205, | |
109 | -205, 205, -205, 410, -410, 410, -410, 410 | |
110 | }, d_pieces[] = { | |
111 | 163, -418, 310, -216, -178, -133, 367, -315, -380, | |
112 | -351, -182, -255, 2, 152, -390, -136, -52, -383, | |
113 | -412, -398, -12, 448, -469, -196, 55, 328 | |
114 | }; | |
115 | #endif | |
116 | ||
117 | static const scaf_piece bz_pieces[NPIECE] = { 1, 0, /* ... */ }; | |
118 | #define BX ((const f25519 *)bx_pieces) | |
119 | #define BY ((const f25519 *)by_pieces) | |
120 | #define BZ ((const f25519 *)bz_pieces) | |
121 | #define D ((const f25519 *)d_pieces) | |
122 | ||
123 | /*----- Point encoding and decoding ---------------------------------------*/ | |
124 | ||
125 | static void ptencode(octet q[32], | |
126 | const f25519 *X, const f25519 *Y, const f25519 *Z) | |
127 | { | |
128 | f25519 x, y, t; | |
129 | octet b[32]; | |
130 | ||
131 | f25519_inv(&t, Z); f25519_mul(&x, X, &t); f25519_mul(&y, Y, &t); | |
132 | f25519_store(q, &y); f25519_store(b, &x); q[31] |= (b[0]&1u) << 7; | |
133 | } | |
134 | ||
135 | static int ptdecode(f25519 *X, f25519 *Y, f25519 *Z, const octet q[32]) | |
136 | { | |
137 | octet b[32]; | |
138 | f25519 t, u; | |
139 | uint32 m; | |
140 | int rc; | |
141 | ||
142 | memcpy(b, q, 32); b[31] &= 0x7fu; f25519_load(Y, b); | |
143 | f25519_sqr(&t, Y); f25519_mul(&u, &t, D); t.P[0] -= 1; u.P[0] += 1; | |
144 | rc = f25519_quosqrt(X, &t, &u); | |
145 | f25519_store(b, X); m = -(((q[31] >> 7) ^ b[0])&0x1u); | |
146 | f25519_condneg(X, X, m); | |
147 | f25519_set(Z, 1); | |
148 | return (rc); | |
149 | } | |
150 | ||
151 | /*----- Edwards curve arithmetic ------------------------------------------*/ | |
152 | ||
153 | static void ptadd(f25519 *X, f25519 *Y, f25519 *Z, | |
154 | const f25519 *X0, const f25519 *Y0, const f25519 *Z0, | |
155 | const f25519 *X1, const f25519 *Y1, const f25519 *Z1) | |
156 | { | |
157 | f25519 t0, t1, t2, t3, t4, t5; | |
158 | ||
159 | /* Bernstein, Birkner, Joye, Lange, and Peters, `Twisted Edwards Curves', | |
160 | * 2008-03-13, https://cr.yp.to/newelliptic/twisted-20080313.pdf shows the | |
161 | * formulae as: | |
162 | * | |
163 | * A = Z1 Z2; B = A^2; C = X1 X2; D = Y1 Y2; | |
164 | * E = d C D; F = B - E; G = B + E; | |
165 | * X3 = A F ((X1 + Y1) (X2 + Y2) - C - D); | |
166 | * Y3 = A G (D - a C); Z3 = F G. | |
167 | * | |
168 | * Note that a = -1, which things easier. | |
169 | */ | |
170 | ||
171 | f25519_mul(&t0, Z0, Z1); /* t0 = A = Z0 Z1 */ | |
172 | f25519_sqr(&t1, &t0); /* t1 = B = A^2 */ | |
173 | f25519_mul(&t2, X0, X1); /* t2 = C = X0 X1 */ | |
174 | f25519_mul(&t3, Y0, Y1); /* t3 = D = Y0 Y1 */ | |
175 | f25519_mul(&t4, &t2, &t3); /* t4 = C D */ | |
176 | f25519_mul(&t4, &t4, D); /* t4 = E = d C D */ | |
177 | f25519_sub(&t5, &t1, &t4); /* t5 = F = B - E */ | |
178 | f25519_add(&t4, &t1, &t4); /* t4 = G = B + E */ | |
179 | f25519_add(&t1, &t2, &t3); /* t1 = C + D */ | |
180 | f25519_add(&t2, X0, Y0); /* t2 = X0 + Y0 */ | |
181 | f25519_add(&t3, X1, Y1); /* t3 = X1 + Y1 */ | |
182 | f25519_mul(X, &t0, &t5); /* X = A F */ | |
183 | f25519_mul(Y, &t0, &t4); /* Y = A G */ | |
184 | f25519_mul(Z, &t5, &t4); /* Z = F G */ | |
185 | f25519_mul(Y, Y, &t1); /* Y = A G (C + D) = A G (D - a C) */ | |
186 | f25519_mul(&t0, &t2, &t3); /* t0 = (X0 + Y0) (X1 + Y1) */ | |
187 | f25519_sub(&t0, &t0, &t1); /* t0 = (X0 + Y0) (X1 + Y1) - C - D */ | |
188 | f25519_mul(X, X, &t0); /* X = A F ((X0 + Y0) (X1 + Y1) - C - D) */ | |
189 | } | |
190 | ||
191 | static void ptdbl(f25519 *X, f25519 *Y, f25519 *Z, | |
192 | const f25519 *X0, const f25519 *Y0, const f25519 *Z0) | |
193 | { | |
194 | f25519 t0, t1, t2; | |
195 | ||
196 | /* Bernstein, Birkner, Joye, Lange, and Peters, `Twisted Edwards Curves', | |
197 | * 2008-03-13, https://cr.yp.to/newelliptic/twisted-20080313.pdf shows the | |
198 | * formulae as: | |
199 | * | |
200 | * B = (X1 + Y1)^2; C = X1^2; D = Y1^2; E = a C; | |
201 | * F = E + D; H = Z1^2; J = F - 2 H; | |
202 | * X3 = (B - C - D) J; Y3 = F (E - D); Z3 = F J. | |
203 | * | |
204 | * Note that a = -1, which things easier. | |
205 | */ | |
206 | ||
207 | f25519_add(&t0, X0, Y0); /* t0 = X0 + Y0 */ | |
208 | f25519_sqr(&t0, &t0); /* t0 = B = (X0 + Y0)^2 */ | |
209 | f25519_sqr(&t1, X0); /* t1 = C = X0^2 */ | |
210 | f25519_sqr(&t2, Y0); /* t2 = D = Y0^2 */ | |
211 | f25519_add(Y, &t1, &t2); /* Y = C + D = -(E - D) */ | |
212 | f25519_sub(X, &t0, Y); /* X = B - C - D */ | |
213 | /* (E = a C = -C) */ | |
214 | f25519_sub(&t0, &t2, &t1); /* t0 = F = D - C = E + D */ | |
215 | f25519_sqr(&t1, Z0); /* t1 = H = Z0^2 */ | |
216 | f25519_mulconst(&t1, &t1, 2); /* t1 = 2 H */ | |
217 | f25519_sub(&t1, &t0, &t1); /* t1 = J = F - 2 H */ | |
218 | f25519_mul(X, X, &t1); /* X = (B - C - D) J */ | |
219 | f25519_mul(Y, Y, &t0); /* Y = -F (E - D) */ | |
220 | f25519_neg(Y, Y); /* Y = F (E - D) */ | |
221 | f25519_mul(Z, &t0, &t1); /* Z = F J */ | |
222 | } | |
223 | ||
224 | static void ptmul(f25519 *X, f25519 *Y, f25519 *Z, | |
225 | const scaf_piece n[NPIECE], | |
226 | const f25519 *X0, const f25519 *Y0, const f25519 *Z0) | |
227 | { | |
228 | /* We assume that the window width divides the scalar piece width. */ | |
229 | #define WINWD 4 | |
230 | #define WINLIM (1 << WINWD) | |
231 | #define WINMASK (WINLIM - 1) | |
232 | #define TABSZ (WINLIM/2 + 1) | |
233 | ||
234 | f25519 VX[TABSZ], VY[TABSZ], VZ[TABSZ]; | |
235 | f25519 TX, TY, TZ, UX, UY, UZ; | |
236 | unsigned i, j, k, w; | |
237 | uint32 m_neg; | |
238 | scaf_piece ni; | |
239 | ||
240 | /* Build a table of small multiples. */ | |
241 | f25519_set(&VX[0], 0); f25519_set(&VY[0], 1); f25519_set(&VZ[0], 1); | |
242 | VX[1] = *X0; VY[1] = *Y0; VZ[1] = *Z0; | |
243 | ptdbl(&VX[2], &VY[2], &VZ[2], &VX[1], &VY[1], &VZ[1]); | |
244 | for (i = 3; i < TABSZ; i += 2) { | |
245 | ptadd(&VX[i], &VY[i], &VZ[i], | |
246 | &VX[i - 1], &VY[i - 1], &VZ[i - 1], X0, Y0, Z0); | |
247 | ptdbl(&VX[i + 1], &VY[i + 1], &VZ[i + 1], | |
248 | &VX[(i + 1)/2], &VY[(i + 1)/2], &VZ[(i + 1)/2]); | |
249 | } | |
250 | ||
251 | /* Now do the multiplication. We lag a window behind the cursor position | |
252 | * because of the scalar recoding we do. | |
253 | */ | |
254 | f25519_set(&TX, 0); f25519_set(&TY, 1); f25519_set(&TZ, 1); | |
255 | for (i = NPIECE, w = 0, m_neg = 0; i--; ) { | |
256 | ni = n[i]; | |
257 | ||
258 | /* Work through each window in the scalar piece. */ | |
259 | for (j = 0; j < PIECEWD; j += WINWD) { | |
260 | ||
261 | /* Shift along by a window. */ | |
262 | for (k = 0; k < WINWD; k++) ptdbl(&TX, &TY, &TZ, &TX, &TY, &TZ); | |
263 | ||
264 | /* Peek at the next window of four bits. If the top bit is set we lend | |
265 | * a bit leftwards, into w. It's too late for this to affect the sign | |
266 | * now, but if we negated earlier then the addition would be wrong. | |
267 | */ | |
268 | w += (ni >> (PIECEWD - 1))&0x1u; | |
269 | w = ((WINLIM - w)&m_neg) | (w&~m_neg); | |
270 | ||
271 | /* Collect the entry from the table, and add or subtract. */ | |
272 | f25519_pickn(&UX, VX, TABSZ, w); | |
273 | f25519_pickn(&UY, VY, TABSZ, w); | |
274 | f25519_pickn(&UZ, VZ, TABSZ, w); | |
275 | f25519_condneg(&UX, &UX, m_neg); | |
276 | ptadd(&TX, &TY, &TZ, &TX, &TY, &TZ, &UX, &UY, &UZ); | |
277 | ||
278 | /* Move the next window into the delay slot. If its top bit is set, | |
279 | * then negate it and set m_neg. | |
280 | */ | |
281 | w = (ni >> (PIECEWD - WINWD))&WINMASK; | |
282 | m_neg = -(uint32)((w >> (WINWD - 1))&0x1u); | |
283 | ni <<= WINWD; | |
284 | } | |
285 | } | |
286 | ||
287 | /* Do the final window. Just fix the sign and go. */ | |
288 | for (k = 0; k < WINWD; k++) ptdbl(&TX, &TY, &TZ, &TX, &TY, &TZ); | |
289 | w = ((WINLIM - w)&m_neg) | (w&~m_neg); | |
290 | f25519_pickn(&UX, VX, TABSZ, w); | |
291 | f25519_pickn(&UY, VY, TABSZ, w); | |
292 | f25519_pickn(&UZ, VZ, TABSZ, w); | |
293 | f25519_condneg(&UX, &UX, m_neg); | |
294 | ptadd(X, Y, Z, &TX, &TY, &TZ, &UX, &UY, &UZ); | |
295 | ||
296 | #undef WINWD | |
297 | #undef WINLIM | |
298 | #undef WINMASK | |
299 | #undef TABSZ | |
300 | } | |
301 | ||
302 | static void ptsimmul(f25519 *X, f25519 *Y, f25519 *Z, | |
303 | const scaf_piece n0[NPIECE], | |
304 | const f25519 *X0, const f25519 *Y0, const f25519 *Z0, | |
305 | const scaf_piece n1[NPIECE], | |
306 | const f25519 *X1, const f25519 *Y1, const f25519 *Z1) | |
307 | { | |
308 | /* We assume that the window width divides the scalar piece width. */ | |
309 | #define WINWD 2 | |
310 | #define WINLIM (1 << WINWD) | |
311 | #define WINMASK (WINLIM - 1) | |
312 | #define TABSZ (1 << 2*WINWD) | |
313 | ||
314 | f25519 VX[TABSZ], VY[TABSZ], VZ[TABSZ]; | |
315 | f25519 TX, TY, TZ, UX, UY, UZ; | |
316 | unsigned i, j, k, w, ni0, ni1; | |
317 | ||
318 | /* Build a table of small linear combinations. */ | |
319 | f25519_set(&VX[0], 0); f25519_set(&VY[0], 1); f25519_set(&VZ[0], 1); | |
320 | VX[1] = *X0; VX[WINLIM] = *X1; | |
321 | VY[1] = *Y0; VY[WINLIM] = *Y1; | |
322 | VZ[1] = *Z0; VZ[WINLIM] = *Z1; | |
323 | for (i = 2; i < WINLIM; i <<= 1) { | |
324 | ptdbl(&VX[i], &VY[i], &VZ[i], | |
325 | &VX[i/2], &VY[i/2], &VZ[i/2]); | |
326 | ptdbl(&VX[i*WINLIM], &VY[i*WINLIM], &VZ[i*WINLIM], | |
327 | &VX[i*WINLIM/2], &VY[i*WINLIM/2], &VZ[i*WINLIM/2]); | |
328 | } | |
329 | for (i = 2; i < TABSZ; i <<= 1) { | |
330 | for (j = 1; j < i; j++) | |
331 | ptadd(&VX[i + j], &VY[i + j], &VZ[i + j], | |
332 | &VX[i], &VY[i], &VZ[i], &VX[j], &VY[j], &VZ[j]); | |
333 | } | |
334 | ||
335 | /* Do the multiplication. */ | |
336 | f25519_set(&TX, 0); f25519_set(&TY, 1); f25519_set(&TZ, 1); | |
337 | for (i = NPIECE; i--; ) { | |
338 | ni0 = n0[i]; ni1 = n1[i]; | |
339 | ||
340 | /* Work through each window in the scalar pieces. */ | |
341 | for (j = 0; j < PIECEWD; j += WINWD) { | |
342 | ||
343 | /* Shift along by a window. */ | |
344 | for (k = 0; k < WINWD; k++) ptdbl(&TX, &TY, &TZ, &TX, &TY, &TZ); | |
345 | ||
346 | /* Collect the next window from the scalars. */ | |
347 | w = ((ni0 >> (PIECEWD - WINWD))&WINMASK) | | |
348 | ((ni1 >> (PIECEWD - 2*WINWD))&(WINMASK << WINWD)); | |
349 | ni0 <<= WINWD; ni1 <<= WINWD; | |
350 | ||
351 | /* Collect the entry from the table, and add. */ | |
352 | f25519_pickn(&UX, VX, TABSZ, w); | |
353 | f25519_pickn(&UY, VY, TABSZ, w); | |
354 | f25519_pickn(&UZ, VZ, TABSZ, w); | |
355 | ptadd(&TX, &TY, &TZ, &TX, &TY, &TZ, &UX, &UY, &UZ); | |
356 | } | |
357 | } | |
358 | ||
359 | /* Done. */ | |
360 | *X = TX; *Y = TY; *Z = TZ; | |
361 | } | |
362 | ||
363 | /*----- Key derivation utilities ------------------------------------------*/ | |
364 | ||
365 | static void unpack_key(scaf_piece a[NPIECE], octet h1[32], | |
366 | const octet *k, size_t ksz) | |
367 | { | |
368 | sha512_ctx h; | |
369 | octet b[SHA512_HASHSZ]; | |
370 | ||
371 | sha512_init(&h); sha512_hash(&h, k, ksz); sha512_done(&h, b); | |
372 | b[0] &= 0xf8u; b[31] = (b[31]&0x3f) | 0x40; | |
373 | scaf_load(a, b, 32, NPIECE, PIECEWD); | |
374 | memcpy(h1, b + 32, 32); | |
375 | } | |
376 | ||
377 | /*----- Main code ---------------------------------------------------------*/ | |
378 | ||
379 | /* --- @ed25519_pubkey@ --- * | |
380 | * | |
381 | * Arguments: @octet K[ED25519_PUBSZ]@ = where to put the public key | |
382 | * @const void *k@ = private key | |
383 | * @size_t ksz@ = length of private key | |
384 | * | |
385 | * Returns: --- | |
386 | * | |
387 | * Use: Derives the public key from a private key. | |
388 | */ | |
389 | ||
390 | void ed25519_pubkey(octet K[ED25519_PUBSZ], const void *k, size_t ksz) | |
391 | { | |
392 | scaf_piece a[NPIECE]; | |
393 | f25519 AX, AY, AZ; | |
394 | octet h1[32]; | |
395 | ||
396 | unpack_key(a, h1, k, ksz); | |
397 | ptmul(&AX, &AY, &AZ, a, BX, BY, BZ); | |
398 | ptencode(K, &AX, &AY, &AZ); | |
399 | } | |
400 | ||
401 | /* --- @ed25519_sign@ --- * | |
402 | * | |
403 | * Arguments: @octet sig[ED25519_SIGSZ]@ = where to put the signature | |
404 | * @const void *k@ = private key | |
405 | * @size_t ksz@ = length of private key | |
406 | * @const octet K[ED25519_PUBSZ]@ = public key | |
407 | * @const void *m@ = message to sign | |
408 | * @size_t msz@ = length of message | |
409 | * | |
410 | * Returns: --- | |
411 | * | |
412 | * Use: Signs a message. | |
413 | */ | |
414 | ||
415 | void ed25519_sign(octet sig[ED25519_SIGSZ], | |
416 | const void *k, size_t ksz, | |
417 | const octet K[ED25519_PUBSZ], | |
418 | const void *m, size_t msz) | |
419 | { | |
420 | sha512_ctx h; | |
421 | scaf_piece a[NPIECE], r[NPIECE], t[NPIECE], scratch[3*NPIECE + 1]; | |
422 | scaf_dblpiece tt[2*NPIECE]; | |
423 | f25519 RX, RY, RZ; | |
424 | octet h1[32], b[SHA512_HASHSZ]; | |
425 | unsigned i; | |
426 | ||
427 | /* Get my private key. */ | |
428 | unpack_key(a, h1, k, ksz); | |
429 | ||
430 | /* Select the nonce and the vector part. */ | |
431 | sha512_init(&h); | |
432 | sha512_hash(&h, h1, 32); | |
433 | sha512_hash(&h, m, msz); | |
434 | sha512_done(&h, b); | |
435 | scaf_loaddbl(tt, b, 64, 2*NPIECE, PIECEWD); | |
436 | scaf_reduce(r, tt, l, mu, NPIECE, PIECEWD, scratch); | |
437 | ptmul(&RX, &RY, &RZ, r, BX, BY, BZ); | |
438 | ptencode(sig, &RX, &RY, &RZ); | |
439 | ||
440 | /* Calculate the scalar part. */ | |
441 | sha512_init(&h); | |
442 | sha512_hash(&h, sig, 32); | |
443 | sha512_hash(&h, K, 32); | |
444 | sha512_hash(&h, m, msz); | |
445 | sha512_done(&h, b); | |
446 | scaf_loaddbl(tt, b, 64, 2*NPIECE, PIECEWD); | |
447 | scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch); | |
448 | scaf_mul(tt, t, a, NPIECE); | |
449 | for (i = 0; i < NPIECE; i++) tt[i] += r[i]; | |
450 | scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch); | |
451 | scaf_store(sig + 32, 32, t, NPIECE, PIECEWD); | |
452 | } | |
453 | ||
454 | /* --- @ed25519_verify@ --- * | |
455 | * | |
456 | * Arguments: @const octet K[ED25519_PUBSZ]@ = public key | |
457 | * @const void *m@ = message to sign | |
458 | * @size_t msz@ = length of message | |
459 | * @const octet sig[ED25519_SIGSZ]@ = signature | |
460 | * | |
461 | * Returns: Zero if OK, negative on failure. | |
462 | * | |
463 | * Use: Verify a signature. | |
464 | */ | |
465 | ||
466 | int ed25519_verify(const octet K[ED25519_PUBSZ], | |
467 | const void *m, size_t msz, | |
468 | const octet sig[ED25519_SIGSZ]) | |
469 | { | |
470 | sha512_ctx h; | |
471 | scaf_piece s[NPIECE], t[NPIECE], scratch[3*NPIECE + 1]; | |
472 | scaf_dblpiece tt[2*NPIECE]; | |
473 | f25519 AX, AY, AZ, RX, RY, RZ; | |
474 | octet b[SHA512_HASHSZ]; | |
475 | ||
476 | /* Unpack the public key. Negate it: we're meant to subtract the term | |
477 | * involving the public key point, and this is easier than negating the | |
478 | * scalar. | |
479 | */ | |
480 | if (ptdecode(&AX, &AY, &AZ, K)) return (-1); | |
481 | f25519_neg(&AX, &AX); | |
482 | ||
483 | /* Check the signature. */ | |
484 | sha512_init(&h); | |
485 | sha512_hash(&h, sig, 32); | |
486 | sha512_hash(&h, K, 32); | |
487 | sha512_hash(&h, m, msz); | |
488 | sha512_done(&h, b); | |
489 | scaf_load(s, sig + 32, 32, NPIECE, PIECEWD); | |
490 | scaf_loaddbl(tt, b, 64, 2*NPIECE, PIECEWD); | |
491 | scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch); | |
492 | ptsimmul(&RX, &RY, &RZ, s, BX, BY, BZ, t, &AX, &AY, &AZ); | |
493 | ptencode(b, &RX, &RY, &RZ); | |
494 | if (memcmp(b, sig, 32) != 0) return (-1); | |
495 | ||
496 | /* All is good. */ | |
497 | return (0); | |
498 | } | |
499 | ||
500 | /*----- Test rig ----------------------------------------------------------*/ | |
501 | ||
502 | #ifdef TEST_RIG | |
503 | ||
504 | #include <stdio.h> | |
505 | #include <string.h> | |
506 | ||
507 | #include <mLib/report.h> | |
508 | #include <mLib/testrig.h> | |
509 | ||
510 | static int vrf_pubkey(dstr dv[]) | |
511 | { | |
512 | dstr dpub = DSTR_INIT; | |
513 | int ok = 1; | |
514 | ||
515 | if (dv[1].len != 32) die(1, "bad pub length"); | |
516 | ||
517 | dstr_ensure(&dpub, 32); dpub.len = 32; | |
518 | ed25519_pubkey((octet *)dpub.buf, dv[0].buf, dv[0].len); | |
519 | if (memcmp(dpub.buf, dv[1].buf, 64) != 0) { | |
520 | ok = 0; | |
521 | fprintf(stderr, "failed!"); | |
522 | fprintf(stderr, "\n\tpriv = "); type_hex.dump(&dv[0], stderr); | |
523 | fprintf(stderr, "\n\tcalc = "); type_hex.dump(&dpub, stderr); | |
524 | fprintf(stderr, "\n\twant = "); type_hex.dump(&dv[1], stderr); | |
525 | fprintf(stderr, "\n"); | |
526 | } | |
527 | ||
528 | dstr_destroy(&dpub); | |
529 | return (ok); | |
530 | } | |
531 | ||
532 | static int vrf_sign(dstr dv[]) | |
533 | { | |
534 | octet K[ED25519_PUBSZ]; | |
535 | dstr dsig = DSTR_INIT; | |
536 | int ok = 1; | |
537 | ||
538 | if (dv[2].len != 64) die(1, "bad result length"); | |
539 | ||
540 | dstr_ensure(&dsig, 64); dsig.len = 64; | |
541 | ed25519_pubkey(K, dv[0].buf, dv[0].len); | |
542 | ed25519_sign((octet *)dsig.buf, dv[0].buf, dv[0].len, K, | |
543 | dv[1].buf, dv[1].len); | |
544 | if (memcmp(dsig.buf, dv[2].buf, 64) != 0) { | |
545 | ok = 0; | |
546 | fprintf(stderr, "failed!"); | |
547 | fprintf(stderr, "\n\tpriv = "); type_hex.dump(&dv[0], stderr); | |
548 | fprintf(stderr, "\n\t msg = "); type_hex.dump(&dv[1], stderr); | |
549 | fprintf(stderr, "\n\tcalc = "); type_hex.dump(&dsig, stderr); | |
550 | fprintf(stderr, "\n\twant = "); type_hex.dump(&dv[2], stderr); | |
551 | fprintf(stderr, "\n"); | |
552 | } | |
553 | ||
554 | dstr_destroy(&dsig); | |
555 | return (ok); | |
556 | } | |
557 | ||
558 | static int vrf_verify(dstr dv[]) | |
559 | { | |
560 | int rc_want, rc_calc; | |
561 | int ok = 1; | |
562 | ||
563 | if (dv[0].len != 32) die(1, "bad pub length"); | |
564 | if (dv[2].len != 64) die(1, "bad sig length"); | |
565 | rc_want = *(int *)dv[3].buf; | |
566 | ||
567 | rc_calc = ed25519_verify((const octet *)dv[0].buf, | |
568 | dv[1].buf, dv[1].len, | |
569 | (const octet *)dv[2].buf); | |
570 | if (!rc_want != !rc_calc) { | |
571 | ok = 0; | |
572 | fprintf(stderr, "failed!"); | |
573 | fprintf(stderr, "\n\t pub = "); type_hex.dump(&dv[0], stderr); | |
574 | fprintf(stderr, "\n\t msg = "); type_hex.dump(&dv[1], stderr); | |
575 | fprintf(stderr, "\n\t sig = "); type_hex.dump(&dv[2], stderr); | |
576 | fprintf(stderr, "\n\tcalc = %d", rc_calc); | |
577 | fprintf(stderr, "\n\twant = %d", rc_want); | |
578 | fprintf(stderr, "\n"); | |
579 | } | |
580 | ||
581 | return (ok); | |
582 | } | |
583 | ||
584 | static test_chunk tests[] = { | |
585 | { "pubkey", vrf_pubkey, { &type_hex, &type_hex } }, | |
586 | { "sign", vrf_sign, { &type_hex, &type_hex, &type_hex } }, | |
587 | { "verify", vrf_verify, { &type_hex, &type_hex, &type_hex, &type_int } }, | |
588 | { 0, 0, { 0 } } | |
589 | }; | |
590 | ||
591 | int main(int argc, char *argv[]) | |
592 | { | |
593 | test_run(argc, argv, tests, SRCDIR "/t/ed25519"); | |
594 | return (0); | |
595 | } | |
596 | ||
597 | #endif | |
598 | ||
599 | /*----- That's all, folks -------------------------------------------------*/ |