Commit | Line | Data |
---|---|---|
a1a6042e 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 secnet. | |
11 | * See README for full list of copyright holders. | |
12 | * | |
13 | * secnet is free software; you can redistribute it and/or modify it | |
14 | * under the terms of the GNU General Public License as published by | |
15 | * the Free Software Foundation; either version d of the License, or | |
16 | * (at your option) any later version. | |
17 | * | |
18 | * secnet is distributed in the hope that it will be useful, but | |
19 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
20 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
21 | * General Public License for more details. | |
22 | * | |
23 | * You should have received a copy of the GNU General Public License | |
24 | * version 3 along with secnet; if not, see | |
25 | * https://www.gnu.org/licenses/gpl.html. | |
26 | * | |
27 | * This file was originally part of Catacomb, but has been automatically | |
28 | * modified for incorporation into secnet: see `import-catacomb-crypto' | |
29 | * for details. | |
30 | * | |
31 | * Catacomb is free software; you can redistribute it and/or modify | |
32 | * it under the terms of the GNU Library General Public License as | |
33 | * published by the Free Software Foundation; either version 2 of the | |
34 | * License, or (at your option) any later version. | |
35 | * | |
36 | * Catacomb is distributed in the hope that it will be useful, | |
37 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
38 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
39 | * GNU Library General Public License for more details. | |
40 | * | |
41 | * You should have received a copy of the GNU Library General Public | |
42 | * License along with Catacomb; if not, write to the Free | |
43 | * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, | |
44 | * MA 02111-1307, USA. | |
45 | */ | |
46 | ||
47 | /*----- Header files ------------------------------------------------------*/ | |
48 | ||
49 | #include <string.h> | |
50 | ||
51 | #include "f25519.h" | |
52 | #include "ed25519.h" | |
53 | #include "scaf.h" | |
54 | #include "scmul.h" | |
55 | #include "sha512.h" | |
56 | ||
57 | /*----- A number of magic numbers -----------------------------------------*/ | |
58 | ||
59 | # define PIECEWD 24 | |
60 | static const scaf_piece l[] = { | |
61 | 0xf5d3ed, 0x631a5c, 0xd65812, 0xa2f79c, 0xdef9de, 0x000014, | |
62 | 0x000000, 0x000000, 0x000000, 0x000000, 0x001000 | |
63 | }; | |
64 | static const scaf_piece mu[] = { | |
65 | 0x1b3994, 0x0a2c13, 0x9ce5a3, 0x29a7ed, 0x5d0863, 0x210621, | |
66 | 0xffffeb, 0xffffff, 0xffffff, 0xffffff, 0xffffff, 0x000fff | |
67 | }; | |
68 | ||
69 | #define NPIECE SCAF_NPIECE(255, PIECEWD) | |
70 | ||
71 | # define P p26 | |
72 | static const f25519_piece bx_pieces[] = { | |
73 | -14297830, -7645148, 16144683, -16471763, 27570974, | |
74 | -2696100, -26142465, 8378389, 20764389, 8758491 | |
75 | }, by_pieces[] = { | |
76 | -26843541, -6710886, 13421773, -13421773, 26843546, | |
77 | 6710886, -13421773, 13421773, -26843546, -6710886 | |
78 | }, d_pieces[] = { | |
79 | -10913610, 13857413, -15372611, 6949391, 114729, | |
80 | -8787816, -6275908, -3247719, -18696448, -12055116 | |
81 | }; | |
82 | ||
83 | static const f25519_piece bz_pieces[NPIECE] = { 1, 0, /* ... */ }; | |
84 | #define BX ((const f25519 *)bx_pieces) | |
85 | #define BY ((const f25519 *)by_pieces) | |
86 | #define BZ ((const f25519 *)bz_pieces) | |
87 | #define D ((const f25519 *)d_pieces) | |
88 | ||
89 | /*----- Point encoding and decoding ---------------------------------------*/ | |
90 | ||
91 | static void ptencode(octet q[32], | |
92 | const f25519 *X, const f25519 *Y, const f25519 *Z) | |
93 | { | |
94 | f25519 x, y, t; | |
95 | octet b[32]; | |
96 | ||
97 | f25519_inv(&t, Z); f25519_mul(&x, X, &t); f25519_mul(&y, Y, &t); | |
98 | f25519_store(q, &y); f25519_store(b, &x); q[31] |= (b[0]&1u) << 7; | |
99 | } | |
100 | ||
101 | static int ptdecode(f25519 *X, f25519 *Y, f25519 *Z, const octet q[32]) | |
102 | { | |
103 | octet b[32]; | |
104 | unsigned i, a; | |
105 | f25519 t, u; | |
106 | uint32 m; | |
107 | int rc = 0; | |
108 | ||
109 | /* Load the y-coordinate. */ | |
110 | memcpy(b, q, 32); b[31] &= 0x7fu; f25519_load(Y, b); | |
111 | ||
112 | /* Check that the coordinate was in range. If we store it, we'll get a | |
113 | * canonical version which we can compare against Q; be careful not to | |
114 | * check the top bit. | |
115 | */ | |
116 | f25519_store(b, Y); | |
117 | for (i = a = 0; i < 31; i++) a |= b[i] ^ q[i]; | |
118 | a |= (b[31] ^ q[31])&0x7fu; | |
119 | a = ((a - 1) >> 8)&0x01u; /* 0 |-> 1, non-0 |-> 0 */ | |
120 | rc |= (int)a - 1; | |
121 | ||
122 | /* Decompress the x-coordinate. */ | |
123 | f25519_sqr(&t, Y); f25519_mul(&u, &t, D); t.P[0] -= 1; u.P[0] += 1; | |
124 | rc |= f25519_quosqrt(X, &t, &u); | |
125 | f25519_store(b, X); m = -(uint32)(((q[31] >> 7) ^ b[0])&0x1u); | |
126 | f25519_condneg(X, X, m); | |
127 | ||
128 | /* Set Z. */ | |
129 | f25519_set(Z, 1); | |
130 | ||
131 | /* And we're done. */ | |
132 | return (rc); | |
133 | } | |
134 | ||
135 | /*----- Edwards curve arithmetic ------------------------------------------*/ | |
136 | ||
137 | static void ptadd(f25519 *X, f25519 *Y, f25519 *Z, | |
138 | const f25519 *X0, const f25519 *Y0, const f25519 *Z0, | |
139 | const f25519 *X1, const f25519 *Y1, const f25519 *Z1) | |
140 | { | |
141 | f25519 t0, t1, t2, t3; | |
142 | ||
143 | /* Bernstein, Birkner, Joye, Lange, and Peters, `Twisted Edwards Curves', | |
144 | * 2008-03-13, https://cr.yp.to/newelliptic/twisted-20080313.pdf shows the | |
145 | * formulae as: | |
146 | * | |
147 | * A = Z1 Z2; B = A^2; C = X1 X2; D = Y1 Y2; | |
148 | * E = d C D; F = B - E; G = B + E; | |
149 | * X3 = A F ((X1 + Y1) (X2 + Y2) - C - D); | |
150 | * Y3 = A G (D - a C); Z3 = F G. | |
151 | * | |
152 | * Note that a = -1, which things easier. | |
153 | */ | |
154 | ||
155 | f25519_mul(&t0, Z0, Z1); /* t0 = A = Z0 Z1 */ | |
156 | f25519_add(&t1, X0, Y0); /* t1 = X0 + Y0 */ | |
157 | f25519_add(&t2, X1, Y1); /* t2 = X1 + Y1 */ | |
158 | f25519_mul(&t1, &t1, &t2); /* t1 = (X0 + Y0) (X1 + Y1) */ | |
159 | f25519_mul(&t2, X0, X1); /* t2 = C = X0 X1 */ | |
160 | f25519_mul(&t3, Y0, Y1); /* t3 = D = Y0 Y1 */ | |
161 | f25519_add(Y, &t2, &t3); /* Y = C + D = D - a C */ | |
162 | f25519_sub(X, &t1, Y); /* X = (X0 + Y0) (X1 + Y1) - C - D */ | |
163 | f25519_mul(X, X, &t0); /* X = A ((X0 + Y0) (X1 + Y1) - C - D) */ | |
164 | f25519_mul(Y, Y, &t0); /* Y = A (D - a C) */ | |
165 | f25519_sqr(&t0, &t0); /* t0 = B = A^2 */ | |
166 | f25519_mul(&t1, &t2, &t3); /* t1 = C D */ | |
167 | f25519_mul(&t1, &t1, D); /* t1 = E = d C D */ | |
168 | f25519_sub(&t2, &t0, &t1); /* t2 = F = B - E */ | |
169 | f25519_add(&t1, &t0, &t1); /* t1 = G = B + E */ | |
170 | f25519_mul(X, X, &t2); /* X = A F ((X0 + Y0) (X1 + Y1) - C - D) */ | |
171 | f25519_mul(Y, Y, &t1); /* Y = A G (D - a C) */ | |
172 | f25519_mul(Z, &t1, &t2); /* Z = F G */ | |
173 | } | |
174 | ||
175 | static void ptdbl(f25519 *X, f25519 *Y, f25519 *Z, | |
176 | const f25519 *X0, const f25519 *Y0, const f25519 *Z0) | |
177 | { | |
178 | f25519 t0, t1, t2; | |
179 | ||
180 | /* Bernstein, Birkner, Joye, Lange, and Peters, `Twisted Edwards Curves', | |
181 | * 2008-03-13, https://cr.yp.to/newelliptic/twisted-20080313.pdf shows the | |
182 | * formulae as: | |
183 | * | |
184 | * B = (X1 + Y1)^2; C = X1^2; D = Y1^2; E = a C; | |
185 | * F = E + D; H = Z1^2; J = F - 2 H; | |
186 | * X3 = (B - C - D) J; Y3 = F (E - D); Z3 = F J. | |
187 | * | |
188 | * Note that a = -1, which things easier. | |
189 | */ | |
190 | ||
191 | f25519_add(&t0, X0, Y0); /* t0 = X0 + Y0 */ | |
192 | f25519_sqr(&t0, &t0); /* t0 = B = (X0 + Y0)^2 */ | |
193 | f25519_sqr(&t1, X0); /* t1 = C = X0^2 */ | |
194 | f25519_sqr(&t2, Y0); /* t2 = D = Y0^2 */ | |
195 | f25519_add(Y, &t1, &t2); /* Y = C + D = -(E - D) */ | |
196 | f25519_sub(X, &t0, Y); /* X = B - C - D */ | |
197 | /* (E = a C = -C) */ | |
198 | f25519_sub(&t0, &t2, &t1); /* t0 = F = D - C = E + D */ | |
199 | f25519_sqr(&t1, Z0); /* t1 = H = Z0^2 */ | |
200 | f25519_add(&t1, &t1, &t1); /* t1 = 2 H */ | |
201 | f25519_sub(&t1, &t0, &t1); /* t1 = J = F - 2 H */ | |
202 | f25519_mul(X, X, &t1); /* X = (B - C - D) J */ | |
203 | f25519_mul(Y, Y, &t0); /* Y = -F (E - D) */ | |
204 | f25519_neg(Y, Y); /* Y = F (E - D) */ | |
205 | f25519_mul(Z, &t0, &t1); /* Z = F J */ | |
206 | } | |
207 | ||
208 | static DEFINE_SCMUL(ptmul, f25519, 4, PIECEWD, NPIECE, ptadd, ptdbl) | |
209 | static DEFINE_SCSIMMUL(ptsimmul, f25519, 2, PIECEWD, NPIECE, ptadd, ptdbl) | |
210 | ||
211 | /*----- Key derivation utilities ------------------------------------------*/ | |
212 | ||
213 | static void unpack_key(scaf_piece a[NPIECE], octet h1[32], | |
214 | const octet *k, size_t ksz) | |
215 | { | |
216 | struct sha512_ctx h; | |
217 | octet b[SHA512_DIGEST_SIZE]; | |
218 | ||
219 | sha512_init_ctx(&h); sha512_process_bytes(k, ksz, &h); sha512_finish_ctx(&h, b); | |
220 | b[0] &= 0xf8u; b[31] = (b[31]&0x3f) | 0x40; | |
221 | scaf_load(a, b, 32, NPIECE, PIECEWD); | |
222 | if (h1) memcpy(h1, b + 32, 32); | |
223 | } | |
224 | ||
225 | #define PREFIX_BUFSZ 290 | |
226 | static size_t prefix(octet b[PREFIX_BUFSZ], | |
227 | int phflag, const octet *p, size_t psz) | |
228 | { | |
229 | if (phflag < 0) return (0); | |
230 | memcpy(b, "SigEd25519 no Ed25519 collisions", 32); | |
231 | b[32] = phflag; | |
232 | assert(psz < ED25519_MAXPERSOSZ); b[33] = psz; memcpy(b + 34, p, psz); | |
233 | return (psz + 34); | |
234 | } | |
235 | ||
236 | /*----- Main code ---------------------------------------------------------*/ | |
237 | ||
238 | /* --- @ed25519_pubkey@ --- * | |
239 | * | |
240 | * Arguments: @octet K[ED25519_PUBSZ]@ = where to put the public key | |
241 | * @const void *k@ = private key | |
242 | * @size_t ksz@ = length of private key | |
243 | * | |
244 | * Returns: --- | |
245 | * | |
246 | * Use: Derives the public key from a private key. | |
247 | */ | |
248 | ||
249 | void ed25519_pubkey(octet K[ED25519_PUBSZ], const void *k, size_t ksz) | |
250 | { | |
251 | scaf_piece a[NPIECE]; | |
252 | f25519 AX, AY, AZ; | |
253 | ||
254 | unpack_key(a, 0, k, ksz); | |
255 | ptmul(&AX, &AY, &AZ, a, BX, BY, BZ); | |
256 | ptencode(K, &AX, &AY, &AZ); | |
257 | } | |
258 | ||
259 | /* --- @ed25519_sign@, @ed25519ctx_sign@ --- * | |
260 | * | |
261 | * Arguments: @octet sig[ED25519_SIGSZ]@ = where to put the signature | |
262 | * @const void *k@ = private key | |
263 | * @size_t ksz@ = length of private key | |
264 | * @const octet K[ED25519_PUBSZ]@ = public key | |
265 | * @int phflag@ = whether the `message' has been hashed already | |
266 | * @const void *p@ = personalization string | |
267 | * @size_t psz@ = length of personalization string | |
268 | * @const void *m@ = message to sign | |
269 | * @size_t msz@ = length of message | |
270 | * | |
271 | * Returns: --- | |
272 | * | |
273 | * Use: Signs a message. | |
274 | * | |
275 | * In @ed25519ctx_sign@, if @phflag@ is @-1@ then you get plain | |
276 | * old Ed25519: the personalization string pointer @p@ will be | |
277 | * ignored. If @phflag > 0@ then the `message' @m@ should be a | |
278 | * SHA512 hash of the actual message. | |
279 | */ | |
280 | ||
281 | void ed25519ctx_sign(octet sig[ED25519_SIGSZ], | |
282 | const void *k, size_t ksz, const octet K[ED25519_PUBSZ], | |
283 | int phflag, const void *p, size_t psz, | |
284 | const void *m, size_t msz) | |
285 | { | |
286 | struct sha512_ctx h; | |
287 | scaf_piece a[NPIECE], r[NPIECE], t[NPIECE], scratch[3*NPIECE]; | |
288 | scaf_dblpiece tt[2*NPIECE]; | |
289 | f25519 RX, RY, RZ; | |
290 | octet h1[32], pb[PREFIX_BUFSZ], rb[SHA512_DIGEST_SIZE]; | |
291 | unsigned i; | |
292 | ||
293 | /* Get my private key. */ | |
294 | unpack_key(a, h1, k, ksz); | |
295 | ||
296 | /* Determine the prefix string. */ | |
297 | psz = prefix(pb, phflag, p, psz); | |
298 | ||
299 | /* Select the nonce and the vector part. */ | |
300 | sha512_init_ctx(&h); | |
301 | sha512_process_bytes(pb, psz, &h); | |
302 | sha512_process_bytes(h1, 32, &h); | |
303 | sha512_process_bytes(m, msz, &h); | |
304 | sha512_finish_ctx(&h, rb); | |
305 | scaf_loaddbl(tt, rb, 64, 2*NPIECE, PIECEWD); | |
306 | scaf_reduce(r, tt, l, mu, NPIECE, PIECEWD, scratch); | |
307 | ptmul(&RX, &RY, &RZ, r, BX, BY, BZ); | |
308 | ptencode(sig, &RX, &RY, &RZ); | |
309 | ||
310 | /* Calculate the scalar part. */ | |
311 | sha512_init_ctx(&h); | |
312 | sha512_process_bytes(pb, psz, &h); | |
313 | sha512_process_bytes(sig, 32, &h); | |
314 | sha512_process_bytes(K, 32, &h); | |
315 | sha512_process_bytes(m, msz, &h); | |
316 | sha512_finish_ctx(&h, rb); | |
317 | scaf_loaddbl(tt, rb, 64, 2*NPIECE, PIECEWD); | |
318 | scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch); | |
319 | scaf_mul(tt, t, a, NPIECE); | |
320 | for (i = 0; i < NPIECE; i++) tt[i] += r[i]; | |
321 | scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch); | |
322 | scaf_store(sig + 32, 32, t, NPIECE, PIECEWD); | |
323 | } | |
324 | ||
325 | void ed25519_sign(octet sig[ED25519_SIGSZ], | |
326 | const void *k, size_t ksz, const octet K[ED25519_PUBSZ], | |
327 | const void *m, size_t msz) | |
328 | { ed25519ctx_sign(sig, k, ksz, K, -1, 0, 0, m, msz); } | |
329 | ||
330 | /* --- @ed25519_verify@, @ed25519ctx_verify@ --- * | |
331 | * | |
332 | * Arguments: @const octet K[ED25519_PUBSZ]@ = public key | |
333 | * @int phflag@ = whether the `message' has been hashed already | |
334 | * @const void *p@ = personalization string | |
335 | * @size_t psz@ = length of personalization string | |
336 | * @const void *m@ = message to sign | |
337 | * @size_t msz@ = length of message | |
338 | * @const octet sig[ED25519_SIGSZ]@ = signature | |
339 | * | |
340 | * Returns: Zero if OK, negative on failure. | |
341 | * | |
342 | * Use: Verify a signature. | |
343 | * | |
344 | * In @ed25519ctx_verify@, if @phflag@ is @-1@ then you get | |
345 | * plain old Ed25519: the personalization string pointer @p@ | |
346 | * will be ignored. If @phflag > 0@ then the `message' @m@ | |
347 | * should be a SHA512 hash of the actual message. | |
348 | */ | |
349 | ||
350 | int ed25519ctx_verify(const octet K[ED25519_PUBSZ], | |
351 | int phflag, const void *p, size_t psz, | |
352 | const void *m, size_t msz, | |
353 | const octet sig[ED25519_SIGSZ]) | |
354 | { | |
355 | struct sha512_ctx h; | |
356 | scaf_piece s[NPIECE], t[NPIECE], scratch[3*NPIECE]; | |
357 | scaf_dblpiece tt[2*NPIECE]; | |
358 | f25519 AX, AY, AZ, RX, RY, RZ; | |
359 | octet b[PREFIX_BUFSZ]; | |
360 | ||
361 | /* Unpack the public key. Negate it: we're meant to subtract the term | |
362 | * involving the public key point, and this is easier than negating the | |
363 | * scalar. | |
364 | */ | |
365 | if (ptdecode(&AX, &AY, &AZ, K)) return (-1); | |
366 | f25519_neg(&AX, &AX); | |
367 | ||
368 | /* Load the scalar and check that it's in range. The easy way is to store | |
369 | * it again and see if the two match. | |
370 | */ | |
371 | scaf_loaddbl(tt, sig + 32, 32, 2*NPIECE, PIECEWD); | |
372 | scaf_reduce(s, tt, l, mu, NPIECE, PIECEWD, scratch); | |
373 | scaf_store(b, 32, s, NPIECE, PIECEWD); | |
374 | if (memcmp(b, sig + 32, 32) != 0) return (-1); | |
375 | ||
376 | /* Check the signature. */ | |
377 | psz = prefix(b, phflag, p, psz); | |
378 | sha512_init_ctx(&h); | |
379 | sha512_process_bytes(b, psz, &h); | |
380 | sha512_process_bytes(sig, 32, &h); | |
381 | sha512_process_bytes(K, 32, &h); | |
382 | sha512_process_bytes(m, msz, &h); | |
383 | sha512_finish_ctx(&h, b); | |
384 | scaf_loaddbl(tt, b, 64, 2*NPIECE, PIECEWD); | |
385 | scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch); | |
386 | ptsimmul(&RX, &RY, &RZ, s, BX, BY, BZ, t, &AX, &AY, &AZ); | |
387 | ptencode(b, &RX, &RY, &RZ); | |
388 | if (memcmp(b, sig, 32) != 0) return (-1); | |
389 | ||
390 | /* All is good. */ | |
391 | return (0); | |
392 | } | |
393 | ||
394 | int ed25519_verify(const octet K[ED25519_PUBSZ], | |
395 | const void *m, size_t msz, | |
396 | const octet sig[ED25519_SIGSZ]) | |
397 | { return (ed25519ctx_verify(K, -1, 0, 0, m, msz, sig)); } | |
398 | ||
399 | /*----- That's all, folks -------------------------------------------------*/ |