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@0:d92f9d21154c, 2015-06-26 (annotated)

Committer:
wolfSSL
Date:
Fri Jun 26 00:39:20 2015 +0000
Revision:
0:d92f9d21154c
wolfSSL 3.6.0

Who changed what in which revision?

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