ge_low_mem.c

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