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@13:f67a6c6013ca, 2017-08-22 (annotated)

Committer:
wolfSSL
Date:
Tue Aug 22 10:48:22 2017 +0000
Revision:
13:f67a6c6013ca
wolfSSL3.12.0 with TLS1.3

Who changed what in which revision?

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