fe_low_mem.c

00001 /* fe_low_mem.c
00002  *
00003  * Copyright (C) 2006-2016 wolfSSL Inc.
00004  *
00005  * This file is part of wolfSSL.
00006  *
00007  * wolfSSL is free software; you can redistribute it and/or modify
00008  * it under the terms of the GNU General Public License as published by
00009  * the Free Software Foundation; either version 2 of the License, or
00010  * (at your option) any later version.
00011  *
00012  * wolfSSL is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015  * GNU General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU General Public License
00018  * along with this program; if not, write to the Free Software
00019  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335, USA
00020  */
00021 
00022 
00023 /* Based from Daniel Beer's public domain word. */
00024 
00025 #ifdef HAVE_CONFIG_H
00026     #include <config.h>
00027 #endif
00028 
00029 #include <wolfssl/wolfcrypt/settings.h>
00030 
00031 #if defined(CURVED25519_SMALL) /* use slower code that takes less memory */
00032 #if defined(HAVE_ED25519) || defined(HAVE_CURVE25519)
00033 
00034 #include <wolfssl/wolfcrypt/fe_operations.h>
00035 
00036 #ifdef NO_INLINE
00037     #include <wolfssl/wolfcrypt/misc.h>
00038 #else
00039     #define WOLFSSL_MISC_INCLUDED
00040     #include <wolfcrypt/src/misc.c>
00041 #endif
00042 
00043 
00044 void fprime_copy(byte *x, const byte *a)
00045 {
00046     int i;
00047     for (i = 0; i < F25519_SIZE; i++)
00048         x[i] = a[i];
00049 }
00050 
00051 
00052 void fe_copy(fe x, const fe a)
00053 {
00054     int i;
00055     for (i = 0; i < F25519_SIZE; i++)
00056         x[i] = a[i];
00057 }
00058 
00059 
00060 /* Double an X-coordinate */
00061 static void xc_double(byte *x3, byte *z3,
00062               const byte *x1, const byte *z1)
00063 {
00064     /* Explicit formulas database: dbl-1987-m
00065      *
00066      * source 1987 Montgomery "Speeding the Pollard and elliptic
00067      *   curve methods of factorization", page 261, fourth display
00068      * compute X3 = (X1^2-Z1^2)^2
00069      * compute Z3 = 4 X1 Z1 (X1^2 + a X1 Z1 + Z1^2)
00070      */
00071     byte x1sq[F25519_SIZE];
00072     byte z1sq[F25519_SIZE];
00073     byte x1z1[F25519_SIZE];
00074     byte a[F25519_SIZE];
00075 
00076     fe_mul__distinct(x1sq, x1, x1);
00077     fe_mul__distinct(z1sq, z1, z1);
00078     fe_mul__distinct(x1z1, x1, z1);
00079 
00080     fe_sub(a, x1sq, z1sq);
00081     fe_mul__distinct(x3, a, a);
00082 
00083     fe_mul_c(a, x1z1, 486662);
00084     fe_add(a, x1sq, a);
00085     fe_add(a, z1sq, a);
00086     fe_mul__distinct(x1sq, x1z1, a);
00087     fe_mul_c(z3, x1sq, 4);
00088 }
00089 
00090 
00091 /* Differential addition */
00092 static void xc_diffadd(byte *x5, byte *z5,
00093                const byte *x1, const byte *z1,
00094                const byte *x2, const byte *z2,
00095                const byte *x3, const byte *z3)
00096 {
00097     /* Explicit formulas database: dbl-1987-m3
00098      *
00099      * source 1987 Montgomery "Speeding the Pollard and elliptic curve
00100      *   methods of factorization", page 261, fifth display, plus
00101      *   common-subexpression elimination
00102      * compute A = X2+Z2
00103      * compute B = X2-Z2
00104      * compute C = X3+Z3
00105      * compute D = X3-Z3
00106      * compute DA = D A
00107      * compute CB = C B
00108      * compute X5 = Z1(DA+CB)^2
00109      * compute Z5 = X1(DA-CB)^2
00110      */
00111     byte da[F25519_SIZE];
00112     byte cb[F25519_SIZE];
00113     byte a[F25519_SIZE];
00114     byte b[F25519_SIZE];
00115 
00116     fe_add(a, x2, z2);
00117     fe_sub(b, x3, z3); /* D */
00118     fe_mul__distinct(da, a, b);
00119 
00120     fe_sub(b, x2, z2);
00121     fe_add(a, x3, z3); /* C */
00122     fe_mul__distinct(cb, a, b);
00123 
00124     fe_add(a, da, cb);
00125     fe_mul__distinct(b, a, a);
00126     fe_mul__distinct(x5, z1, b);
00127 
00128     fe_sub(a, da, cb);
00129     fe_mul__distinct(b, a, a);
00130     fe_mul__distinct(z5, x1, b);
00131 }
00132 
00133 #ifndef FREESCALE_LTC_ECC
00134 int curve25519(byte *result, byte *e, byte *q)
00135 {
00136     /* Current point: P_m */
00137     byte xm[F25519_SIZE];
00138     byte zm[F25519_SIZE] = {1};
00139 
00140     /* Predecessor: P_(m-1) */
00141     byte xm1[F25519_SIZE] = {1};
00142     byte zm1[F25519_SIZE] = {0};
00143 
00144     int i;
00145 
00146     /* Note: bit 254 is assumed to be 1 */
00147     fe_copy(xm, q);
00148 
00149     for (i = 253; i >= 0; i--) {
00150         const int bit = (e[i >> 3] >> (i & 7)) & 1;
00151         byte xms[F25519_SIZE];
00152         byte zms[F25519_SIZE];
00153 
00154         /* From P_m and P_(m-1), compute P_(2m) and P_(2m-1) */
00155         xc_diffadd(xm1, zm1, q, f25519_one, xm, zm, xm1, zm1);
00156         xc_double(xm, zm, xm, zm);
00157 
00158         /* Compute P_(2m+1) */
00159         xc_diffadd(xms, zms, xm1, zm1, xm, zm, q, f25519_one);
00160 
00161         /* Select:
00162          *   bit = 1 --> (P_(2m+1), P_(2m))
00163          *   bit = 0 --> (P_(2m), P_(2m-1))
00164          */
00165         fe_select(xm1, xm1, xm, bit);
00166         fe_select(zm1, zm1, zm, bit);
00167         fe_select(xm, xm, xms, bit);
00168         fe_select(zm, zm, zms, bit);
00169     }
00170 
00171     /* Freeze out of projective coordinates */
00172     fe_inv__distinct(zm1, zm);
00173     fe_mul__distinct(result, zm1, xm);
00174     fe_normalize(result);
00175     return 0;
00176 }
00177 #endif /* !FREESCALE_LTC_ECC */
00178 
00179 static void raw_add(byte *x, const byte *p)
00180 {
00181     word16 c = 0;
00182     int i;
00183 
00184     for (i = 0; i < F25519_SIZE; i++) {
00185         c += ((word16)x[i]) + ((word16)p[i]);
00186         x[i] = (byte)c;
00187         c >>= 8;
00188     }
00189 }
00190 
00191 
00192 static void raw_try_sub(byte *x, const byte *p)
00193 {
00194     byte minusp[F25519_SIZE];
00195     word16 c = 0;
00196     int i;
00197 
00198     for (i = 0; i < F25519_SIZE; i++) {
00199         c = ((word16)x[i]) - ((word16)p[i]) - c;
00200         minusp[i] = (byte)c;
00201         c = (c >> 8) & 1;
00202     }
00203 
00204     fprime_select(x, minusp, x, (byte)c);
00205 }
00206 
00207 
00208 static int prime_msb(const byte *p)
00209 {
00210     int i;
00211     byte x;
00212     int shift = 1;
00213     int z     = F25519_SIZE - 1;
00214 
00215    /*
00216        Test for any hot bits.
00217        As soon as one instance is encountered set shift to 0.
00218     */
00219     for (i = F25519_SIZE - 1; i >= 0; i--) {
00220         shift &= ((shift ^ ((-p[i] | p[i]) >> 7)) & 1);
00221         z -= shift;
00222     }
00223     x = p[z];
00224     z <<= 3;
00225     shift = 1;
00226     for (i = 0; i < 8; i++) {
00227         shift &= ((-(x >> i) | (x >> i)) >> (7 - i) & 1);
00228         z += shift;
00229     }
00230 
00231     return z - 1;
00232 }
00233 
00234 
00235 void fprime_select(byte *dst, const byte *zero, const byte *one, byte condition)
00236 {
00237     const byte mask = -condition;
00238     int i;
00239 
00240     for (i = 0; i < F25519_SIZE; i++)
00241         dst[i] = zero[i] ^ (mask & (one[i] ^ zero[i]));
00242 }
00243 
00244 
00245 void fprime_add(byte *r, const byte *a, const byte *modulus)
00246 {
00247     raw_add(r, a);
00248     raw_try_sub(r, modulus);
00249 }
00250 
00251 
00252 void fprime_sub(byte *r, const byte *a, const byte *modulus)
00253 {
00254     raw_add(r, modulus);
00255     raw_try_sub(r, a);
00256     raw_try_sub(r, modulus);
00257 }
00258 
00259 
00260 void fprime_mul(byte *r, const byte *a, const byte *b,
00261         const byte *modulus)
00262 {
00263     word16 c = 0;
00264     int i,j;
00265 
00266     XMEMSET(r, 0, F25519_SIZE);
00267 
00268     for (i = prime_msb(modulus); i >= 0; i--) {
00269         const byte bit = (b[i >> 3] >> (i & 7)) & 1;
00270         byte plusa[F25519_SIZE];
00271 
00272         for (j = 0; j < F25519_SIZE; j++) {
00273             c |= ((word16)r[j]) << 1;
00274             r[j] = (byte)c;
00275             c >>= 8;
00276         }
00277         raw_try_sub(r, modulus);
00278 
00279         fprime_copy(plusa, r);
00280         fprime_add(plusa, a, modulus);
00281 
00282         fprime_select(r, r, plusa, bit);
00283     }
00284 }
00285 
00286 
00287 void fe_load(byte *x, word32 c)
00288 {
00289     word32 i;
00290 
00291     for (i = 0; i < sizeof(c); i++) {
00292         x[i] = c;
00293         c >>= 8;
00294     }
00295 
00296     for (; i < F25519_SIZE; i++)
00297         x[i] = 0;
00298 }
00299 
00300 
00301 void fe_normalize(byte *x)
00302 {
00303     byte minusp[F25519_SIZE];
00304     word16 c;
00305     int i;
00306 
00307     /* Reduce using 2^255 = 19 mod p */
00308     c = (x[31] >> 7) * 19;
00309     x[31] &= 127;
00310 
00311     for (i = 0; i < F25519_SIZE; i++) {
00312         c += x[i];
00313         x[i] = (byte)c;
00314         c >>= 8;
00315     }
00316 
00317     /* The number is now less than 2^255 + 18, and therefore less than
00318      * 2p. Try subtracting p, and conditionally load the subtracted
00319      * value if underflow did not occur.
00320      */
00321     c = 19;
00322 
00323     for (i = 0; i + 1 < F25519_SIZE; i++) {
00324         c += x[i];
00325         minusp[i] = (byte)c;
00326         c >>= 8;
00327     }
00328 
00329     c += ((word16)x[i]) - 128;
00330     minusp[31] = (byte)c;
00331 
00332     /* Load x-p if no underflow */
00333     fe_select(x, minusp, x, (c >> 15) & 1);
00334 }
00335 
00336 
00337 void fe_select(byte *dst,
00338            const byte *zero, const byte *one,
00339            byte condition)
00340 {
00341     const byte mask = -condition;
00342     int i;
00343 
00344     for (i = 0; i < F25519_SIZE; i++)
00345         dst[i] = zero[i] ^ (mask & (one[i] ^ zero[i]));
00346 }
00347 
00348 
00349 void fe_add(fe r, const fe a, const fe b)
00350 {
00351     word16 c = 0;
00352     int i;
00353 
00354     /* Add */
00355     for (i = 0; i < F25519_SIZE; i++) {
00356         c >>= 8;
00357         c += ((word16)a[i]) + ((word16)b[i]);
00358         r[i] = (byte)c;
00359     }
00360 
00361     /* Reduce with 2^255 = 19 mod p */
00362     r[31] &= 127;
00363     c = (c >> 7) * 19;
00364 
00365     for (i = 0; i < F25519_SIZE; i++) {
00366         c += r[i];
00367         r[i] = (byte)c;
00368         c >>= 8;
00369     }
00370 }
00371 
00372 
00373 void fe_sub(fe r, const fe a, const fe b)
00374 {
00375     word32 c = 0;
00376     int i;
00377 
00378     /* Calculate a + 2p - b, to avoid underflow */
00379     c = 218;
00380     for (i = 0; i + 1 < F25519_SIZE; i++) {
00381         c += 65280 + ((word32)a[i]) - ((word32)b[i]);
00382         r[i] = c;
00383         c >>= 8;
00384     }
00385 
00386     c += ((word32)a[31]) - ((word32)b[31]);
00387     r[31] = c & 127;
00388     c = (c >> 7) * 19;
00389 
00390     for (i = 0; i < F25519_SIZE; i++) {
00391         c += r[i];
00392         r[i] = c;
00393         c >>= 8;
00394     }
00395 }
00396 
00397 
00398 void fe_neg(fe r, const fe a)
00399 {
00400     word32 c = 0;
00401     int i;
00402 
00403     /* Calculate 2p - a, to avoid underflow */
00404     c = 218;
00405     for (i = 0; i + 1 < F25519_SIZE; i++) {
00406         c += 65280 - ((word32)a[i]);
00407         r[i] = c;
00408         c >>= 8;
00409     }
00410 
00411     c -= ((word32)a[31]);
00412     r[31] = c & 127;
00413     c = (c >> 7) * 19;
00414 
00415     for (i = 0; i < F25519_SIZE; i++) {
00416         c += r[i];
00417         r[i] = c;
00418         c >>= 8;
00419     }
00420 }
00421 
00422 
00423 void fe_mul__distinct(byte *r, const byte *a, const byte *b)
00424 {
00425     word32 c = 0;
00426     int i;
00427 
00428     for (i = 0; i < F25519_SIZE; i++) {
00429         int j;
00430 
00431         c >>= 8;
00432         for (j = 0; j <= i; j++)
00433             c += ((word32)a[j]) * ((word32)b[i - j]);
00434 
00435         for (; j < F25519_SIZE; j++)
00436             c += ((word32)a[j]) *
00437                  ((word32)b[i + F25519_SIZE - j]) * 38;
00438 
00439         r[i] = c;
00440     }
00441 
00442     r[31] &= 127;
00443     c = (c >> 7) * 19;
00444 
00445     for (i = 0; i < F25519_SIZE; i++) {
00446         c += r[i];
00447         r[i] = c;
00448         c >>= 8;
00449     }
00450 }
00451 
00452 
00453 void fe_mul(fe r, const fe a, const fe b)
00454 {
00455     byte tmp[F25519_SIZE];
00456 
00457     fe_mul__distinct(tmp, a, b);
00458     fe_copy(r, tmp);
00459 }
00460 
00461 
00462 void fe_mul_c(byte *r, const byte *a, word32 b)
00463 {
00464     word32 c = 0;
00465     int i;
00466 
00467     for (i = 0; i < F25519_SIZE; i++) {
00468         c >>= 8;
00469         c += b * ((word32)a[i]);
00470         r[i] = c;
00471     }
00472 
00473     r[31] &= 127;
00474     c >>= 7;
00475     c *= 19;
00476 
00477     for (i = 0; i < F25519_SIZE; i++) {
00478         c += r[i];
00479         r[i] = c;
00480         c >>= 8;
00481     }
00482 }
00483 
00484 
00485 void fe_inv__distinct(byte *r, const byte *x)
00486 {
00487     byte s[F25519_SIZE];
00488     int i;
00489 
00490     /* This is a prime field, so by Fermat's little theorem:
00491      *
00492      *     x^(p-1) = 1 mod p
00493      *
00494      * Therefore, raise to (p-2) = 2^255-21 to get a multiplicative
00495      * inverse.
00496      *
00497      * This is a 255-bit binary number with the digits:
00498      *
00499      *     11111111... 01011
00500      *
00501      * We compute the result by the usual binary chain, but
00502      * alternate between keeping the accumulator in r and s, so as
00503      * to avoid copying temporaries.
00504      */
00505 
00506     /* 1 1 */
00507     fe_mul__distinct(s, x, x);
00508     fe_mul__distinct(r, s, x);
00509 
00510     /* 1 x 248 */
00511     for (i = 0; i < 248; i++) {
00512         fe_mul__distinct(s, r, r);
00513         fe_mul__distinct(r, s, x);
00514     }
00515 
00516     /* 0 */
00517     fe_mul__distinct(s, r, r);
00518 
00519     /* 1 */
00520     fe_mul__distinct(r, s, s);
00521     fe_mul__distinct(s, r, x);
00522 
00523     /* 0 */
00524     fe_mul__distinct(r, s, s);
00525 
00526     /* 1 */
00527     fe_mul__distinct(s, r, r);
00528     fe_mul__distinct(r, s, x);
00529 
00530     /* 1 */
00531     fe_mul__distinct(s, r, r);
00532     fe_mul__distinct(r, s, x);
00533 }
00534 
00535 
00536 void fe_invert(fe r, const fe x)
00537 {
00538     byte tmp[F25519_SIZE];
00539 
00540     fe_inv__distinct(tmp, x);
00541     fe_copy(r, tmp);
00542 }
00543 
00544 
00545 /* Raise x to the power of (p-5)/8 = 2^252-3, using s for temporary
00546  * storage.
00547  */
00548 static void exp2523(byte *r, const byte *x, byte *s)
00549 {
00550     int i;
00551 
00552     /* This number is a 252-bit number with the binary expansion:
00553      *
00554      *     111111... 01
00555      */
00556 
00557     /* 1 1 */
00558     fe_mul__distinct(r, x, x);
00559     fe_mul__distinct(s, r, x);
00560 
00561     /* 1 x 248 */
00562     for (i = 0; i < 248; i++) {
00563         fe_mul__distinct(r, s, s);
00564         fe_mul__distinct(s, r, x);
00565     }
00566 
00567     /* 0 */
00568     fe_mul__distinct(r, s, s);
00569 
00570     /* 1 */
00571     fe_mul__distinct(s, r, r);
00572     fe_mul__distinct(r, s, x);
00573 }
00574 
00575 
00576 void fe_sqrt(byte *r, const byte *a)
00577 {
00578     byte v[F25519_SIZE];
00579     byte i[F25519_SIZE];
00580     byte x[F25519_SIZE];
00581     byte y[F25519_SIZE];
00582 
00583     /* v = (2a)^((p-5)/8) [x = 2a] */
00584     fe_mul_c(x, a, 2);
00585     exp2523(v, x, y);
00586 
00587     /* i = 2av^2 - 1 */
00588     fe_mul__distinct(y, v, v);
00589     fe_mul__distinct(i, x, y);
00590     fe_load(y, 1);
00591     fe_sub(i, i, y);
00592 
00593     /* r = avi */
00594     fe_mul__distinct(x, v, a);
00595     fe_mul__distinct(r, x, i);
00596 }
00597 
00598 #endif /* HAVE_CURVE25519 or HAVE_ED25519 */
00599 #endif /* CURVED25519_SMALL */
00600