third_party/heimdal/lib/hcrypto/x25519/ed25519_ref10_fe_51.h

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