| 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, input2i); |
| 163 | fmul_shift_reduce(input); |
| 164 | } |
| 165 | { |
| 166 | u64 input2i = input21[1]; |
| 167 | fproduct_sum_scalar_multiplication_(output, input, input2i); |
| 168 | fmul_shift_reduce(input); |
| 169 | } |
| 170 | { |
| 171 | u64 input2i = input21[2]; |
| 172 | fproduct_sum_scalar_multiplication_(output, input, input2i); |
| 173 | fmul_shift_reduce(input); |
| 174 | } |
| 175 | { |
| 176 | u64 input2i = input21[3]; |
| 177 | fproduct_sum_scalar_multiplication_(output, input, input2i); |
| 178 | fmul_shift_reduce(input); |
| 179 | } |
| 180 | i = 4; |
| 181 | input2i = input21[i]; |
| 182 | fproduct_sum_scalar_multiplication_(output, input, 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_(t, tmp, input21); |
| 199 | fproduct_carry_wide_(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, 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, 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, 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, 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(a0, z, 1); |
| 310 | fsquare_fsquare_times(t00, a0, 2); |
| 311 | fmul_fmul(b0, t00, z); |
| 312 | fmul_fmul(a0, b0, a0); |
| 313 | fsquare_fsquare_times(t00, a0, 1); |
| 314 | fmul_fmul(b0, t00, b0); |
| 315 | fsquare_fsquare_times(t00, b0, 5); |
| 316 | t01 = buf + 5; |
| 317 | b1 = buf + 10; |
| 318 | c0 = buf + 15; |
| 319 | fmul_fmul(b1, t01, b1); |
| 320 | fsquare_fsquare_times(t01, b1, 10); |
| 321 | fmul_fmul(c0, t01, b1); |
| 322 | fsquare_fsquare_times(t01, c0, 20); |
| 323 | fmul_fmul(t01, t01, c0); |
| 324 | fsquare_fsquare_times_inplace(t01, 10); |
| 325 | fmul_fmul(b1, t01, b1); |
| 326 | fsquare_fsquare_times(t01, b1, 50); |
| 327 | a = buf; |
| 328 | t0 = buf + 5; |
| 329 | b = buf + 10; |
| 330 | c = buf + 15; |
| 331 | fmul_fmul(c, t0, b); |
| 332 | fsquare_fsquare_times(t0, c, 100); |
| 333 | fmul_fmul(t0, t0, c); |
| 334 | fsquare_fsquare_times_inplace(t0, 50); |
| 335 | fmul_fmul(t0, t0, b); |
| 336 | fsquare_fsquare_times_inplace(t0, 5); |
| 337 | fmul_fmul(out, t0, 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, tmp); |
| 430 | } |
| 431 | |
| 432 | static __always_inline void fmul(u64 *output, u64 *a, u64 *b) |
| 433 | { |
| 434 | fmul_fmul(output, a, b); |
| 435 | } |
| 436 | |
| 437 | static __always_inline void crecip(u64 *output, u64 *input) |
| 438 | { |
| 439 | crecip_crecip(output, 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, 5); |
| 458 | point_swap_conditional_step(a, b, swap1, 4); |
| 459 | point_swap_conditional_step(a, b, swap1, 3); |
| 460 | point_swap_conditional_step(a, b, swap1, 2); |
| 461 | point_swap_conditional_step(a, b, swap1, 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 + 5, 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(x, z); |
| 499 | fdifference(z, origx); |
| 500 | memcpy(origxprime0, xprime, 5 * sizeof(*xprime)); |
| 501 | fsum(xprime, zprime); |
| 502 | fdifference(zprime, origxprime0); |
| 503 | fmul(xxprime0, xprime, z); |
| 504 | fmul(zzprime0, x, 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(xxprime, zzprime); |
| 519 | fdifference(zzprime, origxprime); |
| 520 | fsquare_fsquare_times(x3, xxprime, 1); |
| 521 | fsquare_fsquare_times(zzzprime, zzprime, 1); |
| 522 | fmul(z3, zzzprime, qx); |
| 523 | fsquare_fsquare_times(xx0, x, 1); |
| 524 | fsquare_fsquare_times(zz0, z, 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(x2, xx, zz); |
| 534 | fdifference(zz, xx); |
| 535 | scalar = 121665; |
| 536 | fscalar(zzz, zz, scalar); |
| 537 | fsum(zzz, xx); |
| 538 | fmul(z2, zzz, 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(nq, nqpq, bit0); |
| 550 | addanddouble_fmonty(nq2, nqpq2, nq, nqpq, q); |
| 551 | bit = (u64)(byt >> 7); |
| 552 | point_swap_conditional(nq2, nqpq2, 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(nq2, nqpq2, nq, nqpq, q, 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 | byte, 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(nqpq, q); |
| 596 | nq[0] = 1; |
| 597 | ladder_bigloop_cmult_big_loop(n1, nq, nqpq, nq2, nqpq2, q, 32); |
| 598 | point_copy(result, 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(input); |
| 609 | i1 = get_unaligned_le64(x00); |
| 610 | i2 = get_unaligned_le64(x01); |
| 611 | i3 = get_unaligned_le64(x02); |
| 612 | i4 = get_unaligned_le64(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(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(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(a0, 0x7ffffffffffedLLU); |
| 699 | u64 mask1 = u64_eq_mask(a1, 0x7ffffffffffffLLU); |
| 700 | u64 mask2 = u64_eq_mask(a2, 0x7ffffffffffffLLU); |
| 701 | u64 mask3 = u64_eq_mask(a3, 0x7ffffffffffffLLU); |
| 702 | u64 mask4 = u64_eq_mask(a4, 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(o0, b0); |
| 732 | put_unaligned_le64(o1, b1); |
| 733 | put_unaligned_le64(o2, b2); |
| 734 | put_unaligned_le64(o3, 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(zmone, z); |
| 753 | fmul(sc, x, zmone); |
| 754 | format_fcontract(scalar, 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(x0, 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(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(nq, scalar, q); |
| 780 | format_scalar_of_point(mypublic, nq); |
| 781 | memzero_explicit(buf, sizeof(buf)); |
| 782 | } |
| 783 | memzero_explicit(e, sizeof(e)); |
| 784 | } |
| 785 | memzero_explicit(buf0, sizeof(buf0)); |
| 786 | } |