wolf SSL / wolfSSL-TLS13-Beta

wolfSSL 3.11.1 for TLS1.3 beta

Fork of wolfSSL by wolf SSL

wolfcrypt/src/fe_low_mem.c@13:80fb167dafdf, 2017-05-30 (annotated)

Committer:
wolfSSL
Date:
Tue May 30 06:16:19 2017 +0000
Revision:
13:80fb167dafdf
Parent:
11:cee25a834751 
wolfSSL 3.11.1: TLS1.3 Beta

Who changed what in which revision?

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