wolf SSL / wolfSSL

wolfSSL SSL/TLS library, support up to TLS1.3

Dependents:   CyaSSL-Twitter-OAuth4Tw Example-client-tls-cert TwitterReader TweetTest ... more

wolfcrypt/src/fe_low_mem.c@7:481bce714567, 2017-05-02 (annotated)

Committer:
wolfSSL
Date:
Tue May 02 08:44:47 2017 +0000
Revision:
7:481bce714567
wolfSSL3.10.2

Who changed what in which revision?

UserRevisionLine numberNew contents of line
wolfSSL 7:481bce714567 1 /* fe_low_mem.c
wolfSSL 7:481bce714567 2 *
wolfSSL 7:481bce714567 3 * Copyright (C) 2006-2016 wolfSSL Inc.
wolfSSL 7:481bce714567 4 *
wolfSSL 7:481bce714567 5 * This file is part of wolfSSL.
wolfSSL 7:481bce714567 6 *
wolfSSL 7:481bce714567 7 * wolfSSL is free software; you can redistribute it and/or modify
wolfSSL 7:481bce714567 8 * it under the terms of the GNU General Public License as published by
wolfSSL 7:481bce714567 9 * the Free Software Foundation; either version 2 of the License, or
wolfSSL 7:481bce714567 10 * (at your option) any later version.
wolfSSL 7:481bce714567 11 *
wolfSSL 7:481bce714567 12 * wolfSSL is distributed in the hope that it will be useful,
wolfSSL 7:481bce714567 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
wolfSSL 7:481bce714567 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
wolfSSL 7:481bce714567 15 * GNU General Public License for more details.
wolfSSL 7:481bce714567 16 *
wolfSSL 7:481bce714567 17 * You should have received a copy of the GNU General Public License
wolfSSL 7:481bce714567 18 * along with this program; if not, write to the Free Software
wolfSSL 7:481bce714567 19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335, USA
wolfSSL 7:481bce714567 20 */
wolfSSL 7:481bce714567 21
wolfSSL 7:481bce714567 22
wolfSSL 7:481bce714567 23 /* Based from Daniel Beer's public domain word. */
wolfSSL 7:481bce714567 24
wolfSSL 7:481bce714567 25 #ifdef HAVE_CONFIG_H
wolfSSL 7:481bce714567 26 #include <config.h>
wolfSSL 7:481bce714567 27 #endif
wolfSSL 7:481bce714567 28
wolfSSL 7:481bce714567 29 #include <wolfssl/wolfcrypt/settings.h>
wolfSSL 7:481bce714567 30
wolfSSL 7:481bce714567 31 #if defined(CURVED25519_SMALL) /* use slower code that takes less memory */
wolfSSL 7:481bce714567 32 #if defined(HAVE_ED25519) || defined(HAVE_CURVE25519)
wolfSSL 7:481bce714567 33
wolfSSL 7:481bce714567 34 #include <wolfssl/wolfcrypt/fe_operations.h>
wolfSSL 7:481bce714567 35
wolfSSL 7:481bce714567 36 #ifdef NO_INLINE
wolfSSL 7:481bce714567 37 #include <wolfssl/wolfcrypt/misc.h>
wolfSSL 7:481bce714567 38 #else
wolfSSL 7:481bce714567 39 #define WOLFSSL_MISC_INCLUDED
wolfSSL 7:481bce714567 40 #include <wolfcrypt/src/misc.c>
wolfSSL 7:481bce714567 41 #endif
wolfSSL 7:481bce714567 42
wolfSSL 7:481bce714567 43
wolfSSL 7:481bce714567 44 void fprime_copy(byte *x, const byte *a)
wolfSSL 7:481bce714567 45 {
wolfSSL 7:481bce714567 46 int i;
wolfSSL 7:481bce714567 47 for (i = 0; i < F25519_SIZE; i++)
wolfSSL 7:481bce714567 48 x[i] = a[i];
wolfSSL 7:481bce714567 49 }
wolfSSL 7:481bce714567 50
wolfSSL 7:481bce714567 51
wolfSSL 7:481bce714567 52 void fe_copy(fe x, const fe a)
wolfSSL 7:481bce714567 53 {
wolfSSL 7:481bce714567 54 int i;
wolfSSL 7:481bce714567 55 for (i = 0; i < F25519_SIZE; i++)
wolfSSL 7:481bce714567 56 x[i] = a[i];
wolfSSL 7:481bce714567 57 }
wolfSSL 7:481bce714567 58
wolfSSL 7:481bce714567 59
wolfSSL 7:481bce714567 60 /* Double an X-coordinate */
wolfSSL 7:481bce714567 61 static void xc_double(byte *x3, byte *z3,
wolfSSL 7:481bce714567 62 const byte *x1, const byte *z1)
wolfSSL 7:481bce714567 63 {
wolfSSL 7:481bce714567 64 /* Explicit formulas database: dbl-1987-m
wolfSSL 7:481bce714567 65 *
wolfSSL 7:481bce714567 66 * source 1987 Montgomery "Speeding the Pollard and elliptic
wolfSSL 7:481bce714567 67 * curve methods of factorization", page 261, fourth display
wolfSSL 7:481bce714567 68 * compute X3 = (X1^2-Z1^2)^2
wolfSSL 7:481bce714567 69 * compute Z3 = 4 X1 Z1 (X1^2 + a X1 Z1 + Z1^2)
wolfSSL 7:481bce714567 70 */
wolfSSL 7:481bce714567 71 byte x1sq[F25519_SIZE];
wolfSSL 7:481bce714567 72 byte z1sq[F25519_SIZE];
wolfSSL 7:481bce714567 73 byte x1z1[F25519_SIZE];
wolfSSL 7:481bce714567 74 byte a[F25519_SIZE];
wolfSSL 7:481bce714567 75
wolfSSL 7:481bce714567 76 fe_mul__distinct(x1sq, x1, x1);
wolfSSL 7:481bce714567 77 fe_mul__distinct(z1sq, z1, z1);
wolfSSL 7:481bce714567 78 fe_mul__distinct(x1z1, x1, z1);
wolfSSL 7:481bce714567 79
wolfSSL 7:481bce714567 80 fe_sub(a, x1sq, z1sq);
wolfSSL 7:481bce714567 81 fe_mul__distinct(x3, a, a);
wolfSSL 7:481bce714567 82
wolfSSL 7:481bce714567 83 fe_mul_c(a, x1z1, 486662);
wolfSSL 7:481bce714567 84 fe_add(a, x1sq, a);
wolfSSL 7:481bce714567 85 fe_add(a, z1sq, a);
wolfSSL 7:481bce714567 86 fe_mul__distinct(x1sq, x1z1, a);
wolfSSL 7:481bce714567 87 fe_mul_c(z3, x1sq, 4);
wolfSSL 7:481bce714567 88 }
wolfSSL 7:481bce714567 89
wolfSSL 7:481bce714567 90
wolfSSL 7:481bce714567 91 /* Differential addition */
wolfSSL 7:481bce714567 92 static void xc_diffadd(byte *x5, byte *z5,
wolfSSL 7:481bce714567 93 const byte *x1, const byte *z1,
wolfSSL 7:481bce714567 94 const byte *x2, const byte *z2,
wolfSSL 7:481bce714567 95 const byte *x3, const byte *z3)
wolfSSL 7:481bce714567 96 {
wolfSSL 7:481bce714567 97 /* Explicit formulas database: dbl-1987-m3
wolfSSL 7:481bce714567 98 *
wolfSSL 7:481bce714567 99 * source 1987 Montgomery "Speeding the Pollard and elliptic curve
wolfSSL 7:481bce714567 100 * methods of factorization", page 261, fifth display, plus
wolfSSL 7:481bce714567 101 * common-subexpression elimination
wolfSSL 7:481bce714567 102 * compute A = X2+Z2
wolfSSL 7:481bce714567 103 * compute B = X2-Z2
wolfSSL 7:481bce714567 104 * compute C = X3+Z3
wolfSSL 7:481bce714567 105 * compute D = X3-Z3
wolfSSL 7:481bce714567 106 * compute DA = D A
wolfSSL 7:481bce714567 107 * compute CB = C B
wolfSSL 7:481bce714567 108 * compute X5 = Z1(DA+CB)^2
wolfSSL 7:481bce714567 109 * compute Z5 = X1(DA-CB)^2
wolfSSL 7:481bce714567 110 */
wolfSSL 7:481bce714567 111 byte da[F25519_SIZE];
wolfSSL 7:481bce714567 112 byte cb[F25519_SIZE];
wolfSSL 7:481bce714567 113 byte a[F25519_SIZE];
wolfSSL 7:481bce714567 114 byte b[F25519_SIZE];
wolfSSL 7:481bce714567 115
wolfSSL 7:481bce714567 116 fe_add(a, x2, z2);
wolfSSL 7:481bce714567 117 fe_sub(b, x3, z3); /* D */
wolfSSL 7:481bce714567 118 fe_mul__distinct(da, a, b);
wolfSSL 7:481bce714567 119
wolfSSL 7:481bce714567 120 fe_sub(b, x2, z2);
wolfSSL 7:481bce714567 121 fe_add(a, x3, z3); /* C */
wolfSSL 7:481bce714567 122 fe_mul__distinct(cb, a, b);
wolfSSL 7:481bce714567 123
wolfSSL 7:481bce714567 124 fe_add(a, da, cb);
wolfSSL 7:481bce714567 125 fe_mul__distinct(b, a, a);
wolfSSL 7:481bce714567 126 fe_mul__distinct(x5, z1, b);
wolfSSL 7:481bce714567 127
wolfSSL 7:481bce714567 128 fe_sub(a, da, cb);
wolfSSL 7:481bce714567 129 fe_mul__distinct(b, a, a);
wolfSSL 7:481bce714567 130 fe_mul__distinct(z5, x1, b);
wolfSSL 7:481bce714567 131 }
wolfSSL 7:481bce714567 132
wolfSSL 7:481bce714567 133 #ifndef FREESCALE_LTC_ECC
wolfSSL 7:481bce714567 134 int curve25519(byte *result, byte *e, byte *q)
wolfSSL 7:481bce714567 135 {
wolfSSL 7:481bce714567 136 /* Current point: P_m */
wolfSSL 7:481bce714567 137 byte xm[F25519_SIZE];
wolfSSL 7:481bce714567 138 byte zm[F25519_SIZE] = {1};
wolfSSL 7:481bce714567 139
wolfSSL 7:481bce714567 140 /* Predecessor: P_(m-1) */
wolfSSL 7:481bce714567 141 byte xm1[F25519_SIZE] = {1};
wolfSSL 7:481bce714567 142 byte zm1[F25519_SIZE] = {0};
wolfSSL 7:481bce714567 143
wolfSSL 7:481bce714567 144 int i;
wolfSSL 7:481bce714567 145
wolfSSL 7:481bce714567 146 /* Note: bit 254 is assumed to be 1 */
wolfSSL 7:481bce714567 147 fe_copy(xm, q);
wolfSSL 7:481bce714567 148
wolfSSL 7:481bce714567 149 for (i = 253; i >= 0; i--) {
wolfSSL 7:481bce714567 150 const int bit = (e[i >> 3] >> (i & 7)) & 1;
wolfSSL 7:481bce714567 151 byte xms[F25519_SIZE];
wolfSSL 7:481bce714567 152 byte zms[F25519_SIZE];
wolfSSL 7:481bce714567 153
wolfSSL 7:481bce714567 154 /* From P_m and P_(m-1), compute P_(2m) and P_(2m-1) */
wolfSSL 7:481bce714567 155 xc_diffadd(xm1, zm1, q, f25519_one, xm, zm, xm1, zm1);
wolfSSL 7:481bce714567 156 xc_double(xm, zm, xm, zm);
wolfSSL 7:481bce714567 157
wolfSSL 7:481bce714567 158 /* Compute P_(2m+1) */
wolfSSL 7:481bce714567 159 xc_diffadd(xms, zms, xm1, zm1, xm, zm, q, f25519_one);
wolfSSL 7:481bce714567 160
wolfSSL 7:481bce714567 161 /* Select:
wolfSSL 7:481bce714567 162 * bit = 1 --> (P_(2m+1), P_(2m))
wolfSSL 7:481bce714567 163 * bit = 0 --> (P_(2m), P_(2m-1))
wolfSSL 7:481bce714567 164 */
wolfSSL 7:481bce714567 165 fe_select(xm1, xm1, xm, bit);
wolfSSL 7:481bce714567 166 fe_select(zm1, zm1, zm, bit);
wolfSSL 7:481bce714567 167 fe_select(xm, xm, xms, bit);
wolfSSL 7:481bce714567 168 fe_select(zm, zm, zms, bit);
wolfSSL 7:481bce714567 169 }
wolfSSL 7:481bce714567 170
wolfSSL 7:481bce714567 171 /* Freeze out of projective coordinates */
wolfSSL 7:481bce714567 172 fe_inv__distinct(zm1, zm);
wolfSSL 7:481bce714567 173 fe_mul__distinct(result, zm1, xm);
wolfSSL 7:481bce714567 174 fe_normalize(result);
wolfSSL 7:481bce714567 175 return 0;
wolfSSL 7:481bce714567 176 }
wolfSSL 7:481bce714567 177 #endif /* !FREESCALE_LTC_ECC */
wolfSSL 7:481bce714567 178
wolfSSL 7:481bce714567 179 static void raw_add(byte *x, const byte *p)
wolfSSL 7:481bce714567 180 {
wolfSSL 7:481bce714567 181 word16 c = 0;
wolfSSL 7:481bce714567 182 int i;
wolfSSL 7:481bce714567 183
wolfSSL 7:481bce714567 184 for (i = 0; i < F25519_SIZE; i++) {
wolfSSL 7:481bce714567 185 c += ((word16)x[i]) + ((word16)p[i]);
wolfSSL 7:481bce714567 186 x[i] = c;
wolfSSL 7:481bce714567 187 c >>= 8;
wolfSSL 7:481bce714567 188 }
wolfSSL 7:481bce714567 189 }
wolfSSL 7:481bce714567 190
wolfSSL 7:481bce714567 191
wolfSSL 7:481bce714567 192 static void raw_try_sub(byte *x, const byte *p)
wolfSSL 7:481bce714567 193 {
wolfSSL 7:481bce714567 194 byte minusp[F25519_SIZE];
wolfSSL 7:481bce714567 195 word16 c = 0;
wolfSSL 7:481bce714567 196 int i;
wolfSSL 7:481bce714567 197
wolfSSL 7:481bce714567 198 for (i = 0; i < F25519_SIZE; i++) {
wolfSSL 7:481bce714567 199 c = ((word16)x[i]) - ((word16)p[i]) - c;
wolfSSL 7:481bce714567 200 minusp[i] = c;
wolfSSL 7:481bce714567 201 c = (c >> 8) & 1;
wolfSSL 7:481bce714567 202 }
wolfSSL 7:481bce714567 203
wolfSSL 7:481bce714567 204 fprime_select(x, minusp, x, c);
wolfSSL 7:481bce714567 205 }
wolfSSL 7:481bce714567 206
wolfSSL 7:481bce714567 207
wolfSSL 7:481bce714567 208 static int prime_msb(const byte *p)
wolfSSL 7:481bce714567 209 {
wolfSSL 7:481bce714567 210 int i;
wolfSSL 7:481bce714567 211 byte x;
wolfSSL 7:481bce714567 212 int shift = 1;
wolfSSL 7:481bce714567 213 int z = F25519_SIZE - 1;
wolfSSL 7:481bce714567 214
wolfSSL 7:481bce714567 215 /*
wolfSSL 7:481bce714567 216 Test for any hot bits.
wolfSSL 7:481bce714567 217 As soon as one instance is encountered set shift to 0.
wolfSSL 7:481bce714567 218 */
wolfSSL 7:481bce714567 219 for (i = F25519_SIZE - 1; i >= 0; i--) {
wolfSSL 7:481bce714567 220 shift &= ((shift ^ ((-p[i] | p[i]) >> 7)) & 1);
wolfSSL 7:481bce714567 221 z -= shift;
wolfSSL 7:481bce714567 222 }
wolfSSL 7:481bce714567 223 x = p[z];
wolfSSL 7:481bce714567 224 z <<= 3;
wolfSSL 7:481bce714567 225 shift = 1;
wolfSSL 7:481bce714567 226 for (i = 0; i < 8; i++) {
wolfSSL 7:481bce714567 227 shift &= ((-(x >> i) | (x >> i)) >> (7 - i) & 1);
wolfSSL 7:481bce714567 228 z += shift;
wolfSSL 7:481bce714567 229 }
wolfSSL 7:481bce714567 230
wolfSSL 7:481bce714567 231 return z - 1;
wolfSSL 7:481bce714567 232 }
wolfSSL 7:481bce714567 233
wolfSSL 7:481bce714567 234
wolfSSL 7:481bce714567 235 void fprime_select(byte *dst, const byte *zero, const byte *one, byte condition)
wolfSSL 7:481bce714567 236 {
wolfSSL 7:481bce714567 237 const byte mask = -condition;
wolfSSL 7:481bce714567 238 int i;
wolfSSL 7:481bce714567 239
wolfSSL 7:481bce714567 240 for (i = 0; i < F25519_SIZE; i++)
wolfSSL 7:481bce714567 241 dst[i] = zero[i] ^ (mask & (one[i] ^ zero[i]));
wolfSSL 7:481bce714567 242 }
wolfSSL 7:481bce714567 243
wolfSSL 7:481bce714567 244
wolfSSL 7:481bce714567 245 void fprime_add(byte *r, const byte *a, const byte *modulus)
wolfSSL 7:481bce714567 246 {
wolfSSL 7:481bce714567 247 raw_add(r, a);
wolfSSL 7:481bce714567 248 raw_try_sub(r, modulus);
wolfSSL 7:481bce714567 249 }
wolfSSL 7:481bce714567 250
wolfSSL 7:481bce714567 251
wolfSSL 7:481bce714567 252 void fprime_sub(byte *r, const byte *a, const byte *modulus)
wolfSSL 7:481bce714567 253 {
wolfSSL 7:481bce714567 254 raw_add(r, modulus);
wolfSSL 7:481bce714567 255 raw_try_sub(r, a);
wolfSSL 7:481bce714567 256 raw_try_sub(r, modulus);
wolfSSL 7:481bce714567 257 }
wolfSSL 7:481bce714567 258
wolfSSL 7:481bce714567 259
wolfSSL 7:481bce714567 260 void fprime_mul(byte *r, const byte *a, const byte *b,
wolfSSL 7:481bce714567 261 const byte *modulus)
wolfSSL 7:481bce714567 262 {
wolfSSL 7:481bce714567 263 word16 c = 0;
wolfSSL 7:481bce714567 264 int i,j;
wolfSSL 7:481bce714567 265
wolfSSL 7:481bce714567 266 XMEMSET(r, 0, F25519_SIZE);
wolfSSL 7:481bce714567 267
wolfSSL 7:481bce714567 268 for (i = prime_msb(modulus); i >= 0; i--) {
wolfSSL 7:481bce714567 269 const byte bit = (b[i >> 3] >> (i & 7)) & 1;
wolfSSL 7:481bce714567 270 byte plusa[F25519_SIZE];
wolfSSL 7:481bce714567 271
wolfSSL 7:481bce714567 272 for (j = 0; j < F25519_SIZE; j++) {
wolfSSL 7:481bce714567 273 c |= ((word16)r[j]) << 1;
wolfSSL 7:481bce714567 274 r[j] = c;
wolfSSL 7:481bce714567 275 c >>= 8;
wolfSSL 7:481bce714567 276 }
wolfSSL 7:481bce714567 277 raw_try_sub(r, modulus);
wolfSSL 7:481bce714567 278
wolfSSL 7:481bce714567 279 fprime_copy(plusa, r);
wolfSSL 7:481bce714567 280 fprime_add(plusa, a, modulus);
wolfSSL 7:481bce714567 281
wolfSSL 7:481bce714567 282 fprime_select(r, r, plusa, bit);
wolfSSL 7:481bce714567 283 }
wolfSSL 7:481bce714567 284 }
wolfSSL 7:481bce714567 285
wolfSSL 7:481bce714567 286
wolfSSL 7:481bce714567 287 void fe_load(byte *x, word32 c)
wolfSSL 7:481bce714567 288 {
wolfSSL 7:481bce714567 289 word32 i;
wolfSSL 7:481bce714567 290
wolfSSL 7:481bce714567 291 for (i = 0; i < sizeof(c); i++) {
wolfSSL 7:481bce714567 292 x[i] = c;
wolfSSL 7:481bce714567 293 c >>= 8;
wolfSSL 7:481bce714567 294 }
wolfSSL 7:481bce714567 295
wolfSSL 7:481bce714567 296 for (; i < F25519_SIZE; i++)
wolfSSL 7:481bce714567 297 x[i] = 0;
wolfSSL 7:481bce714567 298 }
wolfSSL 7:481bce714567 299
wolfSSL 7:481bce714567 300
wolfSSL 7:481bce714567 301 void fe_normalize(byte *x)
wolfSSL 7:481bce714567 302 {
wolfSSL 7:481bce714567 303 byte minusp[F25519_SIZE];
wolfSSL 7:481bce714567 304 word16 c;
wolfSSL 7:481bce714567 305 int i;
wolfSSL 7:481bce714567 306
wolfSSL 7:481bce714567 307 /* Reduce using 2^255 = 19 mod p */
wolfSSL 7:481bce714567 308 c = (x[31] >> 7) * 19;
wolfSSL 7:481bce714567 309 x[31] &= 127;
wolfSSL 7:481bce714567 310
wolfSSL 7:481bce714567 311 for (i = 0; i < F25519_SIZE; i++) {
wolfSSL 7:481bce714567 312 c += x[i];
wolfSSL 7:481bce714567 313 x[i] = c;
wolfSSL 7:481bce714567 314 c >>= 8;
wolfSSL 7:481bce714567 315 }
wolfSSL 7:481bce714567 316
wolfSSL 7:481bce714567 317 /* The number is now less than 2^255 + 18, and therefore less than
wolfSSL 7:481bce714567 318 * 2p. Try subtracting p, and conditionally load the subtracted
wolfSSL 7:481bce714567 319 * value if underflow did not occur.
wolfSSL 7:481bce714567 320 */
wolfSSL 7:481bce714567 321 c = 19;
wolfSSL 7:481bce714567 322
wolfSSL 7:481bce714567 323 for (i = 0; i + 1 < F25519_SIZE; i++) {
wolfSSL 7:481bce714567 324 c += x[i];
wolfSSL 7:481bce714567 325 minusp[i] = c;
wolfSSL 7:481bce714567 326 c >>= 8;
wolfSSL 7:481bce714567 327 }
wolfSSL 7:481bce714567 328
wolfSSL 7:481bce714567 329 c += ((word16)x[i]) - 128;
wolfSSL 7:481bce714567 330 minusp[31] = c;
wolfSSL 7:481bce714567 331
wolfSSL 7:481bce714567 332 /* Load x-p if no underflow */
wolfSSL 7:481bce714567 333 fe_select(x, minusp, x, (c >> 15) & 1);
wolfSSL 7:481bce714567 334 }
wolfSSL 7:481bce714567 335
wolfSSL 7:481bce714567 336
wolfSSL 7:481bce714567 337 void fe_select(byte *dst,
wolfSSL 7:481bce714567 338 const byte *zero, const byte *one,
wolfSSL 7:481bce714567 339 byte condition)
wolfSSL 7:481bce714567 340 {
wolfSSL 7:481bce714567 341 const byte mask = -condition;
wolfSSL 7:481bce714567 342 int i;
wolfSSL 7:481bce714567 343
wolfSSL 7:481bce714567 344 for (i = 0; i < F25519_SIZE; i++)
wolfSSL 7:481bce714567 345 dst[i] = zero[i] ^ (mask & (one[i] ^ zero[i]));
wolfSSL 7:481bce714567 346 }
wolfSSL 7:481bce714567 347
wolfSSL 7:481bce714567 348
wolfSSL 7:481bce714567 349 void fe_add(fe r, const fe a, const fe b)
wolfSSL 7:481bce714567 350 {
wolfSSL 7:481bce714567 351 word16 c = 0;
wolfSSL 7:481bce714567 352 int i;
wolfSSL 7:481bce714567 353
wolfSSL 7:481bce714567 354 /* Add */
wolfSSL 7:481bce714567 355 for (i = 0; i < F25519_SIZE; i++) {
wolfSSL 7:481bce714567 356 c >>= 8;
wolfSSL 7:481bce714567 357 c += ((word16)a[i]) + ((word16)b[i]);
wolfSSL 7:481bce714567 358 r[i] = c;
wolfSSL 7:481bce714567 359 }
wolfSSL 7:481bce714567 360
wolfSSL 7:481bce714567 361 /* Reduce with 2^255 = 19 mod p */
wolfSSL 7:481bce714567 362 r[31] &= 127;
wolfSSL 7:481bce714567 363 c = (c >> 7) * 19;
wolfSSL 7:481bce714567 364
wolfSSL 7:481bce714567 365 for (i = 0; i < F25519_SIZE; i++) {
wolfSSL 7:481bce714567 366 c += r[i];
wolfSSL 7:481bce714567 367 r[i] = c;
wolfSSL 7:481bce714567 368 c >>= 8;
wolfSSL 7:481bce714567 369 }
wolfSSL 7:481bce714567 370 }
wolfSSL 7:481bce714567 371
wolfSSL 7:481bce714567 372
wolfSSL 7:481bce714567 373 void fe_sub(fe r, const fe a, const fe b)
wolfSSL 7:481bce714567 374 {
wolfSSL 7:481bce714567 375 word32 c = 0;
wolfSSL 7:481bce714567 376 int i;
wolfSSL 7:481bce714567 377
wolfSSL 7:481bce714567 378 /* Calculate a + 2p - b, to avoid underflow */
wolfSSL 7:481bce714567 379 c = 218;
wolfSSL 7:481bce714567 380 for (i = 0; i + 1 < F25519_SIZE; i++) {
wolfSSL 7:481bce714567 381 c += 65280 + ((word32)a[i]) - ((word32)b[i]);
wolfSSL 7:481bce714567 382 r[i] = c;
wolfSSL 7:481bce714567 383 c >>= 8;
wolfSSL 7:481bce714567 384 }
wolfSSL 7:481bce714567 385
wolfSSL 7:481bce714567 386 c += ((word32)a[31]) - ((word32)b[31]);
wolfSSL 7:481bce714567 387 r[31] = c & 127;
wolfSSL 7:481bce714567 388 c = (c >> 7) * 19;
wolfSSL 7:481bce714567 389
wolfSSL 7:481bce714567 390 for (i = 0; i < F25519_SIZE; i++) {
wolfSSL 7:481bce714567 391 c += r[i];
wolfSSL 7:481bce714567 392 r[i] = c;
wolfSSL 7:481bce714567 393 c >>= 8;
wolfSSL 7:481bce714567 394 }
wolfSSL 7:481bce714567 395 }
wolfSSL 7:481bce714567 396
wolfSSL 7:481bce714567 397
wolfSSL 7:481bce714567 398 void fe_neg(fe r, const fe a)
wolfSSL 7:481bce714567 399 {
wolfSSL 7:481bce714567 400 word32 c = 0;
wolfSSL 7:481bce714567 401 int i;
wolfSSL 7:481bce714567 402
wolfSSL 7:481bce714567 403 /* Calculate 2p - a, to avoid underflow */
wolfSSL 7:481bce714567 404 c = 218;
wolfSSL 7:481bce714567 405 for (i = 0; i + 1 < F25519_SIZE; i++) {
wolfSSL 7:481bce714567 406 c += 65280 - ((word32)a[i]);
wolfSSL 7:481bce714567 407 r[i] = c;
wolfSSL 7:481bce714567 408 c >>= 8;
wolfSSL 7:481bce714567 409 }
wolfSSL 7:481bce714567 410
wolfSSL 7:481bce714567 411 c -= ((word32)a[31]);
wolfSSL 7:481bce714567 412 r[31] = c & 127;
wolfSSL 7:481bce714567 413 c = (c >> 7) * 19;
wolfSSL 7:481bce714567 414
wolfSSL 7:481bce714567 415 for (i = 0; i < F25519_SIZE; i++) {
wolfSSL 7:481bce714567 416 c += r[i];
wolfSSL 7:481bce714567 417 r[i] = c;
wolfSSL 7:481bce714567 418 c >>= 8;
wolfSSL 7:481bce714567 419 }
wolfSSL 7:481bce714567 420 }
wolfSSL 7:481bce714567 421
wolfSSL 7:481bce714567 422
wolfSSL 7:481bce714567 423 void fe_mul__distinct(byte *r, const byte *a, const byte *b)
wolfSSL 7:481bce714567 424 {
wolfSSL 7:481bce714567 425 word32 c = 0;
wolfSSL 7:481bce714567 426 int i;
wolfSSL 7:481bce714567 427
wolfSSL 7:481bce714567 428 for (i = 0; i < F25519_SIZE; i++) {
wolfSSL 7:481bce714567 429 int j;
wolfSSL 7:481bce714567 430
wolfSSL 7:481bce714567 431 c >>= 8;
wolfSSL 7:481bce714567 432 for (j = 0; j <= i; j++)
wolfSSL 7:481bce714567 433 c += ((word32)a[j]) * ((word32)b[i - j]);
wolfSSL 7:481bce714567 434
wolfSSL 7:481bce714567 435 for (; j < F25519_SIZE; j++)
wolfSSL 7:481bce714567 436 c += ((word32)a[j]) *
wolfSSL 7:481bce714567 437 ((word32)b[i + F25519_SIZE - j]) * 38;
wolfSSL 7:481bce714567 438
wolfSSL 7:481bce714567 439 r[i] = c;
wolfSSL 7:481bce714567 440 }
wolfSSL 7:481bce714567 441
wolfSSL 7:481bce714567 442 r[31] &= 127;
wolfSSL 7:481bce714567 443 c = (c >> 7) * 19;
wolfSSL 7:481bce714567 444
wolfSSL 7:481bce714567 445 for (i = 0; i < F25519_SIZE; i++) {
wolfSSL 7:481bce714567 446 c += r[i];
wolfSSL 7:481bce714567 447 r[i] = c;
wolfSSL 7:481bce714567 448 c >>= 8;
wolfSSL 7:481bce714567 449 }
wolfSSL 7:481bce714567 450 }
wolfSSL 7:481bce714567 451
wolfSSL 7:481bce714567 452
wolfSSL 7:481bce714567 453 void fe_mul(fe r, const fe a, const fe b)
wolfSSL 7:481bce714567 454 {
wolfSSL 7:481bce714567 455 byte tmp[F25519_SIZE];
wolfSSL 7:481bce714567 456
wolfSSL 7:481bce714567 457 fe_mul__distinct(tmp, a, b);
wolfSSL 7:481bce714567 458 fe_copy(r, tmp);
wolfSSL 7:481bce714567 459 }
wolfSSL 7:481bce714567 460
wolfSSL 7:481bce714567 461
wolfSSL 7:481bce714567 462 void fe_mul_c(byte *r, const byte *a, word32 b)
wolfSSL 7:481bce714567 463 {
wolfSSL 7:481bce714567 464 word32 c = 0;
wolfSSL 7:481bce714567 465 int i;
wolfSSL 7:481bce714567 466
wolfSSL 7:481bce714567 467 for (i = 0; i < F25519_SIZE; i++) {
wolfSSL 7:481bce714567 468 c >>= 8;
wolfSSL 7:481bce714567 469 c += b * ((word32)a[i]);
wolfSSL 7:481bce714567 470 r[i] = c;
wolfSSL 7:481bce714567 471 }
wolfSSL 7:481bce714567 472
wolfSSL 7:481bce714567 473 r[31] &= 127;
wolfSSL 7:481bce714567 474 c >>= 7;
wolfSSL 7:481bce714567 475 c *= 19;
wolfSSL 7:481bce714567 476
wolfSSL 7:481bce714567 477 for (i = 0; i < F25519_SIZE; i++) {
wolfSSL 7:481bce714567 478 c += r[i];
wolfSSL 7:481bce714567 479 r[i] = c;
wolfSSL 7:481bce714567 480 c >>= 8;
wolfSSL 7:481bce714567 481 }
wolfSSL 7:481bce714567 482 }
wolfSSL 7:481bce714567 483
wolfSSL 7:481bce714567 484
wolfSSL 7:481bce714567 485 void fe_inv__distinct(byte *r, const byte *x)
wolfSSL 7:481bce714567 486 {
wolfSSL 7:481bce714567 487 byte s[F25519_SIZE];
wolfSSL 7:481bce714567 488 int i;
wolfSSL 7:481bce714567 489
wolfSSL 7:481bce714567 490 /* This is a prime field, so by Fermat's little theorem:
wolfSSL 7:481bce714567 491 *
wolfSSL 7:481bce714567 492 * x^(p-1) = 1 mod p
wolfSSL 7:481bce714567 493 *
wolfSSL 7:481bce714567 494 * Therefore, raise to (p-2) = 2^255-21 to get a multiplicative
wolfSSL 7:481bce714567 495 * inverse.
wolfSSL 7:481bce714567 496 *
wolfSSL 7:481bce714567 497 * This is a 255-bit binary number with the digits:
wolfSSL 7:481bce714567 498 *
wolfSSL 7:481bce714567 499 * 11111111... 01011
wolfSSL 7:481bce714567 500 *
wolfSSL 7:481bce714567 501 * We compute the result by the usual binary chain, but
wolfSSL 7:481bce714567 502 * alternate between keeping the accumulator in r and s, so as
wolfSSL 7:481bce714567 503 * to avoid copying temporaries.
wolfSSL 7:481bce714567 504 */
wolfSSL 7:481bce714567 505
wolfSSL 7:481bce714567 506 /* 1 1 */
wolfSSL 7:481bce714567 507 fe_mul__distinct(s, x, x);
wolfSSL 7:481bce714567 508 fe_mul__distinct(r, s, x);
wolfSSL 7:481bce714567 509
wolfSSL 7:481bce714567 510 /* 1 x 248 */
wolfSSL 7:481bce714567 511 for (i = 0; i < 248; i++) {
wolfSSL 7:481bce714567 512 fe_mul__distinct(s, r, r);
wolfSSL 7:481bce714567 513 fe_mul__distinct(r, s, x);
wolfSSL 7:481bce714567 514 }
wolfSSL 7:481bce714567 515
wolfSSL 7:481bce714567 516 /* 0 */
wolfSSL 7:481bce714567 517 fe_mul__distinct(s, r, r);
wolfSSL 7:481bce714567 518
wolfSSL 7:481bce714567 519 /* 1 */
wolfSSL 7:481bce714567 520 fe_mul__distinct(r, s, s);
wolfSSL 7:481bce714567 521 fe_mul__distinct(s, r, x);
wolfSSL 7:481bce714567 522
wolfSSL 7:481bce714567 523 /* 0 */
wolfSSL 7:481bce714567 524 fe_mul__distinct(r, s, s);
wolfSSL 7:481bce714567 525
wolfSSL 7:481bce714567 526 /* 1 */
wolfSSL 7:481bce714567 527 fe_mul__distinct(s, r, r);
wolfSSL 7:481bce714567 528 fe_mul__distinct(r, s, x);
wolfSSL 7:481bce714567 529
wolfSSL 7:481bce714567 530 /* 1 */
wolfSSL 7:481bce714567 531 fe_mul__distinct(s, r, r);
wolfSSL 7:481bce714567 532 fe_mul__distinct(r, s, x);
wolfSSL 7:481bce714567 533 }
wolfSSL 7:481bce714567 534
wolfSSL 7:481bce714567 535
wolfSSL 7:481bce714567 536 void fe_invert(fe r, const fe x)
wolfSSL 7:481bce714567 537 {
wolfSSL 7:481bce714567 538 byte tmp[F25519_SIZE];
wolfSSL 7:481bce714567 539
wolfSSL 7:481bce714567 540 fe_inv__distinct(tmp, x);
wolfSSL 7:481bce714567 541 fe_copy(r, tmp);
wolfSSL 7:481bce714567 542 }
wolfSSL 7:481bce714567 543
wolfSSL 7:481bce714567 544
wolfSSL 7:481bce714567 545 /* Raise x to the power of (p-5)/8 = 2^252-3, using s for temporary
wolfSSL 7:481bce714567 546 * storage.
wolfSSL 7:481bce714567 547 */
wolfSSL 7:481bce714567 548 static void exp2523(byte *r, const byte *x, byte *s)
wolfSSL 7:481bce714567 549 {
wolfSSL 7:481bce714567 550 int i;
wolfSSL 7:481bce714567 551
wolfSSL 7:481bce714567 552 /* This number is a 252-bit number with the binary expansion:
wolfSSL 7:481bce714567 553 *
wolfSSL 7:481bce714567 554 * 111111... 01
wolfSSL 7:481bce714567 555 */
wolfSSL 7:481bce714567 556
wolfSSL 7:481bce714567 557 /* 1 1 */
wolfSSL 7:481bce714567 558 fe_mul__distinct(r, x, x);
wolfSSL 7:481bce714567 559 fe_mul__distinct(s, r, x);
wolfSSL 7:481bce714567 560
wolfSSL 7:481bce714567 561 /* 1 x 248 */
wolfSSL 7:481bce714567 562 for (i = 0; i < 248; i++) {
wolfSSL 7:481bce714567 563 fe_mul__distinct(r, s, s);
wolfSSL 7:481bce714567 564 fe_mul__distinct(s, r, x);
wolfSSL 7:481bce714567 565 }
wolfSSL 7:481bce714567 566
wolfSSL 7:481bce714567 567 /* 0 */
wolfSSL 7:481bce714567 568 fe_mul__distinct(r, s, s);
wolfSSL 7:481bce714567 569
wolfSSL 7:481bce714567 570 /* 1 */
wolfSSL 7:481bce714567 571 fe_mul__distinct(s, r, r);
wolfSSL 7:481bce714567 572 fe_mul__distinct(r, s, x);
wolfSSL 7:481bce714567 573 }
wolfSSL 7:481bce714567 574
wolfSSL 7:481bce714567 575
wolfSSL 7:481bce714567 576 void fe_sqrt(byte *r, const byte *a)
wolfSSL 7:481bce714567 577 {
wolfSSL 7:481bce714567 578 byte v[F25519_SIZE];
wolfSSL 7:481bce714567 579 byte i[F25519_SIZE];
wolfSSL 7:481bce714567 580 byte x[F25519_SIZE];
wolfSSL 7:481bce714567 581 byte y[F25519_SIZE];
wolfSSL 7:481bce714567 582
wolfSSL 7:481bce714567 583 /* v = (2a)^((p-5)/8) [x = 2a] */
wolfSSL 7:481bce714567 584 fe_mul_c(x, a, 2);
wolfSSL 7:481bce714567 585 exp2523(v, x, y);
wolfSSL 7:481bce714567 586
wolfSSL 7:481bce714567 587 /* i = 2av^2 - 1 */
wolfSSL 7:481bce714567 588 fe_mul__distinct(y, v, v);
wolfSSL 7:481bce714567 589 fe_mul__distinct(i, x, y);
wolfSSL 7:481bce714567 590 fe_load(y, 1);
wolfSSL 7:481bce714567 591 fe_sub(i, i, y);
wolfSSL 7:481bce714567 592
wolfSSL 7:481bce714567 593 /* r = avi */
wolfSSL 7:481bce714567 594 fe_mul__distinct(x, v, a);
wolfSSL 7:481bce714567 595 fe_mul__distinct(r, x, i);
wolfSSL 7:481bce714567 596 }
wolfSSL 7:481bce714567 597
wolfSSL 7:481bce714567 598 #endif /* HAVE_CURVE25519 or HAVE_ED25519 */
wolfSSL 7:481bce714567 599 #endif /* CURVED25519_SMALL */
wolfSSL 7:481bce714567 600