]> pd.if.org Git - zpackage/blob - crypto/libeddsa/lib/ed25519-sha512.c
remove stray debug fprintf
[zpackage] / crypto / libeddsa / lib / ed25519-sha512.c
1 /*
2  * implementing ed25519-sha512 from [1].
3  *
4  * This code is public domain.
5  *
6  * Philipp Lay <philipp.lay@illunis.net>
7  *
8  *
9  * References:
10  * [1] High-speed high-security signatures, 2011/09/26,
11  *     Bernstein, Duif, Lange, Schwabe, Yang
12  *
13  * TODO:
14  *   - batch verify
15  */
16
17 #include <stdint.h>
18 #include <stdbool.h>
19 #include <stddef.h>
20 #include <string.h>
21
22 #include "eddsa.h"
23
24 #include "sha512.h"
25 #include "sc.h"
26 #include "fld.h"
27 #include "ed.h"
28 #include "burnstack.h"
29
30
31 static void
32 ed25519_key_setup(uint8_t out[SHA512_HASH_LENGTH],
33                   const uint8_t sk[ED25519_KEY_LEN])
34 {
35         struct sha512 hash;
36
37         /* hash secret-key */
38         sha512_init(&hash);
39         sha512_add(&hash, sk, ED25519_KEY_LEN);
40         sha512_final(&hash, out);
41
42         /* delete bit 255 and set bit 254 */
43         out[31] &= 0x7f;
44         out[31] |= 0x40;
45         /* delete 3 lowest bits */
46         out[0] &= 0xf8;
47 }
48
49
50 /*
51  * genpub - derive public key from secret key
52  */
53 static void
54 genpub(uint8_t pub[ED25519_KEY_LEN], const uint8_t sec[ED25519_KEY_LEN])
55 {
56         uint8_t h[SHA512_HASH_LENGTH];
57         struct ed A;
58         sc_t a;
59
60         /* derive secret and import it */
61         ed25519_key_setup(h, sec);
62         sc_import(a, h, 32);
63
64         /* multiply with base point to calculate public key */
65         ed_scale_base(&A, a);
66         ed_export(pub, &A);
67 }
68
69
70 /*
71  * ed25519_genpub - stack-clearing wrapper for genpub
72  */
73 void
74 ed25519_genpub(uint8_t pub[ED25519_KEY_LEN], const uint8_t sec[ED25519_KEY_LEN])
75 {
76         genpub(pub, sec);
77         burnstack(2048);
78 }
79
80
81 /*
82  * sign - create ed25519 signature of data using secret key sec
83  */
84 static void
85 sign(uint8_t sig[ED25519_SIG_LEN],
86      const uint8_t sec[ED25519_KEY_LEN],
87      const uint8_t pub[ED25519_KEY_LEN],
88      const uint8_t *data, size_t len)
89 {
90         struct sha512 hash;
91         uint8_t h[SHA512_HASH_LENGTH];
92         
93         sc_t a, r, t, S;
94         struct ed R;
95
96         /* derive secret scalar a */
97         ed25519_key_setup(h, sec);
98         sc_import(a, h, 32);
99
100         /* hash next 32 bytes together with data to form r */
101         sha512_init(&hash);
102         sha512_add(&hash, h+32, 32);
103         sha512_add(&hash, data, len);
104         sha512_final(&hash, h);
105         sc_import(r, h, sizeof(h));
106
107         /* calculate R = r * B which form the first 256bit of the signature */
108         ed_scale_base(&R, r);
109         ed_export(sig, &R);
110         
111         /* calculate t := Hash(export(R), export(A), data) mod m */
112         sha512_init(&hash);
113         sha512_add(&hash, sig, 32);
114         sha512_add(&hash, pub, 32);
115         sha512_add(&hash, data, len);
116         sha512_final(&hash, h);
117         sc_import(t, h, sizeof(h));
118         
119         /* calculate S := r + t*a mod m and finish the signature */
120         sc_mul(S, t, a);
121         sc_add(S, r, S);
122         sc_export(sig+32, S);
123 }
124
125
126 /*
127  * ed25519_sign - stack-cleaning wrapper for sign
128  */
129 void
130 ed25519_sign(uint8_t sig[ED25519_SIG_LEN],
131            const uint8_t sec[ED25519_KEY_LEN],
132            const uint8_t pub[ED25519_KEY_LEN],
133            const uint8_t *data, size_t len)
134 {
135         sign(sig, sec, pub, data, len);
136         burnstack(4096);
137 }
138
139
140 /*
141  * ed25519_verify - verifies an ed25519-signature of given data.
142  *
143  * note: this functions runs in vartime and does no stack cleanup, since
144  * all information are considered public.
145  *
146  * returns true if signature is ok and false otherwise.
147  */
148 bool
149 ed25519_verify(const uint8_t sig[ED25519_SIG_LEN],
150                const uint8_t pub[ED25519_KEY_LEN],
151                const uint8_t *data, size_t len)
152 {
153         struct sha512 hash;
154         uint8_t h[SHA512_HASH_LENGTH];
155         struct ed A, C;
156         sc_t t, S;
157         uint8_t check[32];
158
159         /* import public key */
160         ed_import(&A, pub);
161
162         /* import S from second half of the signature */
163         sc_import(S, sig+32, 32);
164
165         /* calculate t := Hash(export(R), export(A), data) mod m */
166         sha512_init(&hash);
167         sha512_add(&hash, sig, 32);
168         sha512_add(&hash, pub, 32);
169         sha512_add(&hash, data, len);
170         sha512_final(&hash, h);
171         sc_import(t, h, 64);
172
173         /* verify signature (vartime!) */
174         fld_neg(A.x, A.x);
175         fld_neg(A.t, A.t);
176         ed_dual_scale(&C, S, t, &A);
177         ed_export(check, &C);
178         
179         /* is export(C) == export(R) (vartime!) */
180         return (memcmp(check, sig, 32) == 0);
181 }
182
183
184 /*
185  * pk_ed25519_to_x25519 - convert a ed25519 public key to x25519
186  */
187 void
188 pk_ed25519_to_x25519(uint8_t out[X25519_KEY_LEN], const uint8_t in[ED25519_KEY_LEN])
189 {
190         struct ed P;
191         fld_t u, t;
192
193         /* import ed25519 public key */
194         ed_import(&P, in);
195
196         /*
197          * We now have the point P = (x,y) on the curve
198          *
199          *      x^2 + y^2 = 1 + (121665/121666)x^2y^2
200          *
201          * and want the u-component of the corresponding point
202          * on the birationally equivalent montgomery curve
203          *
204          *      v^2 = u^3 + 486662 u^2 + u.
205          *
206          *
207          * From the paper [1] we get
208          *
209          *      y = (u - 1) / (u + 1),
210          *
211          * which immediately yields
212          *
213          *      u = (1 + y) / (1 - y)
214          *
215          * or, by using projective coordinantes,
216          *
217          *      u = (z + y) / (z - y).
218          */
219
220         /* u <- z + y */
221         fld_add(u, P.z, P.y);
222
223         /* t <- (z - y)^-1 */
224         fld_sub(t, P.z, P.y);
225         fld_inv(t, t);
226
227         /* u <- u * t = (z+y) / (z-y) */
228         fld_mul(u, u, t);
229
230         /* export curve25519 public key */
231         fld_export(out, u);
232 }
233
234
235
236 /*
237  * conv_sk_ed25519_to_x25519 - convert a ed25519 secret key to x25519 secret.
238  */
239 static void
240 conv_sk_ed25519_to_x25519(uint8_t out[X25519_KEY_LEN], const uint8_t in[ED25519_KEY_LEN])
241 {
242         uint8_t h[SHA512_HASH_LENGTH];
243         ed25519_key_setup(h, in);
244         memcpy(out, h, X25519_KEY_LEN);
245 }
246
247
248 /*
249  * sk_ed25519_to_x25519 - stack-clearing wrapper for conv_sk_ed25519_to_x25519.
250  */
251 void
252 sk_ed25519_to_x25519(uint8_t out[X25519_KEY_LEN], const uint8_t in[ED25519_KEY_LEN])
253 {
254         conv_sk_ed25519_to_x25519(out, in);
255         burnstack(1024);
256 }
257
258
259
260
261
262 /*
263  * Obsolete Interface, this will be removed in the future.
264  */
265
266
267 /*
268  * eddsa_genpub - stack-clearing wrapper for genpub (obsolete interface!)
269  */
270 void
271 eddsa_genpub(uint8_t pub[32], const uint8_t sec[32])
272 {
273         genpub(pub, sec);
274         burnstack(2048);
275 }
276
277
278 /*
279  * eddsa_sign - stack-cleaning wrapper for sign (obsolete interface!)
280  */
281 void
282 eddsa_sign(uint8_t sig[ED25519_SIG_LEN],
283            const uint8_t sec[ED25519_KEY_LEN],
284            const uint8_t pub[ED25519_KEY_LEN],
285            const uint8_t *data, size_t len)
286 {
287         sign(sig, sec, pub, data, len);
288         burnstack(4096);
289 }
290
291 /*
292  * eddsa_verify - verifies an ed25519 signature of given data.
293  * (obsolete interface!)
294  *
295  */
296 bool
297 eddsa_verify(const uint8_t sig[ED25519_SIG_LEN],
298              const uint8_t pub[ED25519_KEY_LEN],
299              const uint8_t *data, size_t len)
300 {
301         return ed25519_verify(sig, pub, data, len);
302 }
303
304 /*
305  * eddsa_pk_eddsa_to_dh - convert a ed25519 public key to x25519.
306  * (obsolete interface!)
307  */
308 void
309 eddsa_pk_eddsa_to_dh(uint8_t out[X25519_KEY_LEN], const uint8_t in[ED25519_KEY_LEN])
310 {
311         pk_ed25519_to_x25519(out, in);
312 }
313
314
315 /*
316  * eddsa_sk_eddsa_to_dh - convert a ed25519 secret key to x25519 secret.
317  * (obsolete interface!)
318  */
319 void
320 eddsa_sk_eddsa_to_dh(uint8_t out[X25519_KEY_LEN], const uint8_t in[ED25519_KEY_LEN])
321 {
322         conv_sk_ed25519_to_x25519(out, in);
323         burnstack(1024);
324 }