ge_low_mem.c

00001 /* ge_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 work. */
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)
00033 
00034 #include <wolfssl/wolfcrypt/ge_operations.h>
00035 #include <wolfssl/wolfcrypt/error-crypt.h>
00036 #ifdef NO_INLINE
00037     #include <wolfssl/wolfcrypt/misc.h>
00038 #else
00039     #include <wolfcrypt/src/misc.c>
00040 #endif
00041 
00042 void ed25519_smult(ge_p3 *r, const ge_p3 *a, const byte *e);
00043 void ed25519_add(ge_p3 *r, const ge_p3 *a, const ge_p3 *b);
00044 void ed25519_double(ge_p3 *r, const ge_p3 *a);
00045 
00046 
00047 static const byte ed25519_order[F25519_SIZE] = {
00048     0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58,
00049     0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14,
00050     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
00051     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10
00052 };
00053 
00054 /*Arithmetic modulo the group order m = 2^252 +
00055  27742317777372353535851937790883648493 =
00056  7237005577332262213973186563042994240857116359379907606001950938285454250989 */
00057 
00058 static const word32 m[32] = {
00059     0xED,0xD3,0xF5,0x5C,0x1A,0x63,0x12,0x58,0xD6,0x9C,0xF7,0xA2,0xDE,0xF9,
00060     0xDE,0x14,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
00061     0x00,0x00,0x00,0x10
00062 };
00063 
00064 static const word32 mu[33] = {
00065     0x1B,0x13,0x2C,0x0A,0xA3,0xE5,0x9C,0xED,0xA7,0x29,0x63,0x08,0x5D,0x21,
00066     0x06,0x21,0xEB,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
00067     0xFF,0xFF,0xFF,0xFF,0x0F
00068 };
00069 
00070 
00071 int ge_compress_key(byte* out, const byte* xIn, const byte* yIn,
00072                         word32 keySz)
00073 {
00074     byte tmp[F25519_SIZE];
00075     byte parity;
00076     byte pt[32];
00077     int     i;
00078 
00079     fe_copy(tmp, xIn);
00080     parity = (tmp[0] & 1) << 7;
00081 
00082     fe_copy(pt, yIn);
00083     pt[31] |= parity;
00084 
00085     for(i = 0; i < 32; i++) {
00086         out[32-i-1] = pt[i];
00087     }
00088     (void)keySz;
00089     return 0;
00090 }
00091 
00092 
00093 static word32 lt(word32 a,word32 b) /* 16-bit inputs */
00094 {
00095   unsigned int x = a;
00096   x -= (unsigned int) b; /* 0..65535: no; 4294901761..4294967295: yes */
00097   x >>= 31; /* 0: no; 1: yes */
00098   return x;
00099 }
00100 
00101 
00102 /* Reduce coefficients of r before calling reduce_add_sub */
00103 static void reduce_add_sub(word32 *r)
00104 {
00105   word32 pb = 0;
00106   word32 b;
00107   word32 mask;
00108   int i;
00109   unsigned char t[32];
00110 
00111   for(i=0;i<32;i++)
00112   {
00113     pb += m[i];
00114     b = lt(r[i],pb);
00115     t[i] = r[i]-pb+(b<<8);
00116     pb = b;
00117   }
00118   mask = b - 1;
00119   for(i=0;i<32;i++)
00120     r[i] ^= mask & (r[i] ^ t[i]);
00121 }
00122 
00123 
00124 /* Reduce coefficients of x before calling barrett_reduce */
00125 static void barrett_reduce(word32* r, word32 x[64])
00126 {
00127   /* See HAC, Alg. 14.42 */
00128   int i,j;
00129   word32 q2[66];
00130   word32 *q3 = q2 + 33;
00131   word32 r1[33];
00132   word32 r2[33];
00133   word32 carry;
00134   word32 pb = 0;
00135   word32 b;
00136 
00137   for (i = 0;i < 66;++i) q2[i] = 0;
00138   for (i = 0;i < 33;++i) r2[i] = 0;
00139 
00140   for(i=0;i<33;i++)
00141     for(j=0;j<33;j++)
00142       if(i+j >= 31) q2[i+j] += mu[i]*x[j+31];
00143   carry = q2[31] >> 8;
00144   q2[32] += carry;
00145   carry = q2[32] >> 8;
00146   q2[33] += carry;
00147 
00148   for(i=0;i<33;i++)r1[i] = x[i];
00149   for(i=0;i<32;i++)
00150     for(j=0;j<33;j++)
00151       if(i+j < 33) r2[i+j] += m[i]*q3[j];
00152 
00153   for(i=0;i<32;i++)
00154   {
00155     carry = r2[i] >> 8;
00156     r2[i+1] += carry;
00157     r2[i] &= 0xff;
00158   }
00159 
00160   for(i=0;i<32;i++)
00161   {
00162     pb += r2[i];
00163     b = lt(r1[i],pb);
00164     r[i] = r1[i]-pb+(b<<8);
00165     pb = b;
00166   }
00167 
00168   /* XXX: Can it really happen that r<0?, See HAC, Alg 14.42, Step 3
00169    * r is an unsigned type.
00170    * If so: Handle  it here!
00171    */
00172 
00173   reduce_add_sub(r);
00174   reduce_add_sub(r);
00175 }
00176 
00177 
00178 void sc_reduce(unsigned char x[64])
00179 {
00180   int i;
00181   word32 t[64];
00182   word32 r[32];
00183   for(i=0;i<64;i++) t[i] = x[i];
00184   barrett_reduce(r, t);
00185   for(i=0;i<32;i++) x[i] = (r[i] & 0xFF);
00186 }
00187 
00188 
00189 void sc_muladd(byte* out, const byte* a, const byte* b, const byte* c)
00190 {
00191 
00192     byte s[32];
00193     byte e[64];
00194 
00195     XMEMSET(e, 0, sizeof(e));
00196     XMEMCPY(e, b, 32);
00197 
00198     /* Obtain e */
00199     sc_reduce(e);
00200 
00201     /* Compute s = ze + k */
00202     fprime_mul(s, a, e, ed25519_order);
00203     fprime_add(s, c, ed25519_order);
00204 
00205     XMEMCPY(out, s, 32);
00206 }
00207 
00208 
00209 /* Base point is (numbers wrapped):
00210  *
00211  *     x = 151122213495354007725011514095885315114
00212  *         54012693041857206046113283949847762202
00213  *     y = 463168356949264781694283940034751631413
00214  *         07993866256225615783033603165251855960
00215  *
00216  * y is derived by transforming the original Montgomery base (u=9). x
00217  * is the corresponding positive coordinate for the new curve equation.
00218  * t is x*y.
00219  */
00220 const ge_p3 ed25519_base = {
00221     {
00222         0x1a, 0xd5, 0x25, 0x8f, 0x60, 0x2d, 0x56, 0xc9,
00223         0xb2, 0xa7, 0x25, 0x95, 0x60, 0xc7, 0x2c, 0x69,
00224         0x5c, 0xdc, 0xd6, 0xfd, 0x31, 0xe2, 0xa4, 0xc0,
00225         0xfe, 0x53, 0x6e, 0xcd, 0xd3, 0x36, 0x69, 0x21
00226     },
00227     {
00228         0x58, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
00229         0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
00230         0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
00231         0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66
00232     },
00233     {1, 0},
00234     {
00235         0xa3, 0xdd, 0xb7, 0xa5, 0xb3, 0x8a, 0xde, 0x6d,
00236         0xf5, 0x52, 0x51, 0x77, 0x80, 0x9f, 0xf0, 0x20,
00237         0x7d, 0xe3, 0xab, 0x64, 0x8e, 0x4e, 0xea, 0x66,
00238         0x65, 0x76, 0x8b, 0xd7, 0x0f, 0x5f, 0x87, 0x67
00239     },
00240 
00241 };
00242 
00243 
00244 const ge_p3 ed25519_neutral = {
00245     {0},
00246     {1, 0},
00247     {1, 0},
00248     {0},
00249 
00250 };
00251 
00252 
00253 static const byte ed25519_d[F25519_SIZE] = {
00254     0xa3, 0x78, 0x59, 0x13, 0xca, 0x4d, 0xeb, 0x75,
00255     0xab, 0xd8, 0x41, 0x41, 0x4d, 0x0a, 0x70, 0x00,
00256     0x98, 0xe8, 0x79, 0x77, 0x79, 0x40, 0xc7, 0x8c,
00257     0x73, 0xfe, 0x6f, 0x2b, 0xee, 0x6c, 0x03, 0x52
00258 };
00259 
00260 
00261 /* k = 2d */
00262 static const byte ed25519_k[F25519_SIZE] = {
00263     0x59, 0xf1, 0xb2, 0x26, 0x94, 0x9b, 0xd6, 0xeb,
00264     0x56, 0xb1, 0x83, 0x82, 0x9a, 0x14, 0xe0, 0x00,
00265     0x30, 0xd1, 0xf3, 0xee, 0xf2, 0x80, 0x8e, 0x19,
00266     0xe7, 0xfc, 0xdf, 0x56, 0xdc, 0xd9, 0x06, 0x24
00267 };
00268 
00269 
00270 void ed25519_add(ge_p3 *r,
00271          const ge_p3 *p1, const ge_p3 *p2)
00272 {
00273     /* Explicit formulas database: add-2008-hwcd-3
00274      *
00275      * source 2008 Hisil--Wong--Carter--Dawson,
00276      *     http://eprint.iacr.org/2008/522, Section 3.1
00277      * appliesto extended-1
00278      * parameter k
00279      * assume k = 2 d
00280      * compute A = (Y1-X1)(Y2-X2)
00281      * compute B = (Y1+X1)(Y2+X2)
00282      * compute C = T1 k T2
00283      * compute D = Z1 2 Z2
00284      * compute E = B - A
00285      * compute F = D - C
00286      * compute G = D + C
00287      * compute H = B + A
00288      * compute X3 = E F
00289      * compute Y3 = G H
00290      * compute T3 = E H
00291      * compute Z3 = F G
00292      */
00293     byte a[F25519_SIZE];
00294     byte b[F25519_SIZE];
00295     byte c[F25519_SIZE];
00296     byte d[F25519_SIZE];
00297     byte e[F25519_SIZE];
00298     byte f[F25519_SIZE];
00299     byte g[F25519_SIZE];
00300     byte h[F25519_SIZE];
00301 
00302     /* A = (Y1-X1)(Y2-X2) */
00303     fe_sub(c, p1->Y, p1->X);
00304     fe_sub(d, p2->Y, p2->X);
00305     fe_mul__distinct(a, c, d);
00306 
00307     /* B = (Y1+X1)(Y2+X2) */
00308     fe_add(c, p1->Y, p1->X);
00309     fe_add(d, p2->Y, p2->X);
00310     fe_mul__distinct(b, c, d);
00311 
00312     /* C = T1 k T2 */
00313     fe_mul__distinct(d, p1->T, p2->T);
00314     fe_mul__distinct(c, d, ed25519_k);
00315 
00316     /* D = Z1 2 Z2 */
00317     fe_mul__distinct(d, p1->Z, p2->Z);
00318     fe_add(d, d, d);
00319 
00320     /* E = B - A */
00321     fe_sub(e, b, a);
00322 
00323     /* F = D - C */
00324     fe_sub(f, d, c);
00325 
00326     /* G = D + C */
00327     fe_add(g, d, c);
00328 
00329     /* H = B + A */
00330     fe_add(h, b, a);
00331 
00332     /* X3 = E F */
00333     fe_mul__distinct(r->X, e, f);
00334 
00335     /* Y3 = G H */
00336     fe_mul__distinct(r->Y, g, h);
00337 
00338     /* T3 = E H */
00339     fe_mul__distinct(r->T, e, h);
00340 
00341     /* Z3 = F G */
00342     fe_mul__distinct(r->Z, f, g);
00343 }
00344 
00345 
00346 void ed25519_double(ge_p3 *r, const ge_p3 *p)
00347 {
00348     /* Explicit formulas database: dbl-2008-hwcd
00349      *
00350      * source 2008 Hisil--Wong--Carter--Dawson,
00351      *     http://eprint.iacr.org/2008/522, Section 3.3
00352      * compute A = X1^2
00353      * compute B = Y1^2
00354      * compute C = 2 Z1^2
00355      * compute D = a A
00356      * compute E = (X1+Y1)^2-A-B
00357      * compute G = D + B
00358      * compute F = G - C
00359      * compute H = D - B
00360      * compute X3 = E F
00361      * compute Y3 = G H
00362      * compute T3 = E H
00363      * compute Z3 = F G
00364      */
00365     byte a[F25519_SIZE];
00366     byte b[F25519_SIZE];
00367     byte c[F25519_SIZE];
00368     byte e[F25519_SIZE];
00369     byte f[F25519_SIZE];
00370     byte g[F25519_SIZE];
00371     byte h[F25519_SIZE];
00372 
00373     /* A = X1^2 */
00374     fe_mul__distinct(a, p->X, p->X);
00375 
00376     /* B = Y1^2 */
00377     fe_mul__distinct(b, p->Y, p->Y);
00378 
00379     /* C = 2 Z1^2 */
00380     fe_mul__distinct(c, p->Z, p->Z);
00381     fe_add(c, c, c);
00382 
00383     /* D = a A (alter sign) */
00384     /* E = (X1+Y1)^2-A-B */
00385     fe_add(f, p->X, p->Y);
00386     fe_mul__distinct(e, f, f);
00387     fe_sub(e, e, a);
00388     fe_sub(e, e, b);
00389 
00390     /* G = D + B */
00391     fe_sub(g, b, a);
00392 
00393     /* F = G - C */
00394     fe_sub(f, g, c);
00395 
00396     /* H = D - B */
00397     fe_neg(h, b);
00398     fe_sub(h, h, a);
00399 
00400     /* X3 = E F */
00401     fe_mul__distinct(r->X, e, f);
00402 
00403     /* Y3 = G H */
00404     fe_mul__distinct(r->Y, g, h);
00405 
00406     /* T3 = E H */
00407     fe_mul__distinct(r->T, e, h);
00408 
00409     /* Z3 = F G */
00410     fe_mul__distinct(r->Z, f, g);
00411 }
00412 
00413 
00414 void ed25519_smult(ge_p3 *r_out, const ge_p3 *p, const byte *e)
00415 {
00416     ge_p3 r;
00417     int   i;
00418 
00419     XMEMCPY(&r, &ed25519_neutral, sizeof(r));
00420 
00421     for (i = 255; i >= 0; i--) {
00422         const byte bit = (e[i >> 3] >> (i & 7)) & 1;
00423         ge_p3 s;
00424 
00425         ed25519_double(&r, &r);
00426         ed25519_add(&s, &r, p);
00427 
00428         fe_select(r.X, r.X, s.X, bit);
00429         fe_select(r.Y, r.Y, s.Y, bit);
00430         fe_select(r.Z, r.Z, s.Z, bit);
00431         fe_select(r.T, r.T, s.T, bit);
00432     }
00433     XMEMCPY(r_out, &r, sizeof(r));
00434 }
00435 
00436 
00437 void ge_scalarmult_base(ge_p3 *R,const unsigned char *nonce)
00438 {
00439     ed25519_smult(R, &ed25519_base, nonce);
00440 }
00441 
00442 
00443 /* pack the point h into array s */
00444 void ge_p3_tobytes(unsigned char *s,const ge_p3 *h)
00445 {
00446     byte x[F25519_SIZE];
00447     byte y[F25519_SIZE];
00448     byte z1[F25519_SIZE];
00449     byte parity;
00450 
00451     fe_inv__distinct(z1, h->Z);
00452     fe_mul__distinct(x, h->X, z1);
00453     fe_mul__distinct(y, h->Y, z1);
00454 
00455     fe_normalize(x);
00456     fe_normalize(y);
00457 
00458     parity = (x[0] & 1) << 7;
00459     fe_copy(s, y);
00460     fe_normalize(s);
00461     s[31] |= parity;
00462 }
00463 
00464 
00465 /* pack the point h into array s */
00466 void ge_tobytes(unsigned char *s,const ge_p2 *h)
00467 {
00468     byte x[F25519_SIZE];
00469     byte y[F25519_SIZE];
00470     byte z1[F25519_SIZE];
00471     byte parity;
00472 
00473     fe_inv__distinct(z1, h->Z);
00474     fe_mul__distinct(x, h->X, z1);
00475     fe_mul__distinct(y, h->Y, z1);
00476 
00477     fe_normalize(x);
00478     fe_normalize(y);
00479 
00480     parity = (x[0] & 1) << 7;
00481     fe_copy(s, y);
00482     fe_normalize(s);
00483     s[31] |= parity;
00484 }
00485 
00486 
00487 /*
00488    Test if the public key can be uncompressed and negate it (-X,Y,Z,-T)
00489    return 0 on success
00490  */
00491 int ge_frombytes_negate_vartime(ge_p3 *p,const unsigned char *s)
00492 {
00493 
00494     byte parity;
00495     byte x[F25519_SIZE];
00496     byte y[F25519_SIZE];
00497     byte a[F25519_SIZE];
00498     byte b[F25519_SIZE];
00499     byte c[F25519_SIZE];
00500     int ret = 0;
00501 
00502     /* unpack the key s */
00503     parity = s[31] >> 7;
00504     fe_copy(y, s);
00505     y[31] &= 127;
00506 
00507     fe_mul__distinct(c, y, y);
00508     fe_mul__distinct(b, c, ed25519_d);
00509     fe_add(a, b, f25519_one);
00510     fe_inv__distinct(b, a);
00511     fe_sub(a, c, f25519_one);
00512     fe_mul__distinct(c, a, b);
00513     fe_sqrt(a, c);
00514     fe_neg(b, a);
00515     fe_select(x, a, b, (a[0] ^ parity) & 1);
00516 
00517     /* test that x^2 is equal to c */
00518     fe_mul__distinct(a, x, x);
00519     fe_normalize(a);
00520     fe_normalize(c);
00521     ret |= ConstantCompare(a, c, F25519_SIZE);
00522 
00523     /* project the key s onto p */
00524     fe_copy(p->X, x);
00525     fe_copy(p->Y, y);
00526     fe_load(p->Z, 1);
00527     fe_mul__distinct(p->T, x, y);
00528 
00529     /* negate, the point becomes (-X,Y,Z,-T) */
00530     fe_neg(p->X,p->X);
00531     fe_neg(p->T,p->T);
00532 
00533     return ret;
00534 }
00535 
00536 
00537 int ge_double_scalarmult_vartime(ge_p2* R, const unsigned char *h,
00538                                  const ge_p3 *inA,const unsigned char *sig)
00539 {
00540     ge_p3 p, A;
00541     int ret = 0;
00542 
00543     XMEMCPY(&A, inA, sizeof(ge_p3));
00544 
00545     /* find SB */
00546     ed25519_smult(&p, &ed25519_base, sig);
00547 
00548     /* find H(R,A,M) * -A */
00549     ed25519_smult(&A, &A, h);
00550 
00551     /* SB + -H(R,A,M)A */
00552     ed25519_add(&A, &p, &A);
00553 
00554     fe_copy(R->X, A.X);
00555     fe_copy(R->Y, A.Y);
00556     fe_copy(R->Z, A.Z);
00557 
00558     return ret;
00559 }
00560 
00561 #endif /* HAVE_ED25519 */
00562 #endif /* CURVED25519_SMALL */
00563 
00564