git.sur5r.net Git - freertos/blob - FreeRTOS-Plus/Source/WolfSSL/wolfcrypt/src/ge_low_mem.c

   1 /* ge_low_mem.c
   2  *
   3  * Copyright (C) 2006-2015 wolfSSL Inc.
   4  *
   5  * This file is part of wolfSSL. (formerly known as CyaSSL)
   6  *
   7  * wolfSSL is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License as published by
   9  * the Free Software Foundation; either version 2 of the License, or
  10  * (at your option) any later version.
  11  *
  12  * wolfSSL is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with this program; if not, write to the Free Software
  19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
  20  */
  21
  22  /* Based from Daniel Beer's public domain work. */
  23
  24 #ifdef HAVE_CONFIG_H
  25     #include <config.h>
  26 #endif
  27
  28 #include <wolfssl/wolfcrypt/settings.h>
  29
  30 #ifdef HAVE_ED25519
  31
  32 #include <wolfssl/wolfcrypt/ge_operations.h>
  33 #include <wolfssl/wolfcrypt/error-crypt.h>
  34 #ifdef NO_INLINE
  35     #include <wolfssl/wolfcrypt/misc.h>
  36 #else
  37     #include <wolfcrypt/src/misc.c>
  38 #endif
  39
  40 void ed25519_smult(ge_p3 *r, const ge_p3 *a, const byte *e);
  41 void ed25519_add(ge_p3 *r, const ge_p3 *a, const ge_p3 *b);
  42 void ed25519_double(ge_p3 *r, const ge_p3 *a);
  43
  44
  45 static const byte ed25519_order[F25519_SIZE] = {
  46         0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58,
  47         0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14,
  48         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  49         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10
  50 };
  51
  52 /*Arithmetic modulo the group order m = 2^252 +
  53  27742317777372353535851937790883648493 =
  54  7237005577332262213973186563042994240857116359379907606001950938285454250989 */
  55
  56 static const word32 m[32] = {
  57     0xED,0xD3,0xF5,0x5C,0x1A,0x63,0x12,0x58,0xD6,0x9C,0xF7,0xA2,0xDE,0xF9,
  58     0xDE,0x14,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
  59     0x00,0x00,0x00,0x10
  60 };
  61
  62 static const word32 mu[33] = {
  63     0x1B,0x13,0x2C,0x0A,0xA3,0xE5,0x9C,0xED,0xA7,0x29,0x63,0x08,0x5D,0x21,
  64     0x06,0x21,0xEB,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
  65     0xFF,0xFF,0xFF,0xFF,0x0F
  66 };
  67
  68
  69 int ge_compress_key(byte* out, const byte* xIn, const byte* yIn,
  70                         word32 keySz)
  71 {
  72         byte tmp[F25519_SIZE];
  73         byte parity;
  74     int     i;
  75
  76         fe_copy(tmp, xIn);
  77         parity = (tmp[0] & 1) << 7;
  78
  79     byte pt[32];
  80         fe_copy(pt, yIn);
  81         pt[31] |= parity;
  82
  83     for(i = 0; i < 32; i++) {
  84         out[32-i-1] = pt[i];
  85     }
  86     (void)keySz;
  87     return 0;
  88 }
  89
  90
  91 static word32 lt(word32 a,word32 b) /* 16-bit inputs */
  92 {
  93   unsigned int x = a;
  94   x -= (unsigned int) b; /* 0..65535: no; 4294901761..4294967295: yes */
  95   x >>= 31; /* 0: no; 1: yes */
  96   return x;
  97 }
  98
  99
 100 /* Reduce coefficients of r before calling reduce_add_sub */
 101 static void reduce_add_sub(word32 *r)
 102 {
 103   word32 pb = 0;
 104   word32 b;
 105   word32 mask;
 106   int i;
 107   unsigned char t[32];
 108
 109   for(i=0;i<32;i++)
 110   {
 111     pb += m[i];
 112     b = lt(r[i],pb);
 113     t[i] = r[i]-pb+(b<<8);
 114     pb = b;
 115   }
 116   mask = b - 1;
 117   for(i=0;i<32;i++)
 118     r[i] ^= mask & (r[i] ^ t[i]);
 119 }
 120
 121
 122 /* Reduce coefficients of x before calling barrett_reduce */
 123 static void barrett_reduce(word32* r, word32 x[64])
 124 {
 125   /* See HAC, Alg. 14.42 */
 126   int i,j;
 127   word32 q2[66];
 128   word32 *q3 = q2 + 33;
 129   word32 r1[33];
 130   word32 r2[33];
 131   word32 carry;
 132   word32 pb = 0;
 133   word32 b;
 134
 135   for (i = 0;i < 66;++i) q2[i] = 0;
 136   for (i = 0;i < 33;++i) r2[i] = 0;
 137
 138   for(i=0;i<33;i++)
 139     for(j=0;j<33;j++)
 140       if(i+j >= 31) q2[i+j] += mu[i]*x[j+31];
 141   carry = q2[31] >> 8;
 142   q2[32] += carry;
 143   carry = q2[32] >> 8;
 144   q2[33] += carry;
 145
 146   for(i=0;i<33;i++)r1[i] = x[i];
 147   for(i=0;i<32;i++)
 148     for(j=0;j<33;j++)
 149       if(i+j < 33) r2[i+j] += m[i]*q3[j];
 150
 151   for(i=0;i<32;i++)
 152   {
 153     carry = r2[i] >> 8;
 154     r2[i+1] += carry;
 155     r2[i] &= 0xff;
 156   }
 157
 158   for(i=0;i<32;i++)
 159   {
 160     pb += r2[i];
 161     b = lt(r1[i],pb);
 162     r[i] = r1[i]-pb+(b<<8);
 163     pb = b;
 164   }
 165
 166   /* XXX: Can it really happen that r<0?, See HAC, Alg 14.42, Step 3
 167    * r is an unsigned type.
 168    * If so: Handle  it here!
 169    */
 170
 171   reduce_add_sub(r);
 172   reduce_add_sub(r);
 173 }
 174
 175
 176 void sc_reduce(unsigned char x[64])
 177 {
 178   int i;
 179   word32 t[64];
 180   word32 r[32];
 181   for(i=0;i<64;i++) t[i] = x[i];
 182   barrett_reduce(r, t);
 183   for(i=0;i<32;i++) x[i] = (r[i] & 0xFF);
 184 }
 185
 186
 187 void sc_muladd(byte* out, const byte* a, const byte* b, const byte* c)
 188 {
 189
 190         byte s[32];
 191     byte e[64];
 192
 193     XMEMSET(e, 0, sizeof(e));
 194     XMEMCPY(e, b, 32);
 195
 196         /* Obtain e */
 197         sc_reduce(e);
 198
 199         /* Compute s = ze + k */
 200         fprime_mul(s, a, e, ed25519_order);
 201         fprime_add(s, c, ed25519_order);
 202
 203         XMEMCPY(out, s, 32);
 204 }
 205
 206
 207 /* Base point is (numbers wrapped):
 208  *
 209  *     x = 151122213495354007725011514095885315114
 210  *         54012693041857206046113283949847762202
 211  *     y = 463168356949264781694283940034751631413
 212  *         07993866256225615783033603165251855960
 213  *
 214  * y is derived by transforming the original Montgomery base (u=9). x
 215  * is the corresponding positive coordinate for the new curve equation.
 216  * t is x*y.
 217  */
 218 const ge_p3 ed25519_base = {
 219         .X = {
 220                 0x1a, 0xd5, 0x25, 0x8f, 0x60, 0x2d, 0x56, 0xc9,
 221                 0xb2, 0xa7, 0x25, 0x95, 0x60, 0xc7, 0x2c, 0x69,
 222                 0x5c, 0xdc, 0xd6, 0xfd, 0x31, 0xe2, 0xa4, 0xc0,
 223                 0xfe, 0x53, 0x6e, 0xcd, 0xd3, 0x36, 0x69, 0x21
 224         },
 225         .Y = {
 226                 0x58, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
 227                 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
 228                 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
 229                 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66
 230         },
 231         .T = {
 232                 0xa3, 0xdd, 0xb7, 0xa5, 0xb3, 0x8a, 0xde, 0x6d,
 233                 0xf5, 0x52, 0x51, 0x77, 0x80, 0x9f, 0xf0, 0x20,
 234                 0x7d, 0xe3, 0xab, 0x64, 0x8e, 0x4e, 0xea, 0x66,
 235                 0x65, 0x76, 0x8b, 0xd7, 0x0f, 0x5f, 0x87, 0x67
 236         },
 237         .Z = {1, 0}
 238 };
 239
 240
 241 const ge_p3 ed25519_neutral = {
 242         .X = {0},
 243         .Y = {1, 0},
 244         .T = {0},
 245         .Z = {1, 0}
 246 };
 247
 248
 249 static const byte ed25519_d[F25519_SIZE] = {
 250         0xa3, 0x78, 0x59, 0x13, 0xca, 0x4d, 0xeb, 0x75,
 251         0xab, 0xd8, 0x41, 0x41, 0x4d, 0x0a, 0x70, 0x00,
 252         0x98, 0xe8, 0x79, 0x77, 0x79, 0x40, 0xc7, 0x8c,
 253         0x73, 0xfe, 0x6f, 0x2b, 0xee, 0x6c, 0x03, 0x52
 254 };
 255
 256
 257 /* k = 2d */
 258 static const byte ed25519_k[F25519_SIZE] = {
 259         0x59, 0xf1, 0xb2, 0x26, 0x94, 0x9b, 0xd6, 0xeb,
 260         0x56, 0xb1, 0x83, 0x82, 0x9a, 0x14, 0xe0, 0x00,
 261         0x30, 0xd1, 0xf3, 0xee, 0xf2, 0x80, 0x8e, 0x19,
 262         0xe7, 0xfc, 0xdf, 0x56, 0xdc, 0xd9, 0x06, 0x24
 263 };
 264
 265
 266 void ed25519_add(ge_p3 *r,
 267                  const ge_p3 *p1, const ge_p3 *p2)
 268 {
 269         /* Explicit formulas database: add-2008-hwcd-3
 270          *
 271          * source 2008 Hisil--Wong--Carter--Dawson,
 272          *     http://eprint.iacr.org/2008/522, Section 3.1
 273          * appliesto extended-1
 274          * parameter k
 275          * assume k = 2 d
 276          * compute A = (Y1-X1)(Y2-X2)
 277          * compute B = (Y1+X1)(Y2+X2)
 278          * compute C = T1 k T2
 279          * compute D = Z1 2 Z2
 280          * compute E = B - A
 281          * compute F = D - C
 282          * compute G = D + C
 283          * compute H = B + A
 284          * compute X3 = E F
 285          * compute Y3 = G H
 286          * compute T3 = E H
 287          * compute Z3 = F G
 288          */
 289         byte a[F25519_SIZE];
 290         byte b[F25519_SIZE];
 291         byte c[F25519_SIZE];
 292         byte d[F25519_SIZE];
 293         byte e[F25519_SIZE];
 294         byte f[F25519_SIZE];
 295         byte g[F25519_SIZE];
 296         byte h[F25519_SIZE];
 297
 298         /* A = (Y1-X1)(Y2-X2) */
 299         fe_sub(c, p1->Y, p1->X);
 300         fe_sub(d, p2->Y, p2->X);
 301         fe_mul__distinct(a, c, d);
 302
 303         /* B = (Y1+X1)(Y2+X2) */
 304         fe_add(c, p1->Y, p1->X);
 305         fe_add(d, p2->Y, p2->X);
 306         fe_mul__distinct(b, c, d);
 307
 308         /* C = T1 k T2 */
 309         fe_mul__distinct(d, p1->T, p2->T);
 310         fe_mul__distinct(c, d, ed25519_k);
 311
 312         /* D = Z1 2 Z2 */
 313         fe_mul__distinct(d, p1->Z, p2->Z);
 314         fe_add(d, d, d);
 315
 316         /* E = B - A */
 317         fe_sub(e, b, a);
 318
 319         /* F = D - C */
 320         fe_sub(f, d, c);
 321
 322         /* G = D + C */
 323         fe_add(g, d, c);
 324
 325         /* H = B + A */
 326         fe_add(h, b, a);
 327
 328         /* X3 = E F */
 329         fe_mul__distinct(r->X, e, f);
 330
 331         /* Y3 = G H */
 332         fe_mul__distinct(r->Y, g, h);
 333
 334         /* T3 = E H */
 335         fe_mul__distinct(r->T, e, h);
 336
 337         /* Z3 = F G */
 338         fe_mul__distinct(r->Z, f, g);
 339 }
 340
 341
 342 void ed25519_double(ge_p3 *r, const ge_p3 *p)
 343 {
 344         /* Explicit formulas database: dbl-2008-hwcd
 345          *
 346          * source 2008 Hisil--Wong--Carter--Dawson,
 347          *     http://eprint.iacr.org/2008/522, Section 3.3
 348          * compute A = X1^2
 349          * compute B = Y1^2
 350          * compute C = 2 Z1^2
 351          * compute D = a A
 352          * compute E = (X1+Y1)^2-A-B
 353          * compute G = D + B
 354          * compute F = G - C
 355          * compute H = D - B
 356          * compute X3 = E F
 357          * compute Y3 = G H
 358          * compute T3 = E H
 359          * compute Z3 = F G
 360          */
 361         byte a[F25519_SIZE];
 362         byte b[F25519_SIZE];
 363         byte c[F25519_SIZE];
 364         byte e[F25519_SIZE];
 365         byte f[F25519_SIZE];
 366         byte g[F25519_SIZE];
 367         byte h[F25519_SIZE];
 368
 369         /* A = X1^2 */
 370         fe_mul__distinct(a, p->X, p->X);
 371
 372         /* B = Y1^2 */
 373         fe_mul__distinct(b, p->Y, p->Y);
 374
 375         /* C = 2 Z1^2 */
 376         fe_mul__distinct(c, p->Z, p->Z);
 377         fe_add(c, c, c);
 378
 379         /* D = a A (alter sign) */
 380         /* E = (X1+Y1)^2-A-B */
 381         fe_add(f, p->X, p->Y);
 382         fe_mul__distinct(e, f, f);
 383         fe_sub(e, e, a);
 384         fe_sub(e, e, b);
 385
 386         /* G = D + B */
 387         fe_sub(g, b, a);
 388
 389         /* F = G - C */
 390         fe_sub(f, g, c);
 391
 392         /* H = D - B */
 393         fe_neg(h, b);
 394         fe_sub(h, h, a);
 395
 396         /* X3 = E F */
 397         fe_mul__distinct(r->X, e, f);
 398
 399         /* Y3 = G H */
 400         fe_mul__distinct(r->Y, g, h);
 401
 402         /* T3 = E H */
 403         fe_mul__distinct(r->T, e, h);
 404
 405         /* Z3 = F G */
 406         fe_mul__distinct(r->Z, f, g);
 407 }
 408
 409
 410 void ed25519_smult(ge_p3 *r_out, const ge_p3 *p, const byte *e)
 411 {
 412         ge_p3 r;
 413         int   i;
 414
 415     XMEMCPY(&r, &ed25519_neutral, sizeof(r));
 416
 417         for (i = 255; i >= 0; i--) {
 418                 const byte bit = (e[i >> 3] >> (i & 7)) & 1;
 419                 ge_p3 s;
 420
 421                 ed25519_double(&r, &r);
 422                 ed25519_add(&s, &r, p);
 423
 424                 fe_select(r.X, r.X, s.X, bit);
 425                 fe_select(r.Y, r.Y, s.Y, bit);
 426                 fe_select(r.Z, r.Z, s.Z, bit);
 427                 fe_select(r.T, r.T, s.T, bit);
 428         }
 429     XMEMCPY(r_out, &r, sizeof(r));
 430 }
 431
 432
 433 void ge_scalarmult_base(ge_p3 *R,const unsigned char *nonce)
 434 {
 435         ed25519_smult(R, &ed25519_base, nonce);
 436 }
 437
 438
 439 /* pack the point h into array s */
 440 void ge_p3_tobytes(unsigned char *s,const ge_p3 *h)
 441 {
 442         byte x[F25519_SIZE];
 443         byte y[F25519_SIZE];
 444         byte z1[F25519_SIZE];
 445         byte parity;
 446
 447         fe_inv__distinct(z1, h->Z);
 448         fe_mul__distinct(x, h->X, z1);
 449         fe_mul__distinct(y, h->Y, z1);
 450
 451         fe_normalize(x);
 452         fe_normalize(y);
 453
 454         parity = (x[0] & 1) << 7;
 455         fe_copy(s, y);
 456         fe_normalize(s);
 457         s[31] |= parity;
 458 }
 459
 460
 461 /* pack the point h into array s */
 462 void ge_tobytes(unsigned char *s,const ge_p2 *h)
 463 {
 464         byte x[F25519_SIZE];
 465         byte y[F25519_SIZE];
 466         byte z1[F25519_SIZE];
 467         byte parity;
 468
 469         fe_inv__distinct(z1, h->Z);
 470         fe_mul__distinct(x, h->X, z1);
 471         fe_mul__distinct(y, h->Y, z1);
 472
 473         fe_normalize(x);
 474         fe_normalize(y);
 475
 476         parity = (x[0] & 1) << 7;
 477         fe_copy(s, y);
 478         fe_normalize(s);
 479         s[31] |= parity;
 480 }
 481
 482
 483 /*
 484    Test if the public key can be uncommpressed and negate it (-X,Y,Z,-T)
 485    return 0 on success
 486  */
 487 int ge_frombytes_negate_vartime(ge_p3 *p,const unsigned char *s)
 488 {
 489
 490         byte parity;
 491     byte x[F25519_SIZE];
 492         byte y[F25519_SIZE];
 493         byte a[F25519_SIZE];
 494         byte b[F25519_SIZE];
 495         byte c[F25519_SIZE];
 496     int ret = 0;
 497
 498     /* unpack the key s */
 499     parity = s[31] >> 7;
 500     fe_copy(y, s);
 501         y[31] &= 127;
 502
 503         fe_mul__distinct(c, y, y);
 504     fe_mul__distinct(b, c, ed25519_d);
 505         fe_add(a, b, f25519_one);
 506         fe_inv__distinct(b, a);
 507         fe_sub(a, c, f25519_one);
 508         fe_mul__distinct(c, a, b);
 509         fe_sqrt(a, c);
 510         fe_neg(b, a);
 511         fe_select(x, a, b, (a[0] ^ parity) & 1);
 512
 513     /* test that x^2 is equal to c */
 514     fe_mul__distinct(a, x, x);
 515         fe_normalize(a);
 516         fe_normalize(c);
 517         ret |= ConstantCompare(a, c, F25519_SIZE);
 518
 519     /* project the key s onto p */
 520         fe_copy(p->X, x);
 521         fe_copy(p->Y, y);
 522         fe_load(p->Z, 1);
 523         fe_mul__distinct(p->T, x, y);
 524
 525     /* negate, the point becomes (-X,Y,Z,-T) */
 526     fe_neg(p->X,p->X);
 527     fe_neg(p->T,p->T);
 528
 529     return ret;
 530 }
 531
 532
 533 int ge_double_scalarmult_vartime(ge_p2* R, const unsigned char *h,
 534                                  const ge_p3 *inA,const unsigned char *sig)
 535 {
 536     ge_p3 p, A;
 537     int ret = 0;
 538
 539     XMEMCPY(&A, inA, sizeof(ge_p3));
 540
 541     /* find SB */
 542     ed25519_smult(&p, &ed25519_base, sig);
 543
 544     /* find H(R,A,M) * -A */
 545         ed25519_smult(&A, &A, h);
 546
 547     /* SB + -H(R,A,M)A */
 548         ed25519_add(&A, &p, &A);
 549
 550     fe_copy(R->X, A.X);
 551     fe_copy(R->Y, A.Y);
 552     fe_copy(R->Z, A.Z);
 553
 554     return ret;
 555 }
 556
 557 #endif /* HAVE_ED25519 */
 558