1 | // SPDX-License-Identifier: GPL-2.0 OR MIT |
2 | /* |
3 | * Copyright (C) 2016-2017 INRIA and Microsoft Corporation. |
4 | * Copyright (C) 2018-2019 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved. |
5 | * |
6 | * This is a machine-generated formally verified implementation of Curve25519 |
7 | * ECDH from: <https://github.com/mitls/hacl-star>. Though originally machine |
8 | * generated, it has been tweaked to be suitable for use in the kernel. It is |
9 | * optimized for 64-bit machines that can efficiently work with 128-bit |
10 | * integer types. |
11 | */ |
12 | |
13 | #include <asm/unaligned.h> |
14 | #include <crypto/curve25519.h> |
15 | #include <linux/string.h> |
16 | |
17 | static __always_inline u64 u64_eq_mask(u64 a, u64 b) |
18 | { |
19 | u64 x = a ^ b; |
20 | u64 minus_x = ~x + (u64)1U; |
21 | u64 x_or_minus_x = x | minus_x; |
22 | u64 xnx = x_or_minus_x >> (u32)63U; |
23 | u64 c = xnx - (u64)1U; |
24 | return c; |
25 | } |
26 | |
27 | static __always_inline u64 u64_gte_mask(u64 a, u64 b) |
28 | { |
29 | u64 x = a; |
30 | u64 y = b; |
31 | u64 x_xor_y = x ^ y; |
32 | u64 x_sub_y = x - y; |
33 | u64 x_sub_y_xor_y = x_sub_y ^ y; |
34 | u64 q = x_xor_y | x_sub_y_xor_y; |
35 | u64 x_xor_q = x ^ q; |
36 | u64 x_xor_q_ = x_xor_q >> (u32)63U; |
37 | u64 c = x_xor_q_ - (u64)1U; |
38 | return c; |
39 | } |
40 | |
41 | static __always_inline void modulo_carry_top(u64 *b) |
42 | { |
43 | u64 b4 = b[4]; |
44 | u64 b0 = b[0]; |
45 | u64 b4_ = b4 & 0x7ffffffffffffLLU; |
46 | u64 b0_ = b0 + 19 * (b4 >> 51); |
47 | b[4] = b4_; |
48 | b[0] = b0_; |
49 | } |
50 | |
51 | static __always_inline void fproduct_copy_from_wide_(u64 *output, u128 *input) |
52 | { |
53 | { |
54 | u128 xi = input[0]; |
55 | output[0] = ((u64)(xi)); |
56 | } |
57 | { |
58 | u128 xi = input[1]; |
59 | output[1] = ((u64)(xi)); |
60 | } |
61 | { |
62 | u128 xi = input[2]; |
63 | output[2] = ((u64)(xi)); |
64 | } |
65 | { |
66 | u128 xi = input[3]; |
67 | output[3] = ((u64)(xi)); |
68 | } |
69 | { |
70 | u128 xi = input[4]; |
71 | output[4] = ((u64)(xi)); |
72 | } |
73 | } |
74 | |
75 | static __always_inline void |
76 | fproduct_sum_scalar_multiplication_(u128 *output, u64 *input, u64 s) |
77 | { |
78 | output[0] += (u128)input[0] * s; |
79 | output[1] += (u128)input[1] * s; |
80 | output[2] += (u128)input[2] * s; |
81 | output[3] += (u128)input[3] * s; |
82 | output[4] += (u128)input[4] * s; |
83 | } |
84 | |
85 | static __always_inline void fproduct_carry_wide_(u128 *tmp) |
86 | { |
87 | { |
88 | u32 ctr = 0; |
89 | u128 tctr = tmp[ctr]; |
90 | u128 tctrp1 = tmp[ctr + 1]; |
91 | u64 r0 = ((u64)(tctr)) & 0x7ffffffffffffLLU; |
92 | u128 c = ((tctr) >> (51)); |
93 | tmp[ctr] = ((u128)(r0)); |
94 | tmp[ctr + 1] = ((tctrp1) + (c)); |
95 | } |
96 | { |
97 | u32 ctr = 1; |
98 | u128 tctr = tmp[ctr]; |
99 | u128 tctrp1 = tmp[ctr + 1]; |
100 | u64 r0 = ((u64)(tctr)) & 0x7ffffffffffffLLU; |
101 | u128 c = ((tctr) >> (51)); |
102 | tmp[ctr] = ((u128)(r0)); |
103 | tmp[ctr + 1] = ((tctrp1) + (c)); |
104 | } |
105 | |
106 | { |
107 | u32 ctr = 2; |
108 | u128 tctr = tmp[ctr]; |
109 | u128 tctrp1 = tmp[ctr + 1]; |
110 | u64 r0 = ((u64)(tctr)) & 0x7ffffffffffffLLU; |
111 | u128 c = ((tctr) >> (51)); |
112 | tmp[ctr] = ((u128)(r0)); |
113 | tmp[ctr + 1] = ((tctrp1) + (c)); |
114 | } |
115 | { |
116 | u32 ctr = 3; |
117 | u128 tctr = tmp[ctr]; |
118 | u128 tctrp1 = tmp[ctr + 1]; |
119 | u64 r0 = ((u64)(tctr)) & 0x7ffffffffffffLLU; |
120 | u128 c = ((tctr) >> (51)); |
121 | tmp[ctr] = ((u128)(r0)); |
122 | tmp[ctr + 1] = ((tctrp1) + (c)); |
123 | } |
124 | } |
125 | |
126 | static __always_inline void fmul_shift_reduce(u64 *output) |
127 | { |
128 | u64 tmp = output[4]; |
129 | u64 b0; |
130 | { |
131 | u32 ctr = 5 - 0 - 1; |
132 | u64 z = output[ctr - 1]; |
133 | output[ctr] = z; |
134 | } |
135 | { |
136 | u32 ctr = 5 - 1 - 1; |
137 | u64 z = output[ctr - 1]; |
138 | output[ctr] = z; |
139 | } |
140 | { |
141 | u32 ctr = 5 - 2 - 1; |
142 | u64 z = output[ctr - 1]; |
143 | output[ctr] = z; |
144 | } |
145 | { |
146 | u32 ctr = 5 - 3 - 1; |
147 | u64 z = output[ctr - 1]; |
148 | output[ctr] = z; |
149 | } |
150 | output[0] = tmp; |
151 | b0 = output[0]; |
152 | output[0] = 19 * b0; |
153 | } |
154 | |
155 | static __always_inline void fmul_mul_shift_reduce_(u128 *output, u64 *input, |
156 | u64 *input21) |
157 | { |
158 | u32 i; |
159 | u64 input2i; |
160 | { |
161 | u64 input2i = input21[0]; |
162 | fproduct_sum_scalar_multiplication_(output, input, s: input2i); |
163 | fmul_shift_reduce(output: input); |
164 | } |
165 | { |
166 | u64 input2i = input21[1]; |
167 | fproduct_sum_scalar_multiplication_(output, input, s: input2i); |
168 | fmul_shift_reduce(output: input); |
169 | } |
170 | { |
171 | u64 input2i = input21[2]; |
172 | fproduct_sum_scalar_multiplication_(output, input, s: input2i); |
173 | fmul_shift_reduce(output: input); |
174 | } |
175 | { |
176 | u64 input2i = input21[3]; |
177 | fproduct_sum_scalar_multiplication_(output, input, s: input2i); |
178 | fmul_shift_reduce(output: input); |
179 | } |
180 | i = 4; |
181 | input2i = input21[i]; |
182 | fproduct_sum_scalar_multiplication_(output, input, s: input2i); |
183 | } |
184 | |
185 | static __always_inline void fmul_fmul(u64 *output, u64 *input, u64 *input21) |
186 | { |
187 | u64 tmp[5] = { input[0], input[1], input[2], input[3], input[4] }; |
188 | { |
189 | u128 b4; |
190 | u128 b0; |
191 | u128 b4_; |
192 | u128 b0_; |
193 | u64 i0; |
194 | u64 i1; |
195 | u64 i0_; |
196 | u64 i1_; |
197 | u128 t[5] = { 0 }; |
198 | fmul_mul_shift_reduce_(output: t, input: tmp, input21); |
199 | fproduct_carry_wide_(tmp: t); |
200 | b4 = t[4]; |
201 | b0 = t[0]; |
202 | b4_ = ((b4) & (((u128)(0x7ffffffffffffLLU)))); |
203 | b0_ = ((b0) + (((u128)(19) * (((u64)(((b4) >> (51)))))))); |
204 | t[4] = b4_; |
205 | t[0] = b0_; |
206 | fproduct_copy_from_wide_(output, input: t); |
207 | i0 = output[0]; |
208 | i1 = output[1]; |
209 | i0_ = i0 & 0x7ffffffffffffLLU; |
210 | i1_ = i1 + (i0 >> 51); |
211 | output[0] = i0_; |
212 | output[1] = i1_; |
213 | } |
214 | } |
215 | |
216 | static __always_inline void fsquare_fsquare__(u128 *tmp, u64 *output) |
217 | { |
218 | u64 r0 = output[0]; |
219 | u64 r1 = output[1]; |
220 | u64 r2 = output[2]; |
221 | u64 r3 = output[3]; |
222 | u64 r4 = output[4]; |
223 | u64 d0 = r0 * 2; |
224 | u64 d1 = r1 * 2; |
225 | u64 d2 = r2 * 2 * 19; |
226 | u64 d419 = r4 * 19; |
227 | u64 d4 = d419 * 2; |
228 | u128 s0 = ((((((u128)(r0) * (r0))) + (((u128)(d4) * (r1))))) + |
229 | (((u128)(d2) * (r3)))); |
230 | u128 s1 = ((((((u128)(d0) * (r1))) + (((u128)(d4) * (r2))))) + |
231 | (((u128)(r3 * 19) * (r3)))); |
232 | u128 s2 = ((((((u128)(d0) * (r2))) + (((u128)(r1) * (r1))))) + |
233 | (((u128)(d4) * (r3)))); |
234 | u128 s3 = ((((((u128)(d0) * (r3))) + (((u128)(d1) * (r2))))) + |
235 | (((u128)(r4) * (d419)))); |
236 | u128 s4 = ((((((u128)(d0) * (r4))) + (((u128)(d1) * (r3))))) + |
237 | (((u128)(r2) * (r2)))); |
238 | tmp[0] = s0; |
239 | tmp[1] = s1; |
240 | tmp[2] = s2; |
241 | tmp[3] = s3; |
242 | tmp[4] = s4; |
243 | } |
244 | |
245 | static __always_inline void fsquare_fsquare_(u128 *tmp, u64 *output) |
246 | { |
247 | u128 b4; |
248 | u128 b0; |
249 | u128 b4_; |
250 | u128 b0_; |
251 | u64 i0; |
252 | u64 i1; |
253 | u64 i0_; |
254 | u64 i1_; |
255 | fsquare_fsquare__(tmp, output); |
256 | fproduct_carry_wide_(tmp); |
257 | b4 = tmp[4]; |
258 | b0 = tmp[0]; |
259 | b4_ = ((b4) & (((u128)(0x7ffffffffffffLLU)))); |
260 | b0_ = ((b0) + (((u128)(19) * (((u64)(((b4) >> (51)))))))); |
261 | tmp[4] = b4_; |
262 | tmp[0] = b0_; |
263 | fproduct_copy_from_wide_(output, input: tmp); |
264 | i0 = output[0]; |
265 | i1 = output[1]; |
266 | i0_ = i0 & 0x7ffffffffffffLLU; |
267 | i1_ = i1 + (i0 >> 51); |
268 | output[0] = i0_; |
269 | output[1] = i1_; |
270 | } |
271 | |
272 | static __always_inline void fsquare_fsquare_times_(u64 *output, u128 *tmp, |
273 | u32 count1) |
274 | { |
275 | u32 i; |
276 | fsquare_fsquare_(tmp, output); |
277 | for (i = 1; i < count1; ++i) |
278 | fsquare_fsquare_(tmp, output); |
279 | } |
280 | |
281 | static __always_inline void fsquare_fsquare_times(u64 *output, u64 *input, |
282 | u32 count1) |
283 | { |
284 | u128 t[5]; |
285 | memcpy(output, input, 5 * sizeof(*input)); |
286 | fsquare_fsquare_times_(output, tmp: t, count1); |
287 | } |
288 | |
289 | static __always_inline void fsquare_fsquare_times_inplace(u64 *output, |
290 | u32 count1) |
291 | { |
292 | u128 t[5]; |
293 | fsquare_fsquare_times_(output, tmp: t, count1); |
294 | } |
295 | |
296 | static __always_inline void crecip_crecip(u64 *out, u64 *z) |
297 | { |
298 | u64 buf[20] = { 0 }; |
299 | u64 *a0 = buf; |
300 | u64 *t00 = buf + 5; |
301 | u64 *b0 = buf + 10; |
302 | u64 *t01; |
303 | u64 *b1; |
304 | u64 *c0; |
305 | u64 *a; |
306 | u64 *t0; |
307 | u64 *b; |
308 | u64 *c; |
309 | fsquare_fsquare_times(output: a0, input: z, count1: 1); |
310 | fsquare_fsquare_times(output: t00, input: a0, count1: 2); |
311 | fmul_fmul(output: b0, input: t00, input21: z); |
312 | fmul_fmul(output: a0, input: b0, input21: a0); |
313 | fsquare_fsquare_times(output: t00, input: a0, count1: 1); |
314 | fmul_fmul(output: b0, input: t00, input21: b0); |
315 | fsquare_fsquare_times(output: t00, input: b0, count1: 5); |
316 | t01 = buf + 5; |
317 | b1 = buf + 10; |
318 | c0 = buf + 15; |
319 | fmul_fmul(output: b1, input: t01, input21: b1); |
320 | fsquare_fsquare_times(output: t01, input: b1, count1: 10); |
321 | fmul_fmul(output: c0, input: t01, input21: b1); |
322 | fsquare_fsquare_times(output: t01, input: c0, count1: 20); |
323 | fmul_fmul(output: t01, input: t01, input21: c0); |
324 | fsquare_fsquare_times_inplace(output: t01, count1: 10); |
325 | fmul_fmul(output: b1, input: t01, input21: b1); |
326 | fsquare_fsquare_times(output: t01, input: b1, count1: 50); |
327 | a = buf; |
328 | t0 = buf + 5; |
329 | b = buf + 10; |
330 | c = buf + 15; |
331 | fmul_fmul(output: c, input: t0, input21: b); |
332 | fsquare_fsquare_times(output: t0, input: c, count1: 100); |
333 | fmul_fmul(output: t0, input: t0, input21: c); |
334 | fsquare_fsquare_times_inplace(output: t0, count1: 50); |
335 | fmul_fmul(output: t0, input: t0, input21: b); |
336 | fsquare_fsquare_times_inplace(output: t0, count1: 5); |
337 | fmul_fmul(output: out, input: t0, input21: a); |
338 | } |
339 | |
340 | static __always_inline void fsum(u64 *a, u64 *b) |
341 | { |
342 | a[0] += b[0]; |
343 | a[1] += b[1]; |
344 | a[2] += b[2]; |
345 | a[3] += b[3]; |
346 | a[4] += b[4]; |
347 | } |
348 | |
349 | static __always_inline void fdifference(u64 *a, u64 *b) |
350 | { |
351 | u64 tmp[5] = { 0 }; |
352 | u64 b0; |
353 | u64 b1; |
354 | u64 b2; |
355 | u64 b3; |
356 | u64 b4; |
357 | memcpy(tmp, b, 5 * sizeof(*b)); |
358 | b0 = tmp[0]; |
359 | b1 = tmp[1]; |
360 | b2 = tmp[2]; |
361 | b3 = tmp[3]; |
362 | b4 = tmp[4]; |
363 | tmp[0] = b0 + 0x3fffffffffff68LLU; |
364 | tmp[1] = b1 + 0x3ffffffffffff8LLU; |
365 | tmp[2] = b2 + 0x3ffffffffffff8LLU; |
366 | tmp[3] = b3 + 0x3ffffffffffff8LLU; |
367 | tmp[4] = b4 + 0x3ffffffffffff8LLU; |
368 | { |
369 | u64 xi = a[0]; |
370 | u64 yi = tmp[0]; |
371 | a[0] = yi - xi; |
372 | } |
373 | { |
374 | u64 xi = a[1]; |
375 | u64 yi = tmp[1]; |
376 | a[1] = yi - xi; |
377 | } |
378 | { |
379 | u64 xi = a[2]; |
380 | u64 yi = tmp[2]; |
381 | a[2] = yi - xi; |
382 | } |
383 | { |
384 | u64 xi = a[3]; |
385 | u64 yi = tmp[3]; |
386 | a[3] = yi - xi; |
387 | } |
388 | { |
389 | u64 xi = a[4]; |
390 | u64 yi = tmp[4]; |
391 | a[4] = yi - xi; |
392 | } |
393 | } |
394 | |
395 | static __always_inline void fscalar(u64 *output, u64 *b, u64 s) |
396 | { |
397 | u128 tmp[5]; |
398 | u128 b4; |
399 | u128 b0; |
400 | u128 b4_; |
401 | u128 b0_; |
402 | { |
403 | u64 xi = b[0]; |
404 | tmp[0] = ((u128)(xi) * (s)); |
405 | } |
406 | { |
407 | u64 xi = b[1]; |
408 | tmp[1] = ((u128)(xi) * (s)); |
409 | } |
410 | { |
411 | u64 xi = b[2]; |
412 | tmp[2] = ((u128)(xi) * (s)); |
413 | } |
414 | { |
415 | u64 xi = b[3]; |
416 | tmp[3] = ((u128)(xi) * (s)); |
417 | } |
418 | { |
419 | u64 xi = b[4]; |
420 | tmp[4] = ((u128)(xi) * (s)); |
421 | } |
422 | fproduct_carry_wide_(tmp); |
423 | b4 = tmp[4]; |
424 | b0 = tmp[0]; |
425 | b4_ = ((b4) & (((u128)(0x7ffffffffffffLLU)))); |
426 | b0_ = ((b0) + (((u128)(19) * (((u64)(((b4) >> (51)))))))); |
427 | tmp[4] = b4_; |
428 | tmp[0] = b0_; |
429 | fproduct_copy_from_wide_(output, input: tmp); |
430 | } |
431 | |
432 | static __always_inline void fmul(u64 *output, u64 *a, u64 *b) |
433 | { |
434 | fmul_fmul(output, input: a, input21: b); |
435 | } |
436 | |
437 | static __always_inline void crecip(u64 *output, u64 *input) |
438 | { |
439 | crecip_crecip(out: output, z: input); |
440 | } |
441 | |
442 | static __always_inline void point_swap_conditional_step(u64 *a, u64 *b, |
443 | u64 swap1, u32 ctr) |
444 | { |
445 | u32 i = ctr - 1; |
446 | u64 ai = a[i]; |
447 | u64 bi = b[i]; |
448 | u64 x = swap1 & (ai ^ bi); |
449 | u64 ai1 = ai ^ x; |
450 | u64 bi1 = bi ^ x; |
451 | a[i] = ai1; |
452 | b[i] = bi1; |
453 | } |
454 | |
455 | static __always_inline void point_swap_conditional5(u64 *a, u64 *b, u64 swap1) |
456 | { |
457 | point_swap_conditional_step(a, b, swap1, ctr: 5); |
458 | point_swap_conditional_step(a, b, swap1, ctr: 4); |
459 | point_swap_conditional_step(a, b, swap1, ctr: 3); |
460 | point_swap_conditional_step(a, b, swap1, ctr: 2); |
461 | point_swap_conditional_step(a, b, swap1, ctr: 1); |
462 | } |
463 | |
464 | static __always_inline void point_swap_conditional(u64 *a, u64 *b, u64 iswap) |
465 | { |
466 | u64 swap1 = 0 - iswap; |
467 | point_swap_conditional5(a, b, swap1); |
468 | point_swap_conditional5(a: a + 5, b: b + 5, swap1); |
469 | } |
470 | |
471 | static __always_inline void point_copy(u64 *output, u64 *input) |
472 | { |
473 | memcpy(output, input, 5 * sizeof(*input)); |
474 | memcpy(output + 5, input + 5, 5 * sizeof(*input)); |
475 | } |
476 | |
477 | static __always_inline void addanddouble_fmonty(u64 *pp, u64 *ppq, u64 *p, |
478 | u64 *pq, u64 *qmqp) |
479 | { |
480 | u64 *qx = qmqp; |
481 | u64 *x2 = pp; |
482 | u64 *z2 = pp + 5; |
483 | u64 *x3 = ppq; |
484 | u64 *z3 = ppq + 5; |
485 | u64 *x = p; |
486 | u64 *z = p + 5; |
487 | u64 *xprime = pq; |
488 | u64 *zprime = pq + 5; |
489 | u64 buf[40] = { 0 }; |
490 | u64 *origx = buf; |
491 | u64 *origxprime0 = buf + 5; |
492 | u64 *xxprime0; |
493 | u64 *zzprime0; |
494 | u64 *origxprime; |
495 | xxprime0 = buf + 25; |
496 | zzprime0 = buf + 30; |
497 | memcpy(origx, x, 5 * sizeof(*x)); |
498 | fsum(a: x, b: z); |
499 | fdifference(a: z, b: origx); |
500 | memcpy(origxprime0, xprime, 5 * sizeof(*xprime)); |
501 | fsum(a: xprime, b: zprime); |
502 | fdifference(a: zprime, b: origxprime0); |
503 | fmul(output: xxprime0, a: xprime, b: z); |
504 | fmul(output: zzprime0, a: x, b: zprime); |
505 | origxprime = buf + 5; |
506 | { |
507 | u64 *xx0; |
508 | u64 *zz0; |
509 | u64 *xxprime; |
510 | u64 *zzprime; |
511 | u64 *zzzprime; |
512 | xx0 = buf + 15; |
513 | zz0 = buf + 20; |
514 | xxprime = buf + 25; |
515 | zzprime = buf + 30; |
516 | zzzprime = buf + 35; |
517 | memcpy(origxprime, xxprime, 5 * sizeof(*xxprime)); |
518 | fsum(a: xxprime, b: zzprime); |
519 | fdifference(a: zzprime, b: origxprime); |
520 | fsquare_fsquare_times(output: x3, input: xxprime, count1: 1); |
521 | fsquare_fsquare_times(output: zzzprime, input: zzprime, count1: 1); |
522 | fmul(output: z3, a: zzzprime, b: qx); |
523 | fsquare_fsquare_times(output: xx0, input: x, count1: 1); |
524 | fsquare_fsquare_times(output: zz0, input: z, count1: 1); |
525 | { |
526 | u64 *zzz; |
527 | u64 *xx; |
528 | u64 *zz; |
529 | u64 scalar; |
530 | zzz = buf + 10; |
531 | xx = buf + 15; |
532 | zz = buf + 20; |
533 | fmul(output: x2, a: xx, b: zz); |
534 | fdifference(a: zz, b: xx); |
535 | scalar = 121665; |
536 | fscalar(output: zzz, b: zz, s: scalar); |
537 | fsum(a: zzz, b: xx); |
538 | fmul(output: z2, a: zzz, b: zz); |
539 | } |
540 | } |
541 | } |
542 | |
543 | static __always_inline void |
544 | ladder_smallloop_cmult_small_loop_step(u64 *nq, u64 *nqpq, u64 *nq2, u64 *nqpq2, |
545 | u64 *q, u8 byt) |
546 | { |
547 | u64 bit0 = (u64)(byt >> 7); |
548 | u64 bit; |
549 | point_swap_conditional(a: nq, b: nqpq, iswap: bit0); |
550 | addanddouble_fmonty(pp: nq2, ppq: nqpq2, p: nq, pq: nqpq, qmqp: q); |
551 | bit = (u64)(byt >> 7); |
552 | point_swap_conditional(a: nq2, b: nqpq2, iswap: bit); |
553 | } |
554 | |
555 | static __always_inline void |
556 | ladder_smallloop_cmult_small_loop_double_step(u64 *nq, u64 *nqpq, u64 *nq2, |
557 | u64 *nqpq2, u64 *q, u8 byt) |
558 | { |
559 | u8 byt1; |
560 | ladder_smallloop_cmult_small_loop_step(nq, nqpq, nq2, nqpq2, q, byt); |
561 | byt1 = byt << 1; |
562 | ladder_smallloop_cmult_small_loop_step(nq: nq2, nqpq: nqpq2, nq2: nq, nqpq2: nqpq, q, byt: byt1); |
563 | } |
564 | |
565 | static __always_inline void |
566 | ladder_smallloop_cmult_small_loop(u64 *nq, u64 *nqpq, u64 *nq2, u64 *nqpq2, |
567 | u64 *q, u8 byt, u32 i) |
568 | { |
569 | while (i--) { |
570 | ladder_smallloop_cmult_small_loop_double_step(nq, nqpq, nq2, |
571 | nqpq2, q, byt); |
572 | byt <<= 2; |
573 | } |
574 | } |
575 | |
576 | static __always_inline void ladder_bigloop_cmult_big_loop(u8 *n1, u64 *nq, |
577 | u64 *nqpq, u64 *nq2, |
578 | u64 *nqpq2, u64 *q, |
579 | u32 i) |
580 | { |
581 | while (i--) { |
582 | u8 byte = n1[i]; |
583 | ladder_smallloop_cmult_small_loop(nq, nqpq, nq2, nqpq2, q, |
584 | byt: byte, i: 4); |
585 | } |
586 | } |
587 | |
588 | static void ladder_cmult(u64 *result, u8 *n1, u64 *q) |
589 | { |
590 | u64 point_buf[40] = { 0 }; |
591 | u64 *nq = point_buf; |
592 | u64 *nqpq = point_buf + 10; |
593 | u64 *nq2 = point_buf + 20; |
594 | u64 *nqpq2 = point_buf + 30; |
595 | point_copy(output: nqpq, input: q); |
596 | nq[0] = 1; |
597 | ladder_bigloop_cmult_big_loop(n1, nq, nqpq, nq2, nqpq2, q, i: 32); |
598 | point_copy(output: result, input: nq); |
599 | } |
600 | |
601 | static __always_inline void format_fexpand(u64 *output, const u8 *input) |
602 | { |
603 | const u8 *x00 = input + 6; |
604 | const u8 *x01 = input + 12; |
605 | const u8 *x02 = input + 19; |
606 | const u8 *x0 = input + 24; |
607 | u64 i0, i1, i2, i3, i4, output0, output1, output2, output3, output4; |
608 | i0 = get_unaligned_le64(p: input); |
609 | i1 = get_unaligned_le64(p: x00); |
610 | i2 = get_unaligned_le64(p: x01); |
611 | i3 = get_unaligned_le64(p: x02); |
612 | i4 = get_unaligned_le64(p: x0); |
613 | output0 = i0 & 0x7ffffffffffffLLU; |
614 | output1 = i1 >> 3 & 0x7ffffffffffffLLU; |
615 | output2 = i2 >> 6 & 0x7ffffffffffffLLU; |
616 | output3 = i3 >> 1 & 0x7ffffffffffffLLU; |
617 | output4 = i4 >> 12 & 0x7ffffffffffffLLU; |
618 | output[0] = output0; |
619 | output[1] = output1; |
620 | output[2] = output2; |
621 | output[3] = output3; |
622 | output[4] = output4; |
623 | } |
624 | |
625 | static __always_inline void format_fcontract_first_carry_pass(u64 *input) |
626 | { |
627 | u64 t0 = input[0]; |
628 | u64 t1 = input[1]; |
629 | u64 t2 = input[2]; |
630 | u64 t3 = input[3]; |
631 | u64 t4 = input[4]; |
632 | u64 t1_ = t1 + (t0 >> 51); |
633 | u64 t0_ = t0 & 0x7ffffffffffffLLU; |
634 | u64 t2_ = t2 + (t1_ >> 51); |
635 | u64 t1__ = t1_ & 0x7ffffffffffffLLU; |
636 | u64 t3_ = t3 + (t2_ >> 51); |
637 | u64 t2__ = t2_ & 0x7ffffffffffffLLU; |
638 | u64 t4_ = t4 + (t3_ >> 51); |
639 | u64 t3__ = t3_ & 0x7ffffffffffffLLU; |
640 | input[0] = t0_; |
641 | input[1] = t1__; |
642 | input[2] = t2__; |
643 | input[3] = t3__; |
644 | input[4] = t4_; |
645 | } |
646 | |
647 | static __always_inline void format_fcontract_first_carry_full(u64 *input) |
648 | { |
649 | format_fcontract_first_carry_pass(input); |
650 | modulo_carry_top(b: input); |
651 | } |
652 | |
653 | static __always_inline void format_fcontract_second_carry_pass(u64 *input) |
654 | { |
655 | u64 t0 = input[0]; |
656 | u64 t1 = input[1]; |
657 | u64 t2 = input[2]; |
658 | u64 t3 = input[3]; |
659 | u64 t4 = input[4]; |
660 | u64 t1_ = t1 + (t0 >> 51); |
661 | u64 t0_ = t0 & 0x7ffffffffffffLLU; |
662 | u64 t2_ = t2 + (t1_ >> 51); |
663 | u64 t1__ = t1_ & 0x7ffffffffffffLLU; |
664 | u64 t3_ = t3 + (t2_ >> 51); |
665 | u64 t2__ = t2_ & 0x7ffffffffffffLLU; |
666 | u64 t4_ = t4 + (t3_ >> 51); |
667 | u64 t3__ = t3_ & 0x7ffffffffffffLLU; |
668 | input[0] = t0_; |
669 | input[1] = t1__; |
670 | input[2] = t2__; |
671 | input[3] = t3__; |
672 | input[4] = t4_; |
673 | } |
674 | |
675 | static __always_inline void format_fcontract_second_carry_full(u64 *input) |
676 | { |
677 | u64 i0; |
678 | u64 i1; |
679 | u64 i0_; |
680 | u64 i1_; |
681 | format_fcontract_second_carry_pass(input); |
682 | modulo_carry_top(b: input); |
683 | i0 = input[0]; |
684 | i1 = input[1]; |
685 | i0_ = i0 & 0x7ffffffffffffLLU; |
686 | i1_ = i1 + (i0 >> 51); |
687 | input[0] = i0_; |
688 | input[1] = i1_; |
689 | } |
690 | |
691 | static __always_inline void format_fcontract_trim(u64 *input) |
692 | { |
693 | u64 a0 = input[0]; |
694 | u64 a1 = input[1]; |
695 | u64 a2 = input[2]; |
696 | u64 a3 = input[3]; |
697 | u64 a4 = input[4]; |
698 | u64 mask0 = u64_gte_mask(a: a0, b: 0x7ffffffffffedLLU); |
699 | u64 mask1 = u64_eq_mask(a: a1, b: 0x7ffffffffffffLLU); |
700 | u64 mask2 = u64_eq_mask(a: a2, b: 0x7ffffffffffffLLU); |
701 | u64 mask3 = u64_eq_mask(a: a3, b: 0x7ffffffffffffLLU); |
702 | u64 mask4 = u64_eq_mask(a: a4, b: 0x7ffffffffffffLLU); |
703 | u64 mask = (((mask0 & mask1) & mask2) & mask3) & mask4; |
704 | u64 a0_ = a0 - (0x7ffffffffffedLLU & mask); |
705 | u64 a1_ = a1 - (0x7ffffffffffffLLU & mask); |
706 | u64 a2_ = a2 - (0x7ffffffffffffLLU & mask); |
707 | u64 a3_ = a3 - (0x7ffffffffffffLLU & mask); |
708 | u64 a4_ = a4 - (0x7ffffffffffffLLU & mask); |
709 | input[0] = a0_; |
710 | input[1] = a1_; |
711 | input[2] = a2_; |
712 | input[3] = a3_; |
713 | input[4] = a4_; |
714 | } |
715 | |
716 | static __always_inline void format_fcontract_store(u8 *output, u64 *input) |
717 | { |
718 | u64 t0 = input[0]; |
719 | u64 t1 = input[1]; |
720 | u64 t2 = input[2]; |
721 | u64 t3 = input[3]; |
722 | u64 t4 = input[4]; |
723 | u64 o0 = t1 << 51 | t0; |
724 | u64 o1 = t2 << 38 | t1 >> 13; |
725 | u64 o2 = t3 << 25 | t2 >> 26; |
726 | u64 o3 = t4 << 12 | t3 >> 39; |
727 | u8 *b0 = output; |
728 | u8 *b1 = output + 8; |
729 | u8 *b2 = output + 16; |
730 | u8 *b3 = output + 24; |
731 | put_unaligned_le64(val: o0, p: b0); |
732 | put_unaligned_le64(val: o1, p: b1); |
733 | put_unaligned_le64(val: o2, p: b2); |
734 | put_unaligned_le64(val: o3, p: b3); |
735 | } |
736 | |
737 | static __always_inline void format_fcontract(u8 *output, u64 *input) |
738 | { |
739 | format_fcontract_first_carry_full(input); |
740 | format_fcontract_second_carry_full(input); |
741 | format_fcontract_trim(input); |
742 | format_fcontract_store(output, input); |
743 | } |
744 | |
745 | static __always_inline void format_scalar_of_point(u8 *scalar, u64 *point) |
746 | { |
747 | u64 *x = point; |
748 | u64 *z = point + 5; |
749 | u64 buf[10] __aligned(32) = { 0 }; |
750 | u64 *zmone = buf; |
751 | u64 *sc = buf + 5; |
752 | crecip(output: zmone, input: z); |
753 | fmul(output: sc, a: x, b: zmone); |
754 | format_fcontract(output: scalar, input: sc); |
755 | } |
756 | |
757 | void curve25519_generic(u8 mypublic[CURVE25519_KEY_SIZE], |
758 | const u8 secret[CURVE25519_KEY_SIZE], |
759 | const u8 basepoint[CURVE25519_KEY_SIZE]) |
760 | { |
761 | u64 buf0[10] __aligned(32) = { 0 }; |
762 | u64 *x0 = buf0; |
763 | u64 *z = buf0 + 5; |
764 | u64 *q; |
765 | format_fexpand(output: x0, input: basepoint); |
766 | z[0] = 1; |
767 | q = buf0; |
768 | { |
769 | u8 e[32] __aligned(32) = { 0 }; |
770 | u8 *scalar; |
771 | memcpy(e, secret, 32); |
772 | curve25519_clamp_secret(secret: e); |
773 | scalar = e; |
774 | { |
775 | u64 buf[15] = { 0 }; |
776 | u64 *nq = buf; |
777 | u64 *x = nq; |
778 | x[0] = 1; |
779 | ladder_cmult(result: nq, n1: scalar, q); |
780 | format_scalar_of_point(scalar: mypublic, point: nq); |
781 | memzero_explicit(s: buf, count: sizeof(buf)); |
782 | } |
783 | memzero_explicit(s: e, count: sizeof(e)); |
784 | } |
785 | memzero_explicit(s: buf0, count: sizeof(buf0)); |
786 | } |
787 | |