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@17:a5f916481144, 2020-06-05 (annotated)

Committer:
wolfSSL
Date:
Fri Jun 05 00:11:07 2020 +0000
Revision:
17:a5f916481144
Parent:
16:8e0d178b1d1e 
wolfSSL 4.4.0

Who changed what in which revision?

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