curve25519-hacl64.c 17 KB

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