1 /* $OpenBSD: curve25519.c,v 1.2 2020/07/22 13:54:30 tobhe Exp $ */ 2 /* 3 * Copyright (C) 2018-2020 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved. 4 * Copyright (C) 2015-2016 The fiat-crypto Authors. 5 * 6 * Permission to use, copy, modify, and distribute this software for any 7 * purpose with or without fee is hereby granted, provided that the above 8 * copyright notice and this permission notice appear in all copies. 9 * 10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 17 * 18 * This contains two implementation: a machine-generated formally verified 19 * implementation of Curve25519 ECDH from: 20 * <https://github.com/mit-plv/fiat-crypto>. Though originally machine 21 * generated, it has been tweaked to be suitable for use in the kernel. It is 22 * optimized for 32-bit machines and machines that cannot work efficiently with 23 * 128-bit integer types. 24 */ 25 26 #include <sys/types.h> 27 #include <sys/systm.h> 28 #include <sys/endian.h> 29 30 #include <crypto/curve25519/curve25519.h> 31 32 static const uint8_t null_point[CURVE25519_KEY_SIZE]; 33 static const uint8_t base_point[CURVE25519_KEY_SIZE] = { 9 }; 34 35 int 36 curve25519_generate_public(uint8_t pub[CURVE25519_KEY_SIZE], 37 const uint8_t secret[CURVE25519_KEY_SIZE]) 38 { 39 if (timingsafe_bcmp(secret, null_point, CURVE25519_KEY_SIZE) == 0) 40 return 0; 41 return curve25519(pub, secret, base_point); 42 } 43 44 static __inline __always_inline uint32_t 45 get_unaligned_le32(const uint8_t *a) 46 { 47 uint32_t l; 48 memcpy(&l, a, sizeof(l)); 49 return le32toh(l); 50 } 51 52 /* fe means field element. Here the field is \Z/(2^255-19). An element t, 53 * entries t[0]...t[9], represents the integer t[0]+2^26 t[1]+2^51 t[2]+2^77 54 * t[3]+2^102 t[4]+...+2^230 t[9]. 55 * fe limbs are bounded by 1.125*2^26,1.125*2^25,1.125*2^26,1.125*2^25,etc. 56 * Multiplication and carrying produce fe from fe_loose. 57 */ 58 typedef struct fe { uint32_t v[10]; } fe; 59 60 /* fe_loose limbs are bounded by 3.375*2^26,3.375*2^25,3.375*2^26,3.375*2^25,etc 61 * Addition and subtraction produce fe_loose from (fe, fe). 62 */ 63 typedef struct fe_loose { uint32_t v[10]; } fe_loose; 64 65 static __inline __always_inline void 66 fe_frombytes_impl(uint32_t h[10], const uint8_t *s) 67 { 68 /* Ignores top bit of s. */ 69 uint32_t a0 = get_unaligned_le32(s); 70 uint32_t a1 = get_unaligned_le32(s+4); 71 uint32_t a2 = get_unaligned_le32(s+8); 72 uint32_t a3 = get_unaligned_le32(s+12); 73 uint32_t a4 = get_unaligned_le32(s+16); 74 uint32_t a5 = get_unaligned_le32(s+20); 75 uint32_t a6 = get_unaligned_le32(s+24); 76 uint32_t a7 = get_unaligned_le32(s+28); 77 h[0] = a0&((1<<26)-1); /* 26 used, 32-26 left. 26 */ 78 h[1] = (a0>>26) | ((a1&((1<<19)-1))<< 6); /* (32-26) + 19 = 6+19 = 25 */ 79 h[2] = (a1>>19) | ((a2&((1<<13)-1))<<13); /* (32-19) + 13 = 13+13 = 26 */ 80 h[3] = (a2>>13) | ((a3&((1<< 6)-1))<<19); /* (32-13) + 6 = 19+ 6 = 25 */ 81 h[4] = (a3>> 6); /* (32- 6) = 26 */ 82 h[5] = a4&((1<<25)-1); /* 25 */ 83 h[6] = (a4>>25) | ((a5&((1<<19)-1))<< 7); /* (32-25) + 19 = 7+19 = 26 */ 84 h[7] = (a5>>19) | ((a6&((1<<12)-1))<<13); /* (32-19) + 12 = 13+12 = 25 */ 85 h[8] = (a6>>12) | ((a7&((1<< 6)-1))<<20); /* (32-12) + 6 = 20+ 6 = 26 */ 86 h[9] = (a7>> 6)&((1<<25)-1); /* 25 */ 87 } 88 89 static __inline __always_inline void 90 fe_frombytes(fe *h, const uint8_t *s) 91 { 92 fe_frombytes_impl(h->v, s); 93 } 94 95 static __inline __always_inline uint8_t /*bool*/ 96 addcarryx_u25(uint8_t /*bool*/ c, uint32_t a, uint32_t b, uint32_t *low) 97 { 98 /* This function extracts 25 bits of result and 1 bit of carry 99 * (26 total), so a 32-bit intermediate is sufficient. 100 */ 101 uint32_t x = a + b + c; 102 *low = x & ((1 << 25) - 1); 103 return (x >> 25) & 1; 104 } 105 106 static __inline __always_inline uint8_t /*bool*/ 107 addcarryx_u26(uint8_t /*bool*/ c, uint32_t a, uint32_t b, uint32_t *low) 108 { 109 /* This function extracts 26 bits of result and 1 bit of carry 110 * (27 total), so a 32-bit intermediate is sufficient. 111 */ 112 uint32_t x = a + b + c; 113 *low = x & ((1 << 26) - 1); 114 return (x >> 26) & 1; 115 } 116 117 static __inline __always_inline uint8_t /*bool*/ 118 subborrow_u25(uint8_t /*bool*/ c, uint32_t a, uint32_t b, uint32_t *low) 119 { 120 /* This function extracts 25 bits of result and 1 bit of borrow 121 * (26 total), so a 32-bit intermediate is sufficient. 122 */ 123 uint32_t x = a - b - c; 124 *low = x & ((1 << 25) - 1); 125 return x >> 31; 126 } 127 128 static __inline __always_inline uint8_t /*bool*/ 129 subborrow_u26(uint8_t /*bool*/ c, uint32_t a, uint32_t b, uint32_t *low) 130 { 131 /* This function extracts 26 bits of result and 1 bit of borrow 132 *(27 total), so a 32-bit intermediate is sufficient. 133 */ 134 uint32_t x = a - b - c; 135 *low = x & ((1 << 26) - 1); 136 return x >> 31; 137 } 138 139 static __inline __always_inline uint32_t 140 cmovznz32(uint32_t t, uint32_t z, uint32_t nz) 141 { 142 t = -!!t; /* all set if nonzero, 0 if 0 */ 143 return (t&nz) | ((~t)&z); 144 } 145 146 static __inline __always_inline void 147 fe_freeze(uint32_t out[10], const uint32_t in1[10]) 148 { 149 const uint32_t x17 = in1[9]; 150 const uint32_t x18 = in1[8]; 151 const uint32_t x16 = in1[7]; 152 const uint32_t x14 = in1[6]; 153 const uint32_t x12 = in1[5]; 154 const uint32_t x10 = in1[4]; 155 const uint32_t x8 = in1[3]; 156 const uint32_t x6 = in1[2]; 157 const uint32_t x4 = in1[1]; 158 const uint32_t x2 = in1[0]; 159 uint32_t x20; uint8_t/*bool*/ x21 = subborrow_u26(0x0, x2, 0x3ffffed, &x20); 160 uint32_t x23; uint8_t/*bool*/ x24 = subborrow_u25(x21, x4, 0x1ffffff, &x23); 161 uint32_t x26; uint8_t/*bool*/ x27 = subborrow_u26(x24, x6, 0x3ffffff, &x26); 162 uint32_t x29; uint8_t/*bool*/ x30 = subborrow_u25(x27, x8, 0x1ffffff, &x29); 163 uint32_t x32; uint8_t/*bool*/ x33 = subborrow_u26(x30, x10, 0x3ffffff, &x32); 164 uint32_t x35; uint8_t/*bool*/ x36 = subborrow_u25(x33, x12, 0x1ffffff, &x35); 165 uint32_t x38; uint8_t/*bool*/ x39 = subborrow_u26(x36, x14, 0x3ffffff, &x38); 166 uint32_t x41; uint8_t/*bool*/ x42 = subborrow_u25(x39, x16, 0x1ffffff, &x41); 167 uint32_t x44; uint8_t/*bool*/ x45 = subborrow_u26(x42, x18, 0x3ffffff, &x44); 168 uint32_t x47; uint8_t/*bool*/ x48 = subborrow_u25(x45, x17, 0x1ffffff, &x47); 169 uint32_t x49 = cmovznz32(x48, 0x0, 0xffffffff); 170 uint32_t x50 = (x49 & 0x3ffffed); 171 uint32_t x52; uint8_t/*bool*/ x53 = addcarryx_u26(0x0, x20, x50, &x52); 172 uint32_t x54 = (x49 & 0x1ffffff); 173 uint32_t x56; uint8_t/*bool*/ x57 = addcarryx_u25(x53, x23, x54, &x56); 174 uint32_t x58 = (x49 & 0x3ffffff); 175 uint32_t x60; uint8_t/*bool*/ x61 = addcarryx_u26(x57, x26, x58, &x60); 176 uint32_t x62 = (x49 & 0x1ffffff); 177 uint32_t x64; uint8_t/*bool*/ x65 = addcarryx_u25(x61, x29, x62, &x64); 178 uint32_t x66 = (x49 & 0x3ffffff); 179 uint32_t x68; uint8_t/*bool*/ x69 = addcarryx_u26(x65, x32, x66, &x68); 180 uint32_t x70 = (x49 & 0x1ffffff); 181 uint32_t x72; uint8_t/*bool*/ x73 = addcarryx_u25(x69, x35, x70, &x72); 182 uint32_t x74 = (x49 & 0x3ffffff); 183 uint32_t x76; uint8_t/*bool*/ x77 = addcarryx_u26(x73, x38, x74, &x76); 184 uint32_t x78 = (x49 & 0x1ffffff); 185 uint32_t x80; uint8_t/*bool*/ x81 = addcarryx_u25(x77, x41, x78, &x80); 186 uint32_t x82 = (x49 & 0x3ffffff); 187 uint32_t x84; uint8_t/*bool*/ x85 = addcarryx_u26(x81, x44, x82, &x84); 188 uint32_t x86 = (x49 & 0x1ffffff); 189 uint32_t x88; addcarryx_u25(x85, x47, x86, &x88); 190 out[0] = x52; 191 out[1] = x56; 192 out[2] = x60; 193 out[3] = x64; 194 out[4] = x68; 195 out[5] = x72; 196 out[6] = x76; 197 out[7] = x80; 198 out[8] = x84; 199 out[9] = x88; 200 } 201 202 static __inline __always_inline void 203 fe_tobytes(uint8_t s[32], const fe *f) 204 { 205 uint32_t h[10]; 206 fe_freeze(h, f->v); 207 s[0] = h[0] >> 0; 208 s[1] = h[0] >> 8; 209 s[2] = h[0] >> 16; 210 s[3] = (h[0] >> 24) | (h[1] << 2); 211 s[4] = h[1] >> 6; 212 s[5] = h[1] >> 14; 213 s[6] = (h[1] >> 22) | (h[2] << 3); 214 s[7] = h[2] >> 5; 215 s[8] = h[2] >> 13; 216 s[9] = (h[2] >> 21) | (h[3] << 5); 217 s[10] = h[3] >> 3; 218 s[11] = h[3] >> 11; 219 s[12] = (h[3] >> 19) | (h[4] << 6); 220 s[13] = h[4] >> 2; 221 s[14] = h[4] >> 10; 222 s[15] = h[4] >> 18; 223 s[16] = h[5] >> 0; 224 s[17] = h[5] >> 8; 225 s[18] = h[5] >> 16; 226 s[19] = (h[5] >> 24) | (h[6] << 1); 227 s[20] = h[6] >> 7; 228 s[21] = h[6] >> 15; 229 s[22] = (h[6] >> 23) | (h[7] << 3); 230 s[23] = h[7] >> 5; 231 s[24] = h[7] >> 13; 232 s[25] = (h[7] >> 21) | (h[8] << 4); 233 s[26] = h[8] >> 4; 234 s[27] = h[8] >> 12; 235 s[28] = (h[8] >> 20) | (h[9] << 6); 236 s[29] = h[9] >> 2; 237 s[30] = h[9] >> 10; 238 s[31] = h[9] >> 18; 239 } 240 241 /* h = f */ 242 static __inline __always_inline void 243 fe_copy(fe *h, const fe *f) 244 { 245 memmove(h, f, sizeof(uint32_t) * 10); 246 } 247 248 static __inline __always_inline void 249 fe_copy_lt(fe_loose *h, const fe *f) 250 { 251 memmove(h, f, sizeof(uint32_t) * 10); 252 } 253 254 /* h = 0 */ 255 static __inline __always_inline void 256 fe_0(fe *h) 257 { 258 memset(h, 0, sizeof(uint32_t) * 10); 259 } 260 261 /* h = 1 */ 262 static __inline __always_inline void 263 fe_1(fe *h) 264 { 265 memset(h, 0, sizeof(uint32_t) * 10); 266 h->v[0] = 1; 267 } 268 269 static void 270 fe_add_impl(uint32_t out[10], const uint32_t in1[10], const uint32_t in2[10]) 271 { 272 const uint32_t x20 = in1[9]; 273 const uint32_t x21 = in1[8]; 274 const uint32_t x19 = in1[7]; 275 const uint32_t x17 = in1[6]; 276 const uint32_t x15 = in1[5]; 277 const uint32_t x13 = in1[4]; 278 const uint32_t x11 = in1[3]; 279 const uint32_t x9 = in1[2]; 280 const uint32_t x7 = in1[1]; 281 const uint32_t x5 = in1[0]; 282 const uint32_t x38 = in2[9]; 283 const uint32_t x39 = in2[8]; 284 const uint32_t x37 = in2[7]; 285 const uint32_t x35 = in2[6]; 286 const uint32_t x33 = in2[5]; 287 const uint32_t x31 = in2[4]; 288 const uint32_t x29 = in2[3]; 289 const uint32_t x27 = in2[2]; 290 const uint32_t x25 = in2[1]; 291 const uint32_t x23 = in2[0]; 292 out[0] = (x5 + x23); 293 out[1] = (x7 + x25); 294 out[2] = (x9 + x27); 295 out[3] = (x11 + x29); 296 out[4] = (x13 + x31); 297 out[5] = (x15 + x33); 298 out[6] = (x17 + x35); 299 out[7] = (x19 + x37); 300 out[8] = (x21 + x39); 301 out[9] = (x20 + x38); 302 } 303 304 /* h = f + g 305 * Can overlap h with f or g. 306 */ 307 static __inline __always_inline void 308 fe_add(fe_loose *h, const fe *f, const fe *g) 309 { 310 fe_add_impl(h->v, f->v, g->v); 311 } 312 313 static void 314 fe_sub_impl(uint32_t out[10], const uint32_t in1[10], const uint32_t in2[10]) 315 { 316 const uint32_t x20 = in1[9]; 317 const uint32_t x21 = in1[8]; 318 const uint32_t x19 = in1[7]; 319 const uint32_t x17 = in1[6]; 320 const uint32_t x15 = in1[5]; 321 const uint32_t x13 = in1[4]; 322 const uint32_t x11 = in1[3]; 323 const uint32_t x9 = in1[2]; 324 const uint32_t x7 = in1[1]; 325 const uint32_t x5 = in1[0]; 326 const uint32_t x38 = in2[9]; 327 const uint32_t x39 = in2[8]; 328 const uint32_t x37 = in2[7]; 329 const uint32_t x35 = in2[6]; 330 const uint32_t x33 = in2[5]; 331 const uint32_t x31 = in2[4]; 332 const uint32_t x29 = in2[3]; 333 const uint32_t x27 = in2[2]; 334 const uint32_t x25 = in2[1]; 335 const uint32_t x23 = in2[0]; 336 out[0] = ((0x7ffffda + x5) - x23); 337 out[1] = ((0x3fffffe + x7) - x25); 338 out[2] = ((0x7fffffe + x9) - x27); 339 out[3] = ((0x3fffffe + x11) - x29); 340 out[4] = ((0x7fffffe + x13) - x31); 341 out[5] = ((0x3fffffe + x15) - x33); 342 out[6] = ((0x7fffffe + x17) - x35); 343 out[7] = ((0x3fffffe + x19) - x37); 344 out[8] = ((0x7fffffe + x21) - x39); 345 out[9] = ((0x3fffffe + x20) - x38); 346 } 347 348 /* h = f - g 349 * Can overlap h with f or g. 350 */ 351 static __inline __always_inline void 352 fe_sub(fe_loose *h, const fe *f, const fe *g) 353 { 354 fe_sub_impl(h->v, f->v, g->v); 355 } 356 357 static void 358 fe_mul_impl(uint32_t out[10], const uint32_t in1[10], const uint32_t in2[10]) 359 { 360 const uint32_t x20 = in1[9]; 361 const uint32_t x21 = in1[8]; 362 const uint32_t x19 = in1[7]; 363 const uint32_t x17 = in1[6]; 364 const uint32_t x15 = in1[5]; 365 const uint32_t x13 = in1[4]; 366 const uint32_t x11 = in1[3]; 367 const uint32_t x9 = in1[2]; 368 const uint32_t x7 = in1[1]; 369 const uint32_t x5 = in1[0]; 370 const uint32_t x38 = in2[9]; 371 const uint32_t x39 = in2[8]; 372 const uint32_t x37 = in2[7]; 373 const uint32_t x35 = in2[6]; 374 const uint32_t x33 = in2[5]; 375 const uint32_t x31 = in2[4]; 376 const uint32_t x29 = in2[3]; 377 const uint32_t x27 = in2[2]; 378 const uint32_t x25 = in2[1]; 379 const uint32_t x23 = in2[0]; 380 uint64_t x40 = ((uint64_t)x23 * x5); 381 uint64_t x41 = (((uint64_t)x23 * x7) + ((uint64_t)x25 * x5)); 382 uint64_t x42 = ((((uint64_t)(0x2 * x25) * x7) + ((uint64_t)x23 * x9)) + ((uint64_t)x27 * x5)); 383 uint64_t x43 = (((((uint64_t)x25 * x9) + ((uint64_t)x27 * x7)) + ((uint64_t)x23 * x11)) + ((uint64_t)x29 * x5)); 384 uint64_t x44 = (((((uint64_t)x27 * x9) + (0x2 * (((uint64_t)x25 * x11) + ((uint64_t)x29 * x7)))) + ((uint64_t)x23 * x13)) + ((uint64_t)x31 * x5)); 385 uint64_t x45 = (((((((uint64_t)x27 * x11) + ((uint64_t)x29 * x9)) + ((uint64_t)x25 * x13)) + ((uint64_t)x31 * x7)) + ((uint64_t)x23 * x15)) + ((uint64_t)x33 * x5)); 386 uint64_t x46 = (((((0x2 * ((((uint64_t)x29 * x11) + ((uint64_t)x25 * x15)) + ((uint64_t)x33 * x7))) + ((uint64_t)x27 * x13)) + ((uint64_t)x31 * x9)) + ((uint64_t)x23 * x17)) + ((uint64_t)x35 * x5)); 387 uint64_t x47 = (((((((((uint64_t)x29 * x13) + ((uint64_t)x31 * x11)) + ((uint64_t)x27 * x15)) + ((uint64_t)x33 * x9)) + ((uint64_t)x25 * x17)) + ((uint64_t)x35 * x7)) + ((uint64_t)x23 * x19)) + ((uint64_t)x37 * x5)); 388 uint64_t x48 = (((((((uint64_t)x31 * x13) + (0x2 * (((((uint64_t)x29 * x15) + ((uint64_t)x33 * x11)) + ((uint64_t)x25 * x19)) + ((uint64_t)x37 * x7)))) + ((uint64_t)x27 * x17)) + ((uint64_t)x35 * x9)) + ((uint64_t)x23 * x21)) + ((uint64_t)x39 * x5)); 389 uint64_t x49 = (((((((((((uint64_t)x31 * x15) + ((uint64_t)x33 * x13)) + ((uint64_t)x29 * x17)) + ((uint64_t)x35 * x11)) + ((uint64_t)x27 * x19)) + ((uint64_t)x37 * x9)) + ((uint64_t)x25 * x21)) + ((uint64_t)x39 * x7)) + ((uint64_t)x23 * x20)) + ((uint64_t)x38 * x5)); 390 uint64_t x50 = (((((0x2 * ((((((uint64_t)x33 * x15) + ((uint64_t)x29 * x19)) + ((uint64_t)x37 * x11)) + ((uint64_t)x25 * x20)) + ((uint64_t)x38 * x7))) + ((uint64_t)x31 * x17)) + ((uint64_t)x35 * x13)) + ((uint64_t)x27 * x21)) + ((uint64_t)x39 * x9)); 391 uint64_t x51 = (((((((((uint64_t)x33 * x17) + ((uint64_t)x35 * x15)) + ((uint64_t)x31 * x19)) + ((uint64_t)x37 * x13)) + ((uint64_t)x29 * x21)) + ((uint64_t)x39 * x11)) + ((uint64_t)x27 * x20)) + ((uint64_t)x38 * x9)); 392 uint64_t x52 = (((((uint64_t)x35 * x17) + (0x2 * (((((uint64_t)x33 * x19) + ((uint64_t)x37 * x15)) + ((uint64_t)x29 * x20)) + ((uint64_t)x38 * x11)))) + ((uint64_t)x31 * x21)) + ((uint64_t)x39 * x13)); 393 uint64_t x53 = (((((((uint64_t)x35 * x19) + ((uint64_t)x37 * x17)) + ((uint64_t)x33 * x21)) + ((uint64_t)x39 * x15)) + ((uint64_t)x31 * x20)) + ((uint64_t)x38 * x13)); 394 uint64_t x54 = (((0x2 * ((((uint64_t)x37 * x19) + ((uint64_t)x33 * x20)) + ((uint64_t)x38 * x15))) + ((uint64_t)x35 * x21)) + ((uint64_t)x39 * x17)); 395 uint64_t x55 = (((((uint64_t)x37 * x21) + ((uint64_t)x39 * x19)) + ((uint64_t)x35 * x20)) + ((uint64_t)x38 * x17)); 396 uint64_t x56 = (((uint64_t)x39 * x21) + (0x2 * (((uint64_t)x37 * x20) + ((uint64_t)x38 * x19)))); 397 uint64_t x57 = (((uint64_t)x39 * x20) + ((uint64_t)x38 * x21)); 398 uint64_t x58 = ((uint64_t)(0x2 * x38) * x20); 399 uint64_t x59 = (x48 + (x58 << 0x4)); 400 uint64_t x60 = (x59 + (x58 << 0x1)); 401 uint64_t x61 = (x60 + x58); 402 uint64_t x62 = (x47 + (x57 << 0x4)); 403 uint64_t x63 = (x62 + (x57 << 0x1)); 404 uint64_t x64 = (x63 + x57); 405 uint64_t x65 = (x46 + (x56 << 0x4)); 406 uint64_t x66 = (x65 + (x56 << 0x1)); 407 uint64_t x67 = (x66 + x56); 408 uint64_t x68 = (x45 + (x55 << 0x4)); 409 uint64_t x69 = (x68 + (x55 << 0x1)); 410 uint64_t x70 = (x69 + x55); 411 uint64_t x71 = (x44 + (x54 << 0x4)); 412 uint64_t x72 = (x71 + (x54 << 0x1)); 413 uint64_t x73 = (x72 + x54); 414 uint64_t x74 = (x43 + (x53 << 0x4)); 415 uint64_t x75 = (x74 + (x53 << 0x1)); 416 uint64_t x76 = (x75 + x53); 417 uint64_t x77 = (x42 + (x52 << 0x4)); 418 uint64_t x78 = (x77 + (x52 << 0x1)); 419 uint64_t x79 = (x78 + x52); 420 uint64_t x80 = (x41 + (x51 << 0x4)); 421 uint64_t x81 = (x80 + (x51 << 0x1)); 422 uint64_t x82 = (x81 + x51); 423 uint64_t x83 = (x40 + (x50 << 0x4)); 424 uint64_t x84 = (x83 + (x50 << 0x1)); 425 uint64_t x85 = (x84 + x50); 426 uint64_t x86 = (x85 >> 0x1a); 427 uint32_t x87 = ((uint32_t)x85 & 0x3ffffff); 428 uint64_t x88 = (x86 + x82); 429 uint64_t x89 = (x88 >> 0x19); 430 uint32_t x90 = ((uint32_t)x88 & 0x1ffffff); 431 uint64_t x91 = (x89 + x79); 432 uint64_t x92 = (x91 >> 0x1a); 433 uint32_t x93 = ((uint32_t)x91 & 0x3ffffff); 434 uint64_t x94 = (x92 + x76); 435 uint64_t x95 = (x94 >> 0x19); 436 uint32_t x96 = ((uint32_t)x94 & 0x1ffffff); 437 uint64_t x97 = (x95 + x73); 438 uint64_t x98 = (x97 >> 0x1a); 439 uint32_t x99 = ((uint32_t)x97 & 0x3ffffff); 440 uint64_t x100 = (x98 + x70); 441 uint64_t x101 = (x100 >> 0x19); 442 uint32_t x102 = ((uint32_t)x100 & 0x1ffffff); 443 uint64_t x103 = (x101 + x67); 444 uint64_t x104 = (x103 >> 0x1a); 445 uint32_t x105 = ((uint32_t)x103 & 0x3ffffff); 446 uint64_t x106 = (x104 + x64); 447 uint64_t x107 = (x106 >> 0x19); 448 uint32_t x108 = ((uint32_t)x106 & 0x1ffffff); 449 uint64_t x109 = (x107 + x61); 450 uint64_t x110 = (x109 >> 0x1a); 451 uint32_t x111 = ((uint32_t)x109 & 0x3ffffff); 452 uint64_t x112 = (x110 + x49); 453 uint64_t x113 = (x112 >> 0x19); 454 uint32_t x114 = ((uint32_t)x112 & 0x1ffffff); 455 uint64_t x115 = (x87 + (0x13 * x113)); 456 uint32_t x116 = (uint32_t) (x115 >> 0x1a); 457 uint32_t x117 = ((uint32_t)x115 & 0x3ffffff); 458 uint32_t x118 = (x116 + x90); 459 uint32_t x119 = (x118 >> 0x19); 460 uint32_t x120 = (x118 & 0x1ffffff); 461 out[0] = x117; 462 out[1] = x120; 463 out[2] = (x119 + x93); 464 out[3] = x96; 465 out[4] = x99; 466 out[5] = x102; 467 out[6] = x105; 468 out[7] = x108; 469 out[8] = x111; 470 out[9] = x114; 471 } 472 473 static __inline __always_inline void 474 fe_mul_ttt(fe *h, const fe *f, const fe *g) 475 { 476 fe_mul_impl(h->v, f->v, g->v); 477 } 478 479 static __inline __always_inline void 480 fe_mul_tlt(fe *h, const fe_loose *f, const fe *g) 481 { 482 fe_mul_impl(h->v, f->v, g->v); 483 } 484 485 static __inline __always_inline void 486 fe_mul_tll(fe *h, const fe_loose *f, const fe_loose *g) 487 { 488 fe_mul_impl(h->v, f->v, g->v); 489 } 490 491 static void 492 fe_sqr_impl(uint32_t out[10], const uint32_t in1[10]) 493 { 494 const uint32_t x17 = in1[9]; 495 const uint32_t x18 = in1[8]; 496 const uint32_t x16 = in1[7]; 497 const uint32_t x14 = in1[6]; 498 const uint32_t x12 = in1[5]; 499 const uint32_t x10 = in1[4]; 500 const uint32_t x8 = in1[3]; 501 const uint32_t x6 = in1[2]; 502 const uint32_t x4 = in1[1]; 503 const uint32_t x2 = in1[0]; 504 uint64_t x19 = ((uint64_t)x2 * x2); 505 uint64_t x20 = ((uint64_t)(0x2 * x2) * x4); 506 uint64_t x21 = (0x2 * (((uint64_t)x4 * x4) + ((uint64_t)x2 * x6))); 507 uint64_t x22 = (0x2 * (((uint64_t)x4 * x6) + ((uint64_t)x2 * x8))); 508 uint64_t x23 = ((((uint64_t)x6 * x6) + ((uint64_t)(0x4 * x4) * x8)) + ((uint64_t)(0x2 * x2) * x10)); 509 uint64_t x24 = (0x2 * ((((uint64_t)x6 * x8) + ((uint64_t)x4 * x10)) + ((uint64_t)x2 * x12))); 510 uint64_t x25 = (0x2 * (((((uint64_t)x8 * x8) + ((uint64_t)x6 * x10)) + ((uint64_t)x2 * x14)) + ((uint64_t)(0x2 * x4) * x12))); 511 uint64_t x26 = (0x2 * (((((uint64_t)x8 * x10) + ((uint64_t)x6 * x12)) + ((uint64_t)x4 * x14)) + ((uint64_t)x2 * x16))); 512 uint64_t x27 = (((uint64_t)x10 * x10) + (0x2 * ((((uint64_t)x6 * x14) + ((uint64_t)x2 * x18)) + (0x2 * (((uint64_t)x4 * x16) + ((uint64_t)x8 * x12)))))); 513 uint64_t x28 = (0x2 * ((((((uint64_t)x10 * x12) + ((uint64_t)x8 * x14)) + ((uint64_t)x6 * x16)) + ((uint64_t)x4 * x18)) + ((uint64_t)x2 * x17))); 514 uint64_t x29 = (0x2 * (((((uint64_t)x12 * x12) + ((uint64_t)x10 * x14)) + ((uint64_t)x6 * x18)) + (0x2 * (((uint64_t)x8 * x16) + ((uint64_t)x4 * x17))))); 515 uint64_t x30 = (0x2 * (((((uint64_t)x12 * x14) + ((uint64_t)x10 * x16)) + ((uint64_t)x8 * x18)) + ((uint64_t)x6 * x17))); 516 uint64_t x31 = (((uint64_t)x14 * x14) + (0x2 * (((uint64_t)x10 * x18) + (0x2 * (((uint64_t)x12 * x16) + ((uint64_t)x8 * x17)))))); 517 uint64_t x32 = (0x2 * ((((uint64_t)x14 * x16) + ((uint64_t)x12 * x18)) + ((uint64_t)x10 * x17))); 518 uint64_t x33 = (0x2 * ((((uint64_t)x16 * x16) + ((uint64_t)x14 * x18)) + ((uint64_t)(0x2 * x12) * x17))); 519 uint64_t x34 = (0x2 * (((uint64_t)x16 * x18) + ((uint64_t)x14 * x17))); 520 uint64_t x35 = (((uint64_t)x18 * x18) + ((uint64_t)(0x4 * x16) * x17)); 521 uint64_t x36 = ((uint64_t)(0x2 * x18) * x17); 522 uint64_t x37 = ((uint64_t)(0x2 * x17) * x17); 523 uint64_t x38 = (x27 + (x37 << 0x4)); 524 uint64_t x39 = (x38 + (x37 << 0x1)); 525 uint64_t x40 = (x39 + x37); 526 uint64_t x41 = (x26 + (x36 << 0x4)); 527 uint64_t x42 = (x41 + (x36 << 0x1)); 528 uint64_t x43 = (x42 + x36); 529 uint64_t x44 = (x25 + (x35 << 0x4)); 530 uint64_t x45 = (x44 + (x35 << 0x1)); 531 uint64_t x46 = (x45 + x35); 532 uint64_t x47 = (x24 + (x34 << 0x4)); 533 uint64_t x48 = (x47 + (x34 << 0x1)); 534 uint64_t x49 = (x48 + x34); 535 uint64_t x50 = (x23 + (x33 << 0x4)); 536 uint64_t x51 = (x50 + (x33 << 0x1)); 537 uint64_t x52 = (x51 + x33); 538 uint64_t x53 = (x22 + (x32 << 0x4)); 539 uint64_t x54 = (x53 + (x32 << 0x1)); 540 uint64_t x55 = (x54 + x32); 541 uint64_t x56 = (x21 + (x31 << 0x4)); 542 uint64_t x57 = (x56 + (x31 << 0x1)); 543 uint64_t x58 = (x57 + x31); 544 uint64_t x59 = (x20 + (x30 << 0x4)); 545 uint64_t x60 = (x59 + (x30 << 0x1)); 546 uint64_t x61 = (x60 + x30); 547 uint64_t x62 = (x19 + (x29 << 0x4)); 548 uint64_t x63 = (x62 + (x29 << 0x1)); 549 uint64_t x64 = (x63 + x29); 550 uint64_t x65 = (x64 >> 0x1a); 551 uint32_t x66 = ((uint32_t)x64 & 0x3ffffff); 552 uint64_t x67 = (x65 + x61); 553 uint64_t x68 = (x67 >> 0x19); 554 uint32_t x69 = ((uint32_t)x67 & 0x1ffffff); 555 uint64_t x70 = (x68 + x58); 556 uint64_t x71 = (x70 >> 0x1a); 557 uint32_t x72 = ((uint32_t)x70 & 0x3ffffff); 558 uint64_t x73 = (x71 + x55); 559 uint64_t x74 = (x73 >> 0x19); 560 uint32_t x75 = ((uint32_t)x73 & 0x1ffffff); 561 uint64_t x76 = (x74 + x52); 562 uint64_t x77 = (x76 >> 0x1a); 563 uint32_t x78 = ((uint32_t)x76 & 0x3ffffff); 564 uint64_t x79 = (x77 + x49); 565 uint64_t x80 = (x79 >> 0x19); 566 uint32_t x81 = ((uint32_t)x79 & 0x1ffffff); 567 uint64_t x82 = (x80 + x46); 568 uint64_t x83 = (x82 >> 0x1a); 569 uint32_t x84 = ((uint32_t)x82 & 0x3ffffff); 570 uint64_t x85 = (x83 + x43); 571 uint64_t x86 = (x85 >> 0x19); 572 uint32_t x87 = ((uint32_t)x85 & 0x1ffffff); 573 uint64_t x88 = (x86 + x40); 574 uint64_t x89 = (x88 >> 0x1a); 575 uint32_t x90 = ((uint32_t)x88 & 0x3ffffff); 576 uint64_t x91 = (x89 + x28); 577 uint64_t x92 = (x91 >> 0x19); 578 uint32_t x93 = ((uint32_t)x91 & 0x1ffffff); 579 uint64_t x94 = (x66 + (0x13 * x92)); 580 uint32_t x95 = (uint32_t) (x94 >> 0x1a); 581 uint32_t x96 = ((uint32_t)x94 & 0x3ffffff); 582 uint32_t x97 = (x95 + x69); 583 uint32_t x98 = (x97 >> 0x19); 584 uint32_t x99 = (x97 & 0x1ffffff); 585 out[0] = x96; 586 out[1] = x99; 587 out[2] = (x98 + x72); 588 out[3] = x75; 589 out[4] = x78; 590 out[5] = x81; 591 out[6] = x84; 592 out[7] = x87; 593 out[8] = x90; 594 out[9] = x93; 595 } 596 597 static __inline __always_inline void 598 fe_sq_tl(fe *h, const fe_loose *f) 599 { 600 fe_sqr_impl(h->v, f->v); 601 } 602 603 static __inline __always_inline void 604 fe_sq_tt(fe *h, const fe *f) 605 { 606 fe_sqr_impl(h->v, f->v); 607 } 608 609 static __inline __always_inline void 610 fe_loose_invert(fe *out, const fe_loose *z) 611 { 612 fe t0; 613 fe t1; 614 fe t2; 615 fe t3; 616 int i; 617 618 fe_sq_tl(&t0, z); 619 fe_sq_tt(&t1, &t0); 620 for (i = 1; i < 2; ++i) 621 fe_sq_tt(&t1, &t1); 622 fe_mul_tlt(&t1, z, &t1); 623 fe_mul_ttt(&t0, &t0, &t1); 624 fe_sq_tt(&t2, &t0); 625 fe_mul_ttt(&t1, &t1, &t2); 626 fe_sq_tt(&t2, &t1); 627 for (i = 1; i < 5; ++i) 628 fe_sq_tt(&t2, &t2); 629 fe_mul_ttt(&t1, &t2, &t1); 630 fe_sq_tt(&t2, &t1); 631 for (i = 1; i < 10; ++i) 632 fe_sq_tt(&t2, &t2); 633 fe_mul_ttt(&t2, &t2, &t1); 634 fe_sq_tt(&t3, &t2); 635 for (i = 1; i < 20; ++i) 636 fe_sq_tt(&t3, &t3); 637 fe_mul_ttt(&t2, &t3, &t2); 638 fe_sq_tt(&t2, &t2); 639 for (i = 1; i < 10; ++i) 640 fe_sq_tt(&t2, &t2); 641 fe_mul_ttt(&t1, &t2, &t1); 642 fe_sq_tt(&t2, &t1); 643 for (i = 1; i < 50; ++i) 644 fe_sq_tt(&t2, &t2); 645 fe_mul_ttt(&t2, &t2, &t1); 646 fe_sq_tt(&t3, &t2); 647 for (i = 1; i < 100; ++i) 648 fe_sq_tt(&t3, &t3); 649 fe_mul_ttt(&t2, &t3, &t2); 650 fe_sq_tt(&t2, &t2); 651 for (i = 1; i < 50; ++i) 652 fe_sq_tt(&t2, &t2); 653 fe_mul_ttt(&t1, &t2, &t1); 654 fe_sq_tt(&t1, &t1); 655 for (i = 1; i < 5; ++i) 656 fe_sq_tt(&t1, &t1); 657 fe_mul_ttt(out, &t1, &t0); 658 } 659 660 static __inline __always_inline void 661 fe_invert(fe *out, const fe *z) 662 { 663 fe_loose l; 664 fe_copy_lt(&l, z); 665 fe_loose_invert(out, &l); 666 } 667 668 /* Replace (f,g) with (g,f) if b == 1; 669 * replace (f,g) with (f,g) if b == 0. 670 * 671 * Preconditions: b in {0,1} 672 */ 673 static __inline __always_inline void 674 fe_cswap(fe *f, fe *g, unsigned int b) 675 { 676 unsigned i; 677 b = 0 - b; 678 for (i = 0; i < 10; i++) { 679 uint32_t x = f->v[i] ^ g->v[i]; 680 x &= b; 681 f->v[i] ^= x; 682 g->v[i] ^= x; 683 } 684 } 685 686 /* NOTE: based on fiat-crypto fe_mul, edited for in2=121666, 0, 0.*/ 687 static __inline __always_inline void 688 fe_mul_121666_impl(uint32_t out[10], const uint32_t in1[10]) 689 { 690 const uint32_t x20 = in1[9]; 691 const uint32_t x21 = in1[8]; 692 const uint32_t x19 = in1[7]; 693 const uint32_t x17 = in1[6]; 694 const uint32_t x15 = in1[5]; 695 const uint32_t x13 = in1[4]; 696 const uint32_t x11 = in1[3]; 697 const uint32_t x9 = in1[2]; 698 const uint32_t x7 = in1[1]; 699 const uint32_t x5 = in1[0]; 700 const uint32_t x38 = 0; 701 const uint32_t x39 = 0; 702 const uint32_t x37 = 0; 703 const uint32_t x35 = 0; 704 const uint32_t x33 = 0; 705 const uint32_t x31 = 0; 706 const uint32_t x29 = 0; 707 const uint32_t x27 = 0; 708 const uint32_t x25 = 0; 709 const uint32_t x23 = 121666; 710 uint64_t x40 = ((uint64_t)x23 * x5); 711 uint64_t x41 = (((uint64_t)x23 * x7) + ((uint64_t)x25 * x5)); 712 uint64_t x42 = ((((uint64_t)(0x2 * x25) * x7) + ((uint64_t)x23 * x9)) + ((uint64_t)x27 * x5)); 713 uint64_t x43 = (((((uint64_t)x25 * x9) + ((uint64_t)x27 * x7)) + ((uint64_t)x23 * x11)) + ((uint64_t)x29 * x5)); 714 uint64_t x44 = (((((uint64_t)x27 * x9) + (0x2 * (((uint64_t)x25 * x11) + ((uint64_t)x29 * x7)))) + ((uint64_t)x23 * x13)) + ((uint64_t)x31 * x5)); 715 uint64_t x45 = (((((((uint64_t)x27 * x11) + ((uint64_t)x29 * x9)) + ((uint64_t)x25 * x13)) + ((uint64_t)x31 * x7)) + ((uint64_t)x23 * x15)) + ((uint64_t)x33 * x5)); 716 uint64_t x46 = (((((0x2 * ((((uint64_t)x29 * x11) + ((uint64_t)x25 * x15)) + ((uint64_t)x33 * x7))) + ((uint64_t)x27 * x13)) + ((uint64_t)x31 * x9)) + ((uint64_t)x23 * x17)) + ((uint64_t)x35 * x5)); 717 uint64_t x47 = (((((((((uint64_t)x29 * x13) + ((uint64_t)x31 * x11)) + ((uint64_t)x27 * x15)) + ((uint64_t)x33 * x9)) + ((uint64_t)x25 * x17)) + ((uint64_t)x35 * x7)) + ((uint64_t)x23 * x19)) + ((uint64_t)x37 * x5)); 718 uint64_t x48 = (((((((uint64_t)x31 * x13) + (0x2 * (((((uint64_t)x29 * x15) + ((uint64_t)x33 * x11)) + ((uint64_t)x25 * x19)) + ((uint64_t)x37 * x7)))) + ((uint64_t)x27 * x17)) + ((uint64_t)x35 * x9)) + ((uint64_t)x23 * x21)) + ((uint64_t)x39 * x5)); 719 uint64_t x49 = (((((((((((uint64_t)x31 * x15) + ((uint64_t)x33 * x13)) + ((uint64_t)x29 * x17)) + ((uint64_t)x35 * x11)) + ((uint64_t)x27 * x19)) + ((uint64_t)x37 * x9)) + ((uint64_t)x25 * x21)) + ((uint64_t)x39 * x7)) + ((uint64_t)x23 * x20)) + ((uint64_t)x38 * x5)); 720 uint64_t x50 = (((((0x2 * ((((((uint64_t)x33 * x15) + ((uint64_t)x29 * x19)) + ((uint64_t)x37 * x11)) + ((uint64_t)x25 * x20)) + ((uint64_t)x38 * x7))) + ((uint64_t)x31 * x17)) + ((uint64_t)x35 * x13)) + ((uint64_t)x27 * x21)) + ((uint64_t)x39 * x9)); 721 uint64_t x51 = (((((((((uint64_t)x33 * x17) + ((uint64_t)x35 * x15)) + ((uint64_t)x31 * x19)) + ((uint64_t)x37 * x13)) + ((uint64_t)x29 * x21)) + ((uint64_t)x39 * x11)) + ((uint64_t)x27 * x20)) + ((uint64_t)x38 * x9)); 722 uint64_t x52 = (((((uint64_t)x35 * x17) + (0x2 * (((((uint64_t)x33 * x19) + ((uint64_t)x37 * x15)) + ((uint64_t)x29 * x20)) + ((uint64_t)x38 * x11)))) + ((uint64_t)x31 * x21)) + ((uint64_t)x39 * x13)); 723 uint64_t x53 = (((((((uint64_t)x35 * x19) + ((uint64_t)x37 * x17)) + ((uint64_t)x33 * x21)) + ((uint64_t)x39 * x15)) + ((uint64_t)x31 * x20)) + ((uint64_t)x38 * x13)); 724 uint64_t x54 = (((0x2 * ((((uint64_t)x37 * x19) + ((uint64_t)x33 * x20)) + ((uint64_t)x38 * x15))) + ((uint64_t)x35 * x21)) + ((uint64_t)x39 * x17)); 725 uint64_t x55 = (((((uint64_t)x37 * x21) + ((uint64_t)x39 * x19)) + ((uint64_t)x35 * x20)) + ((uint64_t)x38 * x17)); 726 uint64_t x56 = (((uint64_t)x39 * x21) + (0x2 * (((uint64_t)x37 * x20) + ((uint64_t)x38 * x19)))); 727 uint64_t x57 = (((uint64_t)x39 * x20) + ((uint64_t)x38 * x21)); 728 uint64_t x58 = ((uint64_t)(0x2 * x38) * x20); 729 uint64_t x59 = (x48 + (x58 << 0x4)); 730 uint64_t x60 = (x59 + (x58 << 0x1)); 731 uint64_t x61 = (x60 + x58); 732 uint64_t x62 = (x47 + (x57 << 0x4)); 733 uint64_t x63 = (x62 + (x57 << 0x1)); 734 uint64_t x64 = (x63 + x57); 735 uint64_t x65 = (x46 + (x56 << 0x4)); 736 uint64_t x66 = (x65 + (x56 << 0x1)); 737 uint64_t x67 = (x66 + x56); 738 uint64_t x68 = (x45 + (x55 << 0x4)); 739 uint64_t x69 = (x68 + (x55 << 0x1)); 740 uint64_t x70 = (x69 + x55); 741 uint64_t x71 = (x44 + (x54 << 0x4)); 742 uint64_t x72 = (x71 + (x54 << 0x1)); 743 uint64_t x73 = (x72 + x54); 744 uint64_t x74 = (x43 + (x53 << 0x4)); 745 uint64_t x75 = (x74 + (x53 << 0x1)); 746 uint64_t x76 = (x75 + x53); 747 uint64_t x77 = (x42 + (x52 << 0x4)); 748 uint64_t x78 = (x77 + (x52 << 0x1)); 749 uint64_t x79 = (x78 + x52); 750 uint64_t x80 = (x41 + (x51 << 0x4)); 751 uint64_t x81 = (x80 + (x51 << 0x1)); 752 uint64_t x82 = (x81 + x51); 753 uint64_t x83 = (x40 + (x50 << 0x4)); 754 uint64_t x84 = (x83 + (x50 << 0x1)); 755 uint64_t x85 = (x84 + x50); 756 uint64_t x86 = (x85 >> 0x1a); 757 uint32_t x87 = ((uint32_t)x85 & 0x3ffffff); 758 uint64_t x88 = (x86 + x82); 759 uint64_t x89 = (x88 >> 0x19); 760 uint32_t x90 = ((uint32_t)x88 & 0x1ffffff); 761 uint64_t x91 = (x89 + x79); 762 uint64_t x92 = (x91 >> 0x1a); 763 uint32_t x93 = ((uint32_t)x91 & 0x3ffffff); 764 uint64_t x94 = (x92 + x76); 765 uint64_t x95 = (x94 >> 0x19); 766 uint32_t x96 = ((uint32_t)x94 & 0x1ffffff); 767 uint64_t x97 = (x95 + x73); 768 uint64_t x98 = (x97 >> 0x1a); 769 uint32_t x99 = ((uint32_t)x97 & 0x3ffffff); 770 uint64_t x100 = (x98 + x70); 771 uint64_t x101 = (x100 >> 0x19); 772 uint32_t x102 = ((uint32_t)x100 & 0x1ffffff); 773 uint64_t x103 = (x101 + x67); 774 uint64_t x104 = (x103 >> 0x1a); 775 uint32_t x105 = ((uint32_t)x103 & 0x3ffffff); 776 uint64_t x106 = (x104 + x64); 777 uint64_t x107 = (x106 >> 0x19); 778 uint32_t x108 = ((uint32_t)x106 & 0x1ffffff); 779 uint64_t x109 = (x107 + x61); 780 uint64_t x110 = (x109 >> 0x1a); 781 uint32_t x111 = ((uint32_t)x109 & 0x3ffffff); 782 uint64_t x112 = (x110 + x49); 783 uint64_t x113 = (x112 >> 0x19); 784 uint32_t x114 = ((uint32_t)x112 & 0x1ffffff); 785 uint64_t x115 = (x87 + (0x13 * x113)); 786 uint32_t x116 = (uint32_t) (x115 >> 0x1a); 787 uint32_t x117 = ((uint32_t)x115 & 0x3ffffff); 788 uint32_t x118 = (x116 + x90); 789 uint32_t x119 = (x118 >> 0x19); 790 uint32_t x120 = (x118 & 0x1ffffff); 791 out[0] = x117; 792 out[1] = x120; 793 out[2] = (x119 + x93); 794 out[3] = x96; 795 out[4] = x99; 796 out[5] = x102; 797 out[6] = x105; 798 out[7] = x108; 799 out[8] = x111; 800 out[9] = x114; 801 } 802 803 static __inline __always_inline void 804 fe_mul121666(fe *h, const fe_loose *f) 805 { 806 fe_mul_121666_impl(h->v, f->v); 807 } 808 809 int 810 curve25519(uint8_t out[CURVE25519_KEY_SIZE], 811 const uint8_t scalar[CURVE25519_KEY_SIZE], 812 const uint8_t point[CURVE25519_KEY_SIZE]) 813 { 814 fe x1, x2, z2, x3, z3; 815 fe_loose x2l, z2l, x3l; 816 unsigned swap = 0; 817 int pos; 818 uint8_t e[32]; 819 820 memcpy(e, scalar, 32); 821 curve25519_clamp_secret(e); 822 823 /* The following implementation was transcribed to Coq and proven to 824 * correspond to unary scalar multiplication in affine coordinates given 825 * that x1 != 0 is the x coordinate of some point on the curve. It was 826 * also checked in Coq that doing a ladderstep with x1 = x3 = 0 gives 827 * z2' = z3' = 0, and z2 = z3 = 0 gives z2' = z3' = 0. The statement was 828 * quantified over the underlying field, so it applies to Curve25519 829 * itself and the quadratic twist of Curve25519. It was not proven in 830 * Coq that prime-field arithmetic correctly simulates extension-field 831 * arithmetic on prime-field values. The decoding of the byte array 832 * representation of e was not considered. 833 * 834 * Specification of Montgomery curves in affine coordinates: 835 * <https://github.com/mit-plv/fiat-crypto/blob/2456d821825521f7e03e65882cc3521795b0320f/src/Spec/MontgomeryCurve.v#L27> 836 * 837 * Proof that these form a group that is isomorphic to a Weierstrass 838 * curve: 839 * <https://github.com/mit-plv/fiat-crypto/blob/2456d821825521f7e03e65882cc3521795b0320f/src/Curves/Montgomery/AffineProofs.v#L35> 840 * 841 * Coq transcription and correctness proof of the loop 842 * (where scalarbits=255): 843 * <https://github.com/mit-plv/fiat-crypto/blob/2456d821825521f7e03e65882cc3521795b0320f/src/Curves/Montgomery/XZ.v#L118> 844 * <https://github.com/mit-plv/fiat-crypto/blob/2456d821825521f7e03e65882cc3521795b0320f/src/Curves/Montgomery/XZProofs.v#L278> 845 * preconditions: 0 <= e < 2^255 (not necessarily e < order), 846 * fe_invert(0) = 0 847 */ 848 fe_frombytes(&x1, point); 849 fe_1(&x2); 850 fe_0(&z2); 851 fe_copy(&x3, &x1); 852 fe_1(&z3); 853 854 for (pos = 254; pos >= 0; --pos) { 855 fe tmp0, tmp1; 856 fe_loose tmp0l, tmp1l; 857 /* loop invariant as of right before the test, for the case 858 * where x1 != 0: 859 * pos >= -1; if z2 = 0 then x2 is nonzero; if z3 = 0 then x3 860 * is nonzero 861 * let r := e >> (pos+1) in the following equalities of 862 * projective points: 863 * to_xz (r*P) === if swap then (x3, z3) else (x2, z2) 864 * to_xz ((r+1)*P) === if swap then (x2, z2) else (x3, z3) 865 * x1 is the nonzero x coordinate of the nonzero 866 * point (r*P-(r+1)*P) 867 */ 868 unsigned b = 1 & (e[pos / 8] >> (pos & 7)); 869 swap ^= b; 870 fe_cswap(&x2, &x3, swap); 871 fe_cswap(&z2, &z3, swap); 872 swap = b; 873 /* Coq transcription of ladderstep formula (called from 874 * transcribed loop): 875 * <https://github.com/mit-plv/fiat-crypto/blob/2456d821825521f7e03e65882cc3521795b0320f/src/Curves/Montgomery/XZ.v#L89> 876 * <https://github.com/mit-plv/fiat-crypto/blob/2456d821825521f7e03e65882cc3521795b0320f/src/Curves/Montgomery/XZProofs.v#L131> 877 * x1 != 0 <https://github.com/mit-plv/fiat-crypto/blob/2456d821825521f7e03e65882cc3521795b0320f/src/Curves/Montgomery/XZProofs.v#L217> 878 * x1 = 0 <https://github.com/mit-plv/fiat-crypto/blob/2456d821825521f7e03e65882cc3521795b0320f/src/Curves/Montgomery/XZProofs.v#L147> 879 */ 880 fe_sub(&tmp0l, &x3, &z3); 881 fe_sub(&tmp1l, &x2, &z2); 882 fe_add(&x2l, &x2, &z2); 883 fe_add(&z2l, &x3, &z3); 884 fe_mul_tll(&z3, &tmp0l, &x2l); 885 fe_mul_tll(&z2, &z2l, &tmp1l); 886 fe_sq_tl(&tmp0, &tmp1l); 887 fe_sq_tl(&tmp1, &x2l); 888 fe_add(&x3l, &z3, &z2); 889 fe_sub(&z2l, &z3, &z2); 890 fe_mul_ttt(&x2, &tmp1, &tmp0); 891 fe_sub(&tmp1l, &tmp1, &tmp0); 892 fe_sq_tl(&z2, &z2l); 893 fe_mul121666(&z3, &tmp1l); 894 fe_sq_tl(&x3, &x3l); 895 fe_add(&tmp0l, &tmp0, &z3); 896 fe_mul_ttt(&z3, &x1, &z2); 897 fe_mul_tll(&z2, &tmp1l, &tmp0l); 898 } 899 /* here pos=-1, so r=e, so to_xz (e*P) === if swap then (x3, z3) 900 * else (x2, z2) 901 */ 902 fe_cswap(&x2, &x3, swap); 903 fe_cswap(&z2, &z3, swap); 904 905 fe_invert(&z2, &z2); 906 fe_mul_ttt(&x2, &x2, &z2); 907 fe_tobytes(out, &x2); 908 909 explicit_bzero(&x1, sizeof(x1)); 910 explicit_bzero(&x2, sizeof(x2)); 911 explicit_bzero(&z2, sizeof(z2)); 912 explicit_bzero(&x3, sizeof(x3)); 913 explicit_bzero(&z3, sizeof(z3)); 914 explicit_bzero(&x2l, sizeof(x2l)); 915 explicit_bzero(&z2l, sizeof(z2l)); 916 explicit_bzero(&x3l, sizeof(x3l)); 917 explicit_bzero(&e, sizeof(e)); 918 return timingsafe_bcmp(out, null_point, CURVE25519_KEY_SIZE); 919 } 920