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@4:1b0d80432c79, 2016-04-28 (annotated)

Committer:
wolfSSL
Date:
Thu Apr 28 00:57:21 2016 +0000
Revision:
4:1b0d80432c79
wolfSSL 3.9.0

Who changed what in which revision?

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