]>
Commit | Line | Data |
---|---|---|
1308e022 | 1 | /* |
f53c7764 | 2 | * Copyright 2017-2018 The OpenSSL Project Authors. All Rights Reserved. |
1308e022 | 3 | * Copyright 2015-2016 Cryptography Research, Inc. |
7324473f | 4 | * |
1308e022 MC |
5 | * Licensed under the OpenSSL license (the "License"). You may not use |
6 | * this file except in compliance with the License. You can obtain a copy | |
7 | * in the file LICENSE in the source distribution or at | |
8 | * https://www.openssl.org/source/license.html | |
7324473f | 9 | * |
1308e022 | 10 | * Originally written by Mike Hamburg |
7324473f | 11 | */ |
b6e388ba | 12 | #include <openssl/crypto.h> |
7324473f MC |
13 | #include "word.h" |
14 | #include "field.h" | |
15 | ||
a2039c87 MC |
16 | #include "point_448.h" |
17 | #include "ed448.h" | |
ad0a8a5c | 18 | #include "curve448_lcl.h" |
7324473f | 19 | |
7324473f MC |
20 | #define COFACTOR 4 |
21 | ||
22 | /* Comb config: number of combs, n, t, s. */ | |
23 | #define COMBS_N 5 | |
24 | #define COMBS_T 5 | |
25 | #define COMBS_S 18 | |
aeeef83c MC |
26 | #define C448_WNAF_FIXED_TABLE_BITS 5 |
27 | #define C448_WNAF_VAR_TABLE_BITS 3 | |
7324473f | 28 | |
7324473f | 29 | static const int EDWARDS_D = -39081; |
8d55f844 MC |
30 | static const curve448_scalar_t precomputed_scalarmul_adjustment = { |
31 | { | |
32 | { | |
33 | SC_LIMB(0xc873d6d54a7bb0cf), SC_LIMB(0xe933d8d723a70aad), | |
34 | SC_LIMB(0xbb124b65129c96fd), SC_LIMB(0x00000008335dc163) | |
35 | } | |
36 | } | |
205fd638 | 37 | }; |
7324473f | 38 | |
7324473f | 39 | #define TWISTED_D ((EDWARDS_D)-1) |
7324473f | 40 | |
aeeef83c | 41 | #define WBITS C448_WORD_BITS /* NB this may be different from ARCH_WORD_BITS */ |
7324473f | 42 | |
7324473f | 43 | /* Projective Niels coordinates */ |
205fd638 MC |
44 | typedef struct { |
45 | gf a, b, c; | |
46 | } niels_s, niels_t[1]; | |
47 | typedef struct { | |
48 | niels_t n; | |
49 | gf z; | |
35b7c85a | 50 | } VECTOR_ALIGNED pniels_t[1]; |
7324473f MC |
51 | |
52 | /* Precomputed base */ | |
205fd638 MC |
53 | struct curve448_precomputed_s { |
54 | niels_t table[COMBS_N << (COMBS_T - 1)]; | |
55 | }; | |
7324473f | 56 | |
e7772577 | 57 | extern const gf curve448_precomputed_base_as_fe[]; |
88ba7e71 | 58 | const curve448_precomputed_s *curve448_precomputed_base = |
205fd638 | 59 | (const curve448_precomputed_s *)&curve448_precomputed_base_as_fe; |
7324473f | 60 | |
8d55f844 | 61 | /* Inverse. */ |
205fd638 MC |
62 | static void gf_invert(gf y, const gf x, int assert_nonzero) |
63 | { | |
094c071c MC |
64 | mask_t ret; |
65 | ||
7324473f | 66 | gf t1, t2; |
205fd638 MC |
67 | gf_sqr(t1, x); /* o^2 */ |
68 | ret = gf_isr(t2, t1); /* +-1/sqrt(o^2) = +-1/o */ | |
7324473f | 69 | (void)ret; |
205fd638 MC |
70 | if (assert_nonzero) |
71 | assert(ret); | |
7324473f | 72 | gf_sqr(t1, t2); |
205fd638 | 73 | gf_mul(t2, t1, x); /* not direct to y in case of alias. */ |
7324473f MC |
74 | gf_copy(y, t2); |
75 | } | |
76 | ||
77 | /** identity = (0,1) */ | |
205fd638 MC |
78 | const curve448_point_t curve448_point_identity = |
79 | { {{{{0}}}, {{{1}}}, {{{1}}}, {{{0}}}} }; | |
7324473f | 80 | |
8d55f844 MC |
81 | static void point_double_internal(curve448_point_t p, const curve448_point_t q, |
82 | int before_double) | |
205fd638 | 83 | { |
7324473f | 84 | gf a, b, c, d; |
8d55f844 | 85 | |
205fd638 MC |
86 | gf_sqr(c, q->x); |
87 | gf_sqr(a, q->y); | |
88 | gf_add_nr(d, c, a); /* 2+e */ | |
89 | gf_add_nr(p->t, q->y, q->x); /* 2+e */ | |
90 | gf_sqr(b, p->t); | |
91 | gf_subx_nr(b, b, d, 3); /* 4+e */ | |
92 | gf_sub_nr(p->t, a, c); /* 3+e */ | |
93 | gf_sqr(p->x, q->z); | |
94 | gf_add_nr(p->z, p->x, p->x); /* 2+e */ | |
95 | gf_subx_nr(a, p->z, p->t, 4); /* 6+e */ | |
96 | if (GF_HEADROOM == 5) | |
97 | gf_weak_reduce(a); /* or 1+e */ | |
98 | gf_mul(p->x, a, b); | |
99 | gf_mul(p->z, p->t, a); | |
100 | gf_mul(p->y, p->t, d); | |
101 | if (!before_double) | |
102 | gf_mul(p->t, b, d); | |
7324473f MC |
103 | } |
104 | ||
205fd638 MC |
105 | void curve448_point_double(curve448_point_t p, const curve448_point_t q) |
106 | { | |
107 | point_double_internal(p, q, 0); | |
7324473f MC |
108 | } |
109 | ||
7324473f | 110 | /* Operations on [p]niels */ |
205fd638 MC |
111 | static ossl_inline void cond_neg_niels(niels_t n, mask_t neg) |
112 | { | |
7324473f MC |
113 | gf_cond_swap(n->a, n->b, neg); |
114 | gf_cond_neg(n->c, neg); | |
115 | } | |
116 | ||
205fd638 MC |
117 | static void pt_to_pniels(pniels_t b, const curve448_point_t a) |
118 | { | |
119 | gf_sub(b->n->a, a->y, a->x); | |
120 | gf_add(b->n->b, a->x, a->y); | |
121 | gf_mulw(b->n->c, a->t, 2 * TWISTED_D); | |
122 | gf_add(b->z, a->z, a->z); | |
7324473f MC |
123 | } |
124 | ||
205fd638 MC |
125 | static void pniels_to_pt(curve448_point_t e, const pniels_t d) |
126 | { | |
7324473f | 127 | gf eu; |
8d55f844 | 128 | |
205fd638 MC |
129 | gf_add(eu, d->n->b, d->n->a); |
130 | gf_sub(e->y, d->n->b, d->n->a); | |
131 | gf_mul(e->t, e->y, eu); | |
132 | gf_mul(e->x, d->z, e->y); | |
133 | gf_mul(e->y, d->z, eu); | |
134 | gf_sqr(e->z, d->z); | |
7324473f MC |
135 | } |
136 | ||
205fd638 MC |
137 | static void niels_to_pt(curve448_point_t e, const niels_t n) |
138 | { | |
139 | gf_add(e->y, n->b, n->a); | |
140 | gf_sub(e->x, n->b, n->a); | |
141 | gf_mul(e->t, e->y, e->x); | |
142 | gf_copy(e->z, ONE); | |
7324473f MC |
143 | } |
144 | ||
8d55f844 MC |
145 | static void add_niels_to_pt(curve448_point_t d, const niels_t e, |
146 | int before_double) | |
205fd638 | 147 | { |
7324473f | 148 | gf a, b, c; |
8d55f844 | 149 | |
205fd638 MC |
150 | gf_sub_nr(b, d->y, d->x); /* 3+e */ |
151 | gf_mul(a, e->a, b); | |
152 | gf_add_nr(b, d->x, d->y); /* 2+e */ | |
153 | gf_mul(d->y, e->b, b); | |
154 | gf_mul(d->x, e->c, d->t); | |
155 | gf_add_nr(c, a, d->y); /* 2+e */ | |
156 | gf_sub_nr(b, d->y, a); /* 3+e */ | |
157 | gf_sub_nr(d->y, d->z, d->x); /* 3+e */ | |
158 | gf_add_nr(a, d->x, d->z); /* 2+e */ | |
159 | gf_mul(d->z, a, d->y); | |
160 | gf_mul(d->x, d->y, b); | |
161 | gf_mul(d->y, a, c); | |
162 | if (!before_double) | |
163 | gf_mul(d->t, b, c); | |
7324473f MC |
164 | } |
165 | ||
8d55f844 MC |
166 | static void sub_niels_from_pt(curve448_point_t d, const niels_t e, |
167 | int before_double) | |
205fd638 | 168 | { |
7324473f | 169 | gf a, b, c; |
68b20c00 | 170 | |
205fd638 MC |
171 | gf_sub_nr(b, d->y, d->x); /* 3+e */ |
172 | gf_mul(a, e->b, b); | |
173 | gf_add_nr(b, d->x, d->y); /* 2+e */ | |
174 | gf_mul(d->y, e->a, b); | |
175 | gf_mul(d->x, e->c, d->t); | |
176 | gf_add_nr(c, a, d->y); /* 2+e */ | |
177 | gf_sub_nr(b, d->y, a); /* 3+e */ | |
178 | gf_add_nr(d->y, d->z, d->x); /* 2+e */ | |
179 | gf_sub_nr(a, d->z, d->x); /* 3+e */ | |
180 | gf_mul(d->z, a, d->y); | |
181 | gf_mul(d->x, d->y, b); | |
182 | gf_mul(d->y, a, c); | |
183 | if (!before_double) | |
184 | gf_mul(d->t, b, c); | |
7324473f MC |
185 | } |
186 | ||
8d55f844 MC |
187 | static void add_pniels_to_pt(curve448_point_t p, const pniels_t pn, |
188 | int before_double) | |
205fd638 | 189 | { |
7324473f | 190 | gf L0; |
8d55f844 | 191 | |
205fd638 MC |
192 | gf_mul(L0, p->z, pn->z); |
193 | gf_copy(p->z, L0); | |
194 | add_niels_to_pt(p, pn->n, before_double); | |
7324473f MC |
195 | } |
196 | ||
8d55f844 MC |
197 | static void sub_pniels_from_pt(curve448_point_t p, const pniels_t pn, |
198 | int before_double) | |
205fd638 | 199 | { |
7324473f | 200 | gf L0; |
8d55f844 | 201 | |
205fd638 MC |
202 | gf_mul(L0, p->z, pn->z); |
203 | gf_copy(p->z, L0); | |
204 | sub_niels_from_pt(p, pn->n, before_double); | |
7324473f MC |
205 | } |
206 | ||
aeeef83c MC |
207 | c448_bool_t curve448_point_eq(const curve448_point_t p, |
208 | const curve448_point_t q) | |
205fd638 | 209 | { |
094c071c | 210 | mask_t succ; |
68b20c00 | 211 | gf a, b; |
094c071c | 212 | |
7324473f | 213 | /* equality mod 2-torsion compares x/y */ |
205fd638 MC |
214 | gf_mul(a, p->y, q->x); |
215 | gf_mul(b, q->y, p->x); | |
216 | succ = gf_eq(a, b); | |
a469abf0 | 217 | |
7324473f MC |
218 | return mask_to_bool(succ); |
219 | } | |
220 | ||
aeeef83c | 221 | c448_bool_t curve448_point_valid(const curve448_point_t p) |
205fd638 | 222 | { |
094c071c | 223 | mask_t out; |
205fd638 | 224 | gf a, b, c; |
68b20c00 | 225 | |
205fd638 MC |
226 | gf_mul(a, p->x, p->y); |
227 | gf_mul(b, p->z, p->t); | |
228 | out = gf_eq(a, b); | |
229 | gf_sqr(a, p->x); | |
230 | gf_sqr(b, p->y); | |
231 | gf_sub(a, b, a); | |
232 | gf_sqr(b, p->t); | |
233 | gf_mulw(c, b, TWISTED_D); | |
234 | gf_sqr(b, p->z); | |
235 | gf_add(b, b, c); | |
236 | out &= gf_eq(a, b); | |
237 | out &= ~gf_eq(p->z, ZERO); | |
7324473f MC |
238 | return mask_to_bool(out); |
239 | } | |
240 | ||
52a9587c | 241 | static ossl_inline void constant_time_lookup_niels(niels_s * RESTRICT ni, |
8d55f844 MC |
242 | const niels_t * table, |
243 | int nelts, int idx) | |
205fd638 | 244 | { |
7324473f MC |
245 | constant_time_lookup(ni, table, sizeof(niels_s), nelts, idx); |
246 | } | |
247 | ||
205fd638 MC |
248 | void curve448_precomputed_scalarmul(curve448_point_t out, |
249 | const curve448_precomputed_s * table, | |
250 | const curve448_scalar_t scalar) | |
251 | { | |
68b20c00 | 252 | unsigned int i, j, k; |
7324473f | 253 | const unsigned int n = COMBS_N, t = COMBS_T, s = COMBS_S; |
094c071c | 254 | niels_t ni; |
88ba7e71 | 255 | curve448_scalar_t scalar1x; |
68b20c00 | 256 | |
e7772577 | 257 | curve448_scalar_add(scalar1x, scalar, precomputed_scalarmul_adjustment); |
205fd638 MC |
258 | curve448_scalar_halve(scalar1x, scalar1x); |
259 | ||
68b20c00 MC |
260 | for (i = s; i > 0; i--) { |
261 | if (i != s) | |
205fd638 MC |
262 | point_double_internal(out, out, 0); |
263 | ||
264 | for (j = 0; j < n; j++) { | |
7324473f | 265 | int tab = 0; |
094c071c | 266 | mask_t invert; |
205fd638 MC |
267 | |
268 | for (k = 0; k < t; k++) { | |
68b20c00 MC |
269 | unsigned int bit = (i - 1) + s * (k + j * t); |
270 | ||
db90b274 | 271 | if (bit < C448_SCALAR_BITS) { |
205fd638 MC |
272 | tab |= |
273 | (scalar1x->limb[bit / WBITS] >> (bit % WBITS) & 1) << k; | |
7324473f MC |
274 | } |
275 | } | |
205fd638 MC |
276 | |
277 | invert = (tab >> (t - 1)) - 1; | |
7324473f | 278 | tab ^= invert; |
205fd638 | 279 | tab &= (1 << (t - 1)) - 1; |
7324473f | 280 | |
205fd638 MC |
281 | constant_time_lookup_niels(ni, &table->table[j << (t - 1)], |
282 | 1 << (t - 1), tab); | |
7324473f MC |
283 | |
284 | cond_neg_niels(ni, invert); | |
68b20c00 MC |
285 | if ((i != s) || j != 0) { |
286 | add_niels_to_pt(out, ni, j == n - 1 && i != 1); | |
7324473f MC |
287 | } else { |
288 | niels_to_pt(out, ni); | |
289 | } | |
290 | } | |
291 | } | |
205fd638 MC |
292 | |
293 | OPENSSL_cleanse(ni, sizeof(ni)); | |
294 | OPENSSL_cleanse(scalar1x, sizeof(scalar1x)); | |
7324473f MC |
295 | } |
296 | ||
8d55f844 | 297 | void curve448_point_mul_by_ratio_and_encode_like_eddsa( |
db90b274 | 298 | uint8_t enc[EDDSA_448_PUBLIC_BYTES], |
8d55f844 | 299 | const curve448_point_t p) |
205fd638 | 300 | { |
7324473f | 301 | gf x, y, z, t; |
88ba7e71 | 302 | curve448_point_t q; |
68b20c00 MC |
303 | |
304 | /* The point is now on the twisted curve. Move it to untwisted. */ | |
205fd638 | 305 | curve448_point_copy(q, p); |
a469abf0 | 306 | |
7324473f MC |
307 | { |
308 | /* 4-isogeny: 2xy/(y^+x^2), (y^2-x^2)/(2z^2-y^2+x^2) */ | |
309 | gf u; | |
8d55f844 | 310 | |
205fd638 MC |
311 | gf_sqr(x, q->x); |
312 | gf_sqr(t, q->y); | |
313 | gf_add(u, x, t); | |
314 | gf_add(z, q->y, q->x); | |
315 | gf_sqr(y, z); | |
316 | gf_sub(y, y, u); | |
317 | gf_sub(z, t, x); | |
318 | gf_sqr(x, q->z); | |
319 | gf_add(t, x, x); | |
320 | gf_sub(t, t, z); | |
321 | gf_mul(x, t, y); | |
322 | gf_mul(y, z, u); | |
323 | gf_mul(z, u, t); | |
324 | OPENSSL_cleanse(u, sizeof(u)); | |
7324473f | 325 | } |
a469abf0 | 326 | |
7324473f | 327 | /* Affinize */ |
205fd638 MC |
328 | gf_invert(z, z, 1); |
329 | gf_mul(t, x, z); | |
330 | gf_mul(x, y, z); | |
331 | ||
7324473f | 332 | /* Encode */ |
db90b274 | 333 | enc[EDDSA_448_PRIVATE_BYTES - 1] = 0; |
7324473f | 334 | gf_serialize(enc, x, 1); |
db90b274 | 335 | enc[EDDSA_448_PRIVATE_BYTES - 1] |= 0x80 & gf_lobit(t); |
7324473f | 336 | |
205fd638 MC |
337 | OPENSSL_cleanse(x, sizeof(x)); |
338 | OPENSSL_cleanse(y, sizeof(y)); | |
339 | OPENSSL_cleanse(z, sizeof(z)); | |
340 | OPENSSL_cleanse(t, sizeof(t)); | |
e7772577 | 341 | curve448_point_destroy(q); |
7324473f MC |
342 | } |
343 | ||
aeeef83c | 344 | c448_error_t curve448_point_decode_like_eddsa_and_mul_by_ratio( |
8d55f844 | 345 | curve448_point_t p, |
db90b274 | 346 | const uint8_t enc[EDDSA_448_PUBLIC_BYTES]) |
205fd638 | 347 | { |
db90b274 | 348 | uint8_t enc2[EDDSA_448_PUBLIC_BYTES]; |
094c071c MC |
349 | mask_t low; |
350 | mask_t succ; | |
351 | ||
205fd638 MC |
352 | memcpy(enc2, enc, sizeof(enc2)); |
353 | ||
db90b274 MC |
354 | low = ~word_is_zero(enc2[EDDSA_448_PRIVATE_BYTES - 1] & 0x80); |
355 | enc2[EDDSA_448_PRIVATE_BYTES - 1] &= ~0x80; | |
7324473f | 356 | |
094c071c | 357 | succ = gf_deserialize(p->y, enc2, 1, 0); |
db90b274 | 358 | succ &= word_is_zero(enc2[EDDSA_448_PRIVATE_BYTES - 1]); |
7324473f | 359 | |
205fd638 MC |
360 | gf_sqr(p->x, p->y); |
361 | gf_sub(p->z, ONE, p->x); /* num = 1-y^2 */ | |
362 | gf_mulw(p->t, p->x, EDWARDS_D); /* dy^2 */ | |
363 | gf_sub(p->t, ONE, p->t); /* denom = 1-dy^2 or 1-d + dy^2 */ | |
364 | ||
365 | gf_mul(p->x, p->z, p->t); | |
366 | succ &= gf_isr(p->t, p->x); /* 1/sqrt(num * denom) */ | |
367 | ||
368 | gf_mul(p->x, p->t, p->z); /* sqrt(num / denom) */ | |
369 | gf_cond_neg(p->x, gf_lobit(p->x) ^ low); | |
370 | gf_copy(p->z, ONE); | |
371 | ||
7324473f | 372 | { |
7324473f | 373 | gf a, b, c, d; |
68b20c00 MC |
374 | |
375 | /* 4-isogeny 2xy/(y^2-ax^2), (y^2+ax^2)/(2-y^2-ax^2) */ | |
205fd638 MC |
376 | gf_sqr(c, p->x); |
377 | gf_sqr(a, p->y); | |
378 | gf_add(d, c, a); | |
379 | gf_add(p->t, p->y, p->x); | |
380 | gf_sqr(b, p->t); | |
381 | gf_sub(b, b, d); | |
382 | gf_sub(p->t, a, c); | |
383 | gf_sqr(p->x, p->z); | |
384 | gf_add(p->z, p->x, p->x); | |
385 | gf_sub(a, p->z, d); | |
386 | gf_mul(p->x, a, b); | |
387 | gf_mul(p->z, p->t, a); | |
388 | gf_mul(p->y, p->t, d); | |
389 | gf_mul(p->t, b, d); | |
390 | OPENSSL_cleanse(a, sizeof(a)); | |
391 | OPENSSL_cleanse(b, sizeof(b)); | |
392 | OPENSSL_cleanse(c, sizeof(c)); | |
393 | OPENSSL_cleanse(d, sizeof(d)); | |
7324473f | 394 | } |
205fd638 MC |
395 | |
396 | OPENSSL_cleanse(enc2, sizeof(enc2)); | |
e7772577 | 397 | assert(curve448_point_valid(p) || ~succ); |
205fd638 | 398 | |
aeeef83c | 399 | return c448_succeed_if(mask_to_bool(succ)); |
7324473f MC |
400 | } |
401 | ||
db90b274 MC |
402 | c448_error_t x448_int(uint8_t out[X_PUBLIC_BYTES], |
403 | const uint8_t base[X_PUBLIC_BYTES], | |
404 | const uint8_t scalar[X_PRIVATE_BYTES]) | |
205fd638 | 405 | { |
7324473f | 406 | gf x1, x2, z2, x3, z3, t1, t2; |
094c071c MC |
407 | int t; |
408 | mask_t swap = 0; | |
409 | mask_t nz; | |
410 | ||
205fd638 MC |
411 | ignore_result(gf_deserialize(x1, base, 1, 0)); |
412 | gf_copy(x2, ONE); | |
413 | gf_copy(z2, ZERO); | |
414 | gf_copy(x3, x1); | |
415 | gf_copy(z3, ONE); | |
416 | ||
417 | for (t = X_PRIVATE_BITS - 1; t >= 0; t--) { | |
418 | uint8_t sb = scalar[t / 8]; | |
094c071c | 419 | mask_t k_t; |
205fd638 | 420 | |
7324473f | 421 | /* Scalar conditioning */ |
205fd638 MC |
422 | if (t / 8 == 0) |
423 | sb &= -(uint8_t)COFACTOR; | |
424 | else if (t == X_PRIVATE_BITS - 1) | |
425 | sb = -1; | |
426 | ||
427 | k_t = (sb >> (t % 8)) & 1; | |
52a9587c | 428 | k_t = 0 - k_t; /* set to all 0s or all 1s */ |
205fd638 | 429 | |
7324473f | 430 | swap ^= k_t; |
205fd638 MC |
431 | gf_cond_swap(x2, x3, swap); |
432 | gf_cond_swap(z2, z3, swap); | |
7324473f | 433 | swap = k_t; |
205fd638 MC |
434 | |
435 | gf_add_nr(t1, x2, z2); /* A = x2 + z2 *//* 2+e */ | |
436 | gf_sub_nr(t2, x2, z2); /* B = x2 - z2 *//* 3+e */ | |
437 | gf_sub_nr(z2, x3, z3); /* D = x3 - z3 *//* 3+e */ | |
438 | gf_mul(x2, t1, z2); /* DA */ | |
439 | gf_add_nr(z2, z3, x3); /* C = x3 + z3 *//* 2+e */ | |
440 | gf_mul(x3, t2, z2); /* CB */ | |
441 | gf_sub_nr(z3, x2, x3); /* DA-CB *//* 3+e */ | |
442 | gf_sqr(z2, z3); /* (DA-CB)^2 */ | |
443 | gf_mul(z3, x1, z2); /* z3 = x1(DA-CB)^2 */ | |
444 | gf_add_nr(z2, x2, x3); /* (DA+CB) *//* 2+e */ | |
445 | gf_sqr(x3, z2); /* x3 = (DA+CB)^2 */ | |
446 | ||
447 | gf_sqr(z2, t1); /* AA = A^2 */ | |
448 | gf_sqr(t1, t2); /* BB = B^2 */ | |
449 | gf_mul(x2, z2, t1); /* x2 = AA*BB */ | |
450 | gf_sub_nr(t2, z2, t1); /* E = AA-BB *//* 3+e */ | |
451 | ||
452 | gf_mulw(t1, t2, -EDWARDS_D); /* E*-d = a24*E */ | |
453 | gf_add_nr(t1, t1, z2); /* AA + a24*E *//* 2+e */ | |
454 | gf_mul(z2, t2, t1); /* z2 = E(AA+a24*E) */ | |
7324473f | 455 | } |
205fd638 | 456 | |
7324473f | 457 | /* Finish */ |
205fd638 MC |
458 | gf_cond_swap(x2, x3, swap); |
459 | gf_cond_swap(z2, z3, swap); | |
460 | gf_invert(z2, z2, 0); | |
461 | gf_mul(x1, x2, z2); | |
462 | gf_serialize(out, x1, 1); | |
463 | nz = ~gf_eq(x1, ZERO); | |
464 | ||
465 | OPENSSL_cleanse(x1, sizeof(x1)); | |
466 | OPENSSL_cleanse(x2, sizeof(x2)); | |
467 | OPENSSL_cleanse(z2, sizeof(z2)); | |
468 | OPENSSL_cleanse(x3, sizeof(x3)); | |
469 | OPENSSL_cleanse(z3, sizeof(z3)); | |
470 | OPENSSL_cleanse(t1, sizeof(t1)); | |
471 | OPENSSL_cleanse(t2, sizeof(t2)); | |
472 | ||
aeeef83c | 473 | return c448_succeed_if(mask_to_bool(nz)); |
7324473f MC |
474 | } |
475 | ||
205fd638 MC |
476 | void curve448_point_mul_by_ratio_and_encode_like_x448(uint8_t |
477 | out[X_PUBLIC_BYTES], | |
478 | const curve448_point_t p) | |
479 | { | |
88ba7e71 | 480 | curve448_point_t q; |
68b20c00 | 481 | |
205fd638 MC |
482 | curve448_point_copy(q, p); |
483 | gf_invert(q->t, q->x, 0); /* 1/x */ | |
484 | gf_mul(q->z, q->t, q->y); /* y/x */ | |
485 | gf_sqr(q->y, q->z); /* (y/x)^2 */ | |
486 | gf_serialize(out, q->y, 1); | |
e7772577 | 487 | curve448_point_destroy(q); |
7324473f MC |
488 | } |
489 | ||
db90b274 MC |
490 | void x448_derive_public_key(uint8_t out[X_PUBLIC_BYTES], |
491 | const uint8_t scalar[X_PRIVATE_BYTES]) | |
205fd638 | 492 | { |
7324473f MC |
493 | /* Scalar conditioning */ |
494 | uint8_t scalar2[X_PRIVATE_BYTES]; | |
094c071c MC |
495 | curve448_scalar_t the_scalar; |
496 | curve448_point_t p; | |
497 | unsigned int i; | |
498 | ||
205fd638 | 499 | memcpy(scalar2, scalar, sizeof(scalar2)); |
7324473f | 500 | scalar2[0] &= -(uint8_t)COFACTOR; |
205fd638 | 501 | |
52a9587c | 502 | scalar2[X_PRIVATE_BYTES - 1] &= ~((0u - 1u) << ((X_PRIVATE_BITS + 7) % 8)); |
205fd638 MC |
503 | scalar2[X_PRIVATE_BYTES - 1] |= 1 << ((X_PRIVATE_BITS + 7) % 8); |
504 | ||
505 | curve448_scalar_decode_long(the_scalar, scalar2, sizeof(scalar2)); | |
506 | ||
7324473f | 507 | /* Compensate for the encoding ratio */ |
db90b274 | 508 | for (i = 1; i < X448_ENCODE_RATIO; i <<= 1) { |
205fd638 | 509 | curve448_scalar_halve(the_scalar, the_scalar); |
7324473f | 510 | } |
205fd638 MC |
511 | curve448_precomputed_scalarmul(p, curve448_precomputed_base, the_scalar); |
512 | curve448_point_mul_by_ratio_and_encode_like_x448(out, p); | |
e7772577 | 513 | curve448_point_destroy(p); |
7324473f MC |
514 | } |
515 | ||
8d55f844 | 516 | /* Control for variable-time scalar multiply algorithms. */ |
7324473f | 517 | struct smvt_control { |
205fd638 | 518 | int power, addend; |
7324473f MC |
519 | }; |
520 | ||
52a9587c MC |
521 | #if defined(__GNUC__) || defined(__clang__) |
522 | # define NUMTRAILINGZEROS __builtin_ctz | |
523 | #else | |
524 | # define NUMTRAILINGZEROS numtrailingzeros | |
525 | static uint32_t numtrailingzeros(uint32_t i) | |
526 | { | |
68b20c00 | 527 | uint32_t tmp; |
52a9587c MC |
528 | uint32_t num = 31; |
529 | ||
530 | if (i == 0) | |
531 | return 32; | |
532 | ||
533 | tmp = i << 16; | |
534 | if (tmp != 0) { | |
535 | i = tmp; | |
536 | num -= 16; | |
537 | } | |
538 | tmp = i << 8; | |
539 | if (tmp != 0) { | |
540 | i = tmp; | |
541 | num -= 8; | |
542 | } | |
543 | tmp = i << 4; | |
544 | if (tmp != 0) { | |
545 | i = tmp; | |
546 | num -= 4; | |
547 | } | |
548 | tmp = i << 2; | |
549 | if (tmp != 0) { | |
550 | i = tmp; | |
551 | num -= 2; | |
552 | } | |
68b20c00 MC |
553 | tmp = i << 1; |
554 | if (tmp != 0) | |
52a9587c MC |
555 | num--; |
556 | ||
557 | return num; | |
558 | } | |
559 | #endif | |
560 | ||
8d55f844 MC |
561 | static int recode_wnaf(struct smvt_control *control, |
562 | /* [nbits/(table_bits + 1) + 3] */ | |
563 | const curve448_scalar_t scalar, | |
564 | unsigned int table_bits) | |
205fd638 | 565 | { |
db90b274 | 566 | unsigned int table_size = C448_SCALAR_BITS / (table_bits + 1) + 3; |
7324473f | 567 | int position = table_size - 1; /* at the end */ |
094c071c | 568 | uint64_t current = scalar->limb[0] & 0xFFFF; |
205fd638 | 569 | uint32_t mask = (1 << (table_bits + 1)) - 1; |
094c071c MC |
570 | unsigned int w; |
571 | const unsigned int B_OVER_16 = sizeof(scalar->limb[0]) / 2; | |
572 | unsigned int n, i; | |
573 | ||
7324473f MC |
574 | /* place the end marker */ |
575 | control[position].power = -1; | |
576 | control[position].addend = 0; | |
577 | position--; | |
578 | ||
205fd638 MC |
579 | /* |
580 | * PERF: Could negate scalar if it's large. But then would need more cases | |
581 | * in the actual code that uses it, all for an expected reduction of like | |
582 | * 1/5 op. Probably not worth it. | |
7324473f | 583 | */ |
7324473f | 584 | |
db90b274 MC |
585 | for (w = 1; w < (C448_SCALAR_BITS - 1) / 16 + 3; w++) { |
586 | if (w < (C448_SCALAR_BITS - 1) / 16 + 1) { | |
7324473f | 587 | /* Refill the 16 high bits of current */ |
8d55f844 MC |
588 | current += (uint32_t)((scalar->limb[w / B_OVER_16] |
589 | >> (16 * (w % B_OVER_16))) << 16); | |
7324473f | 590 | } |
205fd638 | 591 | |
7324473f | 592 | while (current & 0xFFFF) { |
52a9587c | 593 | uint32_t pos = NUMTRAILINGZEROS((uint32_t)current); |
8d55f844 | 594 | uint32_t odd = (uint32_t)current >> pos; |
7324473f | 595 | int32_t delta = odd & mask; |
094c071c MC |
596 | |
597 | assert(position >= 0); | |
68b20c00 | 598 | if (odd & (1 << (table_bits + 1))) |
205fd638 | 599 | delta -= (1 << (table_bits + 1)); |
7324473f | 600 | current -= delta << pos; |
205fd638 | 601 | control[position].power = pos + 16 * (w - 1); |
7324473f MC |
602 | control[position].addend = delta; |
603 | position--; | |
604 | } | |
605 | current >>= 16; | |
606 | } | |
205fd638 MC |
607 | assert(current == 0); |
608 | ||
7324473f | 609 | position++; |
094c071c | 610 | n = table_size - position; |
68b20c00 | 611 | for (i = 0; i < n; i++) |
205fd638 | 612 | control[i] = control[i + position]; |
68b20c00 | 613 | |
205fd638 | 614 | return n - 1; |
7324473f MC |
615 | } |
616 | ||
8d55f844 MC |
617 | static void prepare_wnaf_table(pniels_t * output, |
618 | const curve448_point_t working, | |
619 | unsigned int tbits) | |
205fd638 | 620 | { |
88ba7e71 | 621 | curve448_point_t tmp; |
7324473f | 622 | int i; |
094c071c MC |
623 | pniels_t twop; |
624 | ||
7324473f MC |
625 | pt_to_pniels(output[0], working); |
626 | ||
205fd638 MC |
627 | if (tbits == 0) |
628 | return; | |
7324473f | 629 | |
205fd638 | 630 | curve448_point_double(tmp, working); |
7324473f MC |
631 | pt_to_pniels(twop, tmp); |
632 | ||
205fd638 | 633 | add_pniels_to_pt(tmp, output[0], 0); |
7324473f MC |
634 | pt_to_pniels(output[1], tmp); |
635 | ||
205fd638 MC |
636 | for (i = 2; i < 1 << tbits; i++) { |
637 | add_pniels_to_pt(tmp, twop, 0); | |
7324473f MC |
638 | pt_to_pniels(output[i], tmp); |
639 | } | |
205fd638 | 640 | |
e7772577 | 641 | curve448_point_destroy(tmp); |
205fd638 | 642 | OPENSSL_cleanse(twop, sizeof(twop)); |
7324473f MC |
643 | } |
644 | ||
e7772577 | 645 | extern const gf curve448_precomputed_wnaf_as_fe[]; |
205fd638 MC |
646 | static const niels_t *curve448_wnaf_base = |
647 | (const niels_t *)curve448_precomputed_wnaf_as_fe; | |
648 | ||
649 | void curve448_base_double_scalarmul_non_secret(curve448_point_t combo, | |
650 | const curve448_scalar_t scalar1, | |
651 | const curve448_point_t base2, | |
652 | const curve448_scalar_t scalar2) | |
653 | { | |
68b20c00 MC |
654 | const int table_bits_var = C448_WNAF_VAR_TABLE_BITS; |
655 | const int table_bits_pre = C448_WNAF_FIXED_TABLE_BITS; | |
db90b274 | 656 | struct smvt_control control_var[C448_SCALAR_BITS / |
aeeef83c | 657 | (C448_WNAF_VAR_TABLE_BITS + 1) + 3]; |
db90b274 | 658 | struct smvt_control control_pre[C448_SCALAR_BITS / |
aeeef83c | 659 | (C448_WNAF_FIXED_TABLE_BITS + 1) + 3]; |
7324473f MC |
660 | int ncb_pre = recode_wnaf(control_pre, scalar1, table_bits_pre); |
661 | int ncb_var = recode_wnaf(control_var, scalar2, table_bits_var); | |
aeeef83c | 662 | pniels_t precmp_var[1 << C448_WNAF_VAR_TABLE_BITS]; |
205fd638 | 663 | int contp = 0, contv = 0, i; |
094c071c | 664 | |
7324473f | 665 | prepare_wnaf_table(precmp_var, base2, table_bits_var); |
094c071c | 666 | i = control_var[0].power; |
7324473f MC |
667 | |
668 | if (i < 0) { | |
e7772577 | 669 | curve448_point_copy(combo, curve448_point_identity); |
7324473f MC |
670 | return; |
671 | } else if (i > control_pre[0].power) { | |
672 | pniels_to_pt(combo, precmp_var[control_var[0].addend >> 1]); | |
673 | contv++; | |
205fd638 | 674 | } else if (i == control_pre[0].power && i >= 0) { |
7324473f | 675 | pniels_to_pt(combo, precmp_var[control_var[0].addend >> 1]); |
205fd638 MC |
676 | add_niels_to_pt(combo, curve448_wnaf_base[control_pre[0].addend >> 1], |
677 | i); | |
678 | contv++; | |
679 | contp++; | |
7324473f MC |
680 | } else { |
681 | i = control_pre[0].power; | |
e7772577 | 682 | niels_to_pt(combo, curve448_wnaf_base[control_pre[0].addend >> 1]); |
7324473f MC |
683 | contp++; |
684 | } | |
205fd638 | 685 | |
7324473f | 686 | for (i--; i >= 0; i--) { |
68b20c00 MC |
687 | int cv = (i == control_var[contv].power); |
688 | int cp = (i == control_pre[contp].power); | |
689 | ||
205fd638 | 690 | point_double_internal(combo, combo, i && !(cv || cp)); |
7324473f MC |
691 | |
692 | if (cv) { | |
693 | assert(control_var[contv].addend); | |
694 | ||
68b20c00 | 695 | if (control_var[contv].addend > 0) |
205fd638 | 696 | add_pniels_to_pt(combo, |
8d55f844 MC |
697 | precmp_var[control_var[contv].addend >> 1], |
698 | i && !cp); | |
68b20c00 | 699 | else |
205fd638 | 700 | sub_pniels_from_pt(combo, |
8d55f844 MC |
701 | precmp_var[(-control_var[contv].addend) |
702 | >> 1], i && !cp); | |
7324473f MC |
703 | contv++; |
704 | } | |
705 | ||
706 | if (cp) { | |
707 | assert(control_pre[contp].addend); | |
708 | ||
68b20c00 | 709 | if (control_pre[contp].addend > 0) |
205fd638 | 710 | add_niels_to_pt(combo, |
8d55f844 MC |
711 | curve448_wnaf_base[control_pre[contp].addend |
712 | >> 1], i); | |
68b20c00 | 713 | else |
205fd638 MC |
714 | sub_niels_from_pt(combo, |
715 | curve448_wnaf_base[(-control_pre | |
716 | [contp].addend) >> 1], i); | |
7324473f MC |
717 | contp++; |
718 | } | |
719 | } | |
7324473f | 720 | |
205fd638 MC |
721 | /* This function is non-secret, but whatever this is cheap. */ |
722 | OPENSSL_cleanse(control_var, sizeof(control_var)); | |
723 | OPENSSL_cleanse(control_pre, sizeof(control_pre)); | |
724 | OPENSSL_cleanse(precmp_var, sizeof(precmp_var)); | |
725 | ||
726 | assert(contv == ncb_var); | |
727 | (void)ncb_var; | |
728 | assert(contp == ncb_pre); | |
729 | (void)ncb_pre; | |
7324473f MC |
730 | } |
731 | ||
205fd638 MC |
732 | void curve448_point_destroy(curve448_point_t point) |
733 | { | |
88ba7e71 | 734 | OPENSSL_cleanse(point, sizeof(curve448_point_t)); |
7324473f MC |
735 | } |
736 | ||
ad0a8a5c MC |
737 | int X448(uint8_t out_shared_key[56], const uint8_t private_key[56], |
738 | const uint8_t peer_public_value[56]) | |
739 | { | |
db90b274 MC |
740 | return x448_int(out_shared_key, peer_public_value, private_key) |
741 | == C448_SUCCESS; | |
ad0a8a5c MC |
742 | } |
743 | ||
744 | void X448_public_from_private(uint8_t out_public_value[56], | |
745 | const uint8_t private_key[56]) | |
746 | { | |
db90b274 | 747 | x448_derive_public_key(out_public_value, private_key); |
ad0a8a5c | 748 | } |