1 #include <string.h> 2 3 #include "private/common.h" 4 #include "utils.h" 5 6 /* 7 h = 0 8 */ 9 10 static inline void 11 fe25519_0(fe25519 h) 12 { 13 memset(&h[0], 0, 5 * sizeof h[0]); 14 } 15 16 /* 17 h = 1 18 */ 19 20 static inline void 21 fe25519_1(fe25519 h) 22 { 23 h[0] = 1; 24 memset(&h[1], 0, 4 * sizeof h[0]); 25 } 26 27 /* 28 h = f + g 29 Can overlap h with f or g. 30 */ 31 32 static inline void 33 fe25519_add(fe25519 h, const fe25519 f, const fe25519 g) 34 { 35 uint64_t h0 = f[0] + g[0]; 36 uint64_t h1 = f[1] + g[1]; 37 uint64_t h2 = f[2] + g[2]; 38 uint64_t h3 = f[3] + g[3]; 39 uint64_t h4 = f[4] + g[4]; 40 41 h[0] = h0; 42 h[1] = h1; 43 h[2] = h2; 44 h[3] = h3; 45 h[4] = h4; 46 } 47 48 /* 49 h = f - g 50 */ 51 52 static void 53 fe25519_sub(fe25519 h, const fe25519 f, const fe25519 g) 54 { 55 const uint64_t mask = 0x7ffffffffffffULL; 56 uint64_t h0, h1, h2, h3, h4; 57 58 h0 = g[0]; 59 h1 = g[1]; 60 h2 = g[2]; 61 h3 = g[3]; 62 h4 = g[4]; 63 64 h1 += h0 >> 51; 65 h0 &= mask; 66 h2 += h1 >> 51; 67 h1 &= mask; 68 h3 += h2 >> 51; 69 h2 &= mask; 70 h4 += h3 >> 51; 71 h3 &= mask; 72 h0 += 19ULL * (h4 >> 51); 73 h4 &= mask; 74 75 h0 = (f[0] + 0xfffffffffffdaULL) - h0; 76 h1 = (f[1] + 0xffffffffffffeULL) - h1; 77 h2 = (f[2] + 0xffffffffffffeULL) - h2; 78 h3 = (f[3] + 0xffffffffffffeULL) - h3; 79 h4 = (f[4] + 0xffffffffffffeULL) - h4; 80 81 h[0] = h0; 82 h[1] = h1; 83 h[2] = h2; 84 h[3] = h3; 85 h[4] = h4; 86 } 87 88 /* 89 h = -f 90 */ 91 92 static inline void 93 fe25519_neg(fe25519 h, const fe25519 f) 94 { 95 fe25519 zero; 96 97 fe25519_0(zero); 98 fe25519_sub(h, zero, f); 99 } 100 101 /* 102 Replace (f,g) with (g,g) if b == 1; 103 replace (f,g) with (f,g) if b == 0. 104 * 105 Preconditions: b in {0,1}. 106 */ 107 108 static void 109 fe25519_cmov(fe25519 f, const fe25519 g, unsigned int b) 110 { 111 const uint64_t mask = (uint64_t) (-(int64_t) b); 112 113 uint64_t f0 = f[0]; 114 uint64_t f1 = f[1]; 115 uint64_t f2 = f[2]; 116 uint64_t f3 = f[3]; 117 uint64_t f4 = f[4]; 118 119 uint64_t x0 = f0 ^ g[0]; 120 uint64_t x1 = f1 ^ g[1]; 121 uint64_t x2 = f2 ^ g[2]; 122 uint64_t x3 = f3 ^ g[3]; 123 uint64_t x4 = f4 ^ g[4]; 124 125 x0 &= mask; 126 x1 &= mask; 127 x2 &= mask; 128 x3 &= mask; 129 x4 &= mask; 130 131 f[0] = f0 ^ x0; 132 f[1] = f1 ^ x1; 133 f[2] = f2 ^ x2; 134 f[3] = f3 ^ x3; 135 f[4] = f4 ^ x4; 136 } 137 138 /* 139 Replace (f,g) with (g,f) if b == 1; 140 replace (f,g) with (f,g) if b == 0. 141 142 Preconditions: b in {0,1}. 143 */ 144 145 static void 146 fe25519_cswap(fe25519 f, fe25519 g, unsigned int b) 147 { 148 const uint64_t mask = (uint64_t) (-(int64_t) b); 149 150 uint64_t f0 = f[0]; 151 uint64_t f1 = f[1]; 152 uint64_t f2 = f[2]; 153 uint64_t f3 = f[3]; 154 uint64_t f4 = f[4]; 155 156 uint64_t g0 = g[0]; 157 uint64_t g1 = g[1]; 158 uint64_t g2 = g[2]; 159 uint64_t g3 = g[3]; 160 uint64_t g4 = g[4]; 161 162 uint64_t x0 = f0 ^ g0; 163 uint64_t x1 = f1 ^ g1; 164 uint64_t x2 = f2 ^ g2; 165 uint64_t x3 = f3 ^ g3; 166 uint64_t x4 = f4 ^ g4; 167 168 x0 &= mask; 169 x1 &= mask; 170 x2 &= mask; 171 x3 &= mask; 172 x4 &= mask; 173 174 f[0] = f0 ^ x0; 175 f[1] = f1 ^ x1; 176 f[2] = f2 ^ x2; 177 f[3] = f3 ^ x3; 178 f[4] = f4 ^ x4; 179 180 g[0] = g0 ^ x0; 181 g[1] = g1 ^ x1; 182 g[2] = g2 ^ x2; 183 g[3] = g3 ^ x3; 184 g[4] = g4 ^ x4; 185 } 186 187 /* 188 h = f 189 */ 190 191 static inline void 192 fe25519_copy(fe25519 h, const fe25519 f) 193 { 194 uint64_t f0 = f[0]; 195 uint64_t f1 = f[1]; 196 uint64_t f2 = f[2]; 197 uint64_t f3 = f[3]; 198 uint64_t f4 = f[4]; 199 200 h[0] = f0; 201 h[1] = f1; 202 h[2] = f2; 203 h[3] = f3; 204 h[4] = f4; 205 } 206 207 /* 208 return 1 if f is in {1,3,5,...,q-2} 209 return 0 if f is in {0,2,4,...,q-1} 210 */ 211 212 static inline int 213 fe25519_isnegative(const fe25519 f) 214 { 215 unsigned char s[32]; 216 217 fe25519_tobytes(s, f); 218 219 return s[0] & 1; 220 } 221 222 /* 223 return 1 if f == 0 224 return 0 if f != 0 225 */ 226 227 static inline int 228 fe25519_iszero(const fe25519 f) 229 { 230 unsigned char s[32]; 231 232 fe25519_tobytes(s, f); 233 234 return sodium_is_zero(s, 32); 235 } 236 237 /* 238 h = f * g 239 Can overlap h with f or g. 240 */ 241 242 static void 243 fe25519_mul(fe25519 h, const fe25519 f, const fe25519 g) 244 { 245 const uint64_t mask = 0x7ffffffffffffULL; 246 uint128_t r0, r1, r2, r3, r4, carry; 247 uint64_t f0, f1, f2, f3, f4; 248 uint64_t f1_19, f2_19, f3_19, f4_19; 249 uint64_t g0, g1, g2, g3, g4; 250 uint64_t r00, r01, r02, r03, r04; 251 252 f0 = f[0]; 253 f1 = f[1]; 254 f2 = f[2]; 255 f3 = f[3]; 256 f4 = f[4]; 257 258 g0 = g[0]; 259 g1 = g[1]; 260 g2 = g[2]; 261 g3 = g[3]; 262 g4 = g[4]; 263 264 f1_19 = 19ULL * f1; 265 f2_19 = 19ULL * f2; 266 f3_19 = 19ULL * f3; 267 f4_19 = 19ULL * f4; 268 269 r0 = ((uint128_t) f0 ) * ((uint128_t) g0); 270 r0 += ((uint128_t) f1_19) * ((uint128_t) g4); 271 r0 += ((uint128_t) f2_19) * ((uint128_t) g3); 272 r0 += ((uint128_t) f3_19) * ((uint128_t) g2); 273 r0 += ((uint128_t) f4_19) * ((uint128_t) g1); 274 275 r1 = ((uint128_t) f0 ) * ((uint128_t) g1); 276 r1 += ((uint128_t) f1 ) * ((uint128_t) g0); 277 r1 += ((uint128_t) f2_19) * ((uint128_t) g4); 278 r1 += ((uint128_t) f3_19) * ((uint128_t) g3); 279 r1 += ((uint128_t) f4_19) * ((uint128_t) g2); 280 281 r2 = ((uint128_t) f0 ) * ((uint128_t) g2); 282 r2 += ((uint128_t) f1 ) * ((uint128_t) g1); 283 r2 += ((uint128_t) f2 ) * ((uint128_t) g0); 284 r2 += ((uint128_t) f3_19) * ((uint128_t) g4); 285 r2 += ((uint128_t) f4_19) * ((uint128_t) g3); 286 287 r3 = ((uint128_t) f0 ) * ((uint128_t) g3); 288 r3 += ((uint128_t) f1 ) * ((uint128_t) g2); 289 r3 += ((uint128_t) f2 ) * ((uint128_t) g1); 290 r3 += ((uint128_t) f3 ) * ((uint128_t) g0); 291 r3 += ((uint128_t) f4_19) * ((uint128_t) g4); 292 293 r4 = ((uint128_t) f0 ) * ((uint128_t) g4); 294 r4 += ((uint128_t) f1 ) * ((uint128_t) g3); 295 r4 += ((uint128_t) f2 ) * ((uint128_t) g2); 296 r4 += ((uint128_t) f3 ) * ((uint128_t) g1); 297 r4 += ((uint128_t) f4 ) * ((uint128_t) g0); 298 299 r00 = ((uint64_t) r0) & mask; 300 carry = r0 >> 51; 301 r1 += carry; 302 r01 = ((uint64_t) r1) & mask; 303 carry = r1 >> 51; 304 r2 += carry; 305 r02 = ((uint64_t) r2) & mask; 306 carry = r2 >> 51; 307 r3 += carry; 308 r03 = ((uint64_t) r3) & mask; 309 carry = r3 >> 51; 310 r4 += carry; 311 r04 = ((uint64_t) r4) & mask; 312 carry = r4 >> 51; 313 r00 += 19ULL * (uint64_t) carry; 314 carry = r00 >> 51; 315 r00 &= mask; 316 r01 += (uint64_t) carry; 317 carry = r01 >> 51; 318 r01 &= mask; 319 r02 += (uint64_t) carry; 320 321 h[0] = r00; 322 h[1] = r01; 323 h[2] = r02; 324 h[3] = r03; 325 h[4] = r04; 326 } 327 328 /* 329 h = f * f 330 Can overlap h with f. 331 */ 332 333 static void 334 fe25519_sq(fe25519 h, const fe25519 f) 335 { 336 const uint64_t mask = 0x7ffffffffffffULL; 337 uint128_t r0, r1, r2, r3, r4, carry; 338 uint64_t f0, f1, f2, f3, f4; 339 uint64_t f0_2, f1_2, f1_38, f2_38, f3_38, f3_19, f4_19; 340 uint64_t r00, r01, r02, r03, r04; 341 342 f0 = f[0]; 343 f1 = f[1]; 344 f2 = f[2]; 345 f3 = f[3]; 346 f4 = f[4]; 347 348 f0_2 = f0 << 1; 349 f1_2 = f1 << 1; 350 351 f1_38 = 38ULL * f1; 352 f2_38 = 38ULL * f2; 353 f3_38 = 38ULL * f3; 354 355 f3_19 = 19ULL * f3; 356 f4_19 = 19ULL * f4; 357 358 r0 = ((uint128_t) f0 ) * ((uint128_t) f0); 359 r0 += ((uint128_t) f1_38) * ((uint128_t) f4); 360 r0 += ((uint128_t) f2_38) * ((uint128_t) f3); 361 362 r1 = ((uint128_t) f0_2 ) * ((uint128_t) f1); 363 r1 += ((uint128_t) f2_38) * ((uint128_t) f4); 364 r1 += ((uint128_t) f3_19) * ((uint128_t) f3); 365 366 r2 = ((uint128_t) f0_2 ) * ((uint128_t) f2); 367 r2 += ((uint128_t) f1 ) * ((uint128_t) f1); 368 r2 += ((uint128_t) f3_38) * ((uint128_t) f4); 369 370 r3 = ((uint128_t) f0_2 ) * ((uint128_t) f3); 371 r3 += ((uint128_t) f1_2 ) * ((uint128_t) f2); 372 r3 += ((uint128_t) f4_19) * ((uint128_t) f4); 373 374 r4 = ((uint128_t) f0_2 ) * ((uint128_t) f4); 375 r4 += ((uint128_t) f1_2 ) * ((uint128_t) f3); 376 r4 += ((uint128_t) f2 ) * ((uint128_t) f2); 377 378 r00 = ((uint64_t) r0) & mask; 379 carry = r0 >> 51; 380 r1 += carry; 381 r01 = ((uint64_t) r1) & mask; 382 carry = r1 >> 51; 383 r2 += carry; 384 r02 = ((uint64_t) r2) & mask; 385 carry = r2 >> 51; 386 r3 += carry; 387 r03 = ((uint64_t) r3) & mask; 388 carry = r3 >> 51; 389 r4 += carry; 390 r04 = ((uint64_t) r4) & mask; 391 carry = r4 >> 51; 392 r00 += 19ULL * (uint64_t) carry; 393 carry = r00 >> 51; 394 r00 &= mask; 395 r01 += (uint64_t) carry; 396 carry = r01 >> 51; 397 r01 &= mask; 398 r02 += (uint64_t) carry; 399 400 h[0] = r00; 401 h[1] = r01; 402 h[2] = r02; 403 h[3] = r03; 404 h[4] = r04; 405 } 406 407 /* 408 h = 2 * f * f 409 Can overlap h with f. 410 */ 411 412 static void 413 fe25519_sq2(fe25519 h, const fe25519 f) 414 { 415 const uint64_t mask = 0x7ffffffffffffULL; 416 uint128_t r0, r1, r2, r3, r4, carry; 417 uint64_t f0, f1, f2, f3, f4; 418 uint64_t f0_2, f1_2, f1_38, f2_38, f3_38, f3_19, f4_19; 419 uint64_t r00, r01, r02, r03, r04; 420 421 f0 = f[0]; 422 f1 = f[1]; 423 f2 = f[2]; 424 f3 = f[3]; 425 f4 = f[4]; 426 427 f0_2 = f0 << 1; 428 f1_2 = f1 << 1; 429 430 f1_38 = 38ULL * f1; 431 f2_38 = 38ULL * f2; 432 f3_38 = 38ULL * f3; 433 434 f3_19 = 19ULL * f3; 435 f4_19 = 19ULL * f4; 436 437 r0 = ((uint128_t) f0 ) * ((uint128_t) f0); 438 r0 += ((uint128_t) f1_38) * ((uint128_t) f4); 439 r0 += ((uint128_t) f2_38) * ((uint128_t) f3); 440 441 r1 = ((uint128_t) f0_2 ) * ((uint128_t) f1); 442 r1 += ((uint128_t) f2_38) * ((uint128_t) f4); 443 r1 += ((uint128_t) f3_19) * ((uint128_t) f3); 444 445 r2 = ((uint128_t) f0_2 ) * ((uint128_t) f2); 446 r2 += ((uint128_t) f1 ) * ((uint128_t) f1); 447 r2 += ((uint128_t) f3_38) * ((uint128_t) f4); 448 449 r3 = ((uint128_t) f0_2 ) * ((uint128_t) f3); 450 r3 += ((uint128_t) f1_2 ) * ((uint128_t) f2); 451 r3 += ((uint128_t) f4_19) * ((uint128_t) f4); 452 453 r4 = ((uint128_t) f0_2 ) * ((uint128_t) f4); 454 r4 += ((uint128_t) f1_2 ) * ((uint128_t) f3); 455 r4 += ((uint128_t) f2 ) * ((uint128_t) f2); 456 457 r0 <<= 1; 458 r1 <<= 1; 459 r2 <<= 1; 460 r3 <<= 1; 461 r4 <<= 1; 462 463 r00 = ((uint64_t) r0) & mask; 464 carry = r0 >> 51; 465 r1 += carry; 466 r01 = ((uint64_t) r1) & mask; 467 carry = r1 >> 51; 468 r2 += carry; 469 r02 = ((uint64_t) r2) & mask; 470 carry = r2 >> 51; 471 r3 += carry; 472 r03 = ((uint64_t) r3) & mask; 473 carry = r3 >> 51; 474 r4 += carry; 475 r04 = ((uint64_t) r4) & mask; 476 carry = r4 >> 51; 477 r00 += 19ULL * (uint64_t) carry; 478 carry = r00 >> 51; 479 r00 &= mask; 480 r01 += (uint64_t) carry; 481 carry = r01 >> 51; 482 r01 &= mask; 483 r02 += (uint64_t) carry; 484 485 h[0] = r00; 486 h[1] = r01; 487 h[2] = r02; 488 h[3] = r03; 489 h[4] = r04; 490 } 491 492 static void 493 fe25519_scalar_product(fe25519 h, const fe25519 f, uint32_t n) 494 { 495 const uint64_t mask = 0x7ffffffffffffULL; 496 uint128_t a; 497 uint128_t sn = (uint128_t) n; 498 uint64_t h0, h1, h2, h3, h4; 499 500 a = f[0] * sn; 501 h0 = ((uint64_t) a) & mask; 502 a = f[1] * sn + ((uint64_t) (a >> 51)); 503 h1 = ((uint64_t) a) & mask; 504 a = f[2] * sn + ((uint64_t) (a >> 51)); 505 h2 = ((uint64_t) a) & mask; 506 a = f[3] * sn + ((uint64_t) (a >> 51)); 507 h3 = ((uint64_t) a) & mask; 508 a = f[4] * sn + ((uint64_t) (a >> 51)); 509 h4 = ((uint64_t) a) & mask; 510 511 h0 += (a >> 51) * 19ULL; 512 513 h[0] = h0; 514 h[1] = h1; 515 h[2] = h2; 516 h[3] = h3; 517 h[4] = h4; 518 } 519