3 * Copyright (C) 2006-2015 wolfSSL Inc.
5 * This file is part of wolfSSL. (formerly known as CyaSSL)
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.
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.
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
22 /* Based from Daniel Beer's public domain work. */
28 #include <wolfssl/wolfcrypt/settings.h>
32 #include <wolfssl/wolfcrypt/ge_operations.h>
33 #include <wolfssl/wolfcrypt/error-crypt.h>
35 #include <wolfssl/wolfcrypt/misc.h>
37 #include <wolfcrypt/src/misc.c>
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);
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
52 /*Arithmetic modulo the group order m = 2^252 +
53 27742317777372353535851937790883648493 =
54 7237005577332262213973186563042994240857116359379907606001950938285454250989 */
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,
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
69 int ge_compress_key(byte* out, const byte* xIn, const byte* yIn,
72 byte tmp[F25519_SIZE];
77 parity = (tmp[0] & 1) << 7;
83 for(i = 0; i < 32; i++) {
91 static word32 lt(word32 a,word32 b) /* 16-bit inputs */
94 x -= (unsigned int) b; /* 0..65535: no; 4294901761..4294967295: yes */
95 x >>= 31; /* 0: no; 1: yes */
100 /* Reduce coefficients of r before calling reduce_add_sub */
101 static void reduce_add_sub(word32 *r)
113 t[i] = r[i]-pb+(b<<8);
118 r[i] ^= mask & (r[i] ^ t[i]);
122 /* Reduce coefficients of x before calling barrett_reduce */
123 static void barrett_reduce(word32* r, word32 x[64])
125 /* See HAC, Alg. 14.42 */
128 word32 *q3 = q2 + 33;
135 for (i = 0;i < 66;++i) q2[i] = 0;
136 for (i = 0;i < 33;++i) r2[i] = 0;
140 if(i+j >= 31) q2[i+j] += mu[i]*x[j+31];
146 for(i=0;i<33;i++)r1[i] = x[i];
149 if(i+j < 33) r2[i+j] += m[i]*q3[j];
162 r[i] = r1[i]-pb+(b<<8);
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!
176 void sc_reduce(unsigned char x[64])
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);
187 void sc_muladd(byte* out, const byte* a, const byte* b, const byte* c)
193 XMEMSET(e, 0, sizeof(e));
199 /* Compute s = ze + k */
200 fprime_mul(s, a, e, ed25519_order);
201 fprime_add(s, c, ed25519_order);
207 /* Base point is (numbers wrapped):
209 * x = 151122213495354007725011514095885315114
210 * 54012693041857206046113283949847762202
211 * y = 463168356949264781694283940034751631413
212 * 07993866256225615783033603165251855960
214 * y is derived by transforming the original Montgomery base (u=9). x
215 * is the corresponding positive coordinate for the new curve equation.
218 const ge_p3 ed25519_base = {
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
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
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
241 const ge_p3 ed25519_neutral = {
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
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
266 void ed25519_add(ge_p3 *r,
267 const ge_p3 *p1, const ge_p3 *p2)
269 /* Explicit formulas database: add-2008-hwcd-3
271 * source 2008 Hisil--Wong--Carter--Dawson,
272 * http://eprint.iacr.org/2008/522, Section 3.1
273 * appliesto extended-1
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
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);
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);
309 fe_mul__distinct(d, p1->T, p2->T);
310 fe_mul__distinct(c, d, ed25519_k);
313 fe_mul__distinct(d, p1->Z, p2->Z);
329 fe_mul__distinct(r->X, e, f);
332 fe_mul__distinct(r->Y, g, h);
335 fe_mul__distinct(r->T, e, h);
338 fe_mul__distinct(r->Z, f, g);
342 void ed25519_double(ge_p3 *r, const ge_p3 *p)
344 /* Explicit formulas database: dbl-2008-hwcd
346 * source 2008 Hisil--Wong--Carter--Dawson,
347 * http://eprint.iacr.org/2008/522, Section 3.3
352 * compute E = (X1+Y1)^2-A-B
370 fe_mul__distinct(a, p->X, p->X);
373 fe_mul__distinct(b, p->Y, p->Y);
376 fe_mul__distinct(c, p->Z, p->Z);
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);
397 fe_mul__distinct(r->X, e, f);
400 fe_mul__distinct(r->Y, g, h);
403 fe_mul__distinct(r->T, e, h);
406 fe_mul__distinct(r->Z, f, g);
410 void ed25519_smult(ge_p3 *r_out, const ge_p3 *p, const byte *e)
415 XMEMCPY(&r, &ed25519_neutral, sizeof(r));
417 for (i = 255; i >= 0; i--) {
418 const byte bit = (e[i >> 3] >> (i & 7)) & 1;
421 ed25519_double(&r, &r);
422 ed25519_add(&s, &r, p);
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);
429 XMEMCPY(r_out, &r, sizeof(r));
433 void ge_scalarmult_base(ge_p3 *R,const unsigned char *nonce)
435 ed25519_smult(R, &ed25519_base, nonce);
439 /* pack the point h into array s */
440 void ge_p3_tobytes(unsigned char *s,const ge_p3 *h)
444 byte z1[F25519_SIZE];
447 fe_inv__distinct(z1, h->Z);
448 fe_mul__distinct(x, h->X, z1);
449 fe_mul__distinct(y, h->Y, z1);
454 parity = (x[0] & 1) << 7;
461 /* pack the point h into array s */
462 void ge_tobytes(unsigned char *s,const ge_p2 *h)
466 byte z1[F25519_SIZE];
469 fe_inv__distinct(z1, h->Z);
470 fe_mul__distinct(x, h->X, z1);
471 fe_mul__distinct(y, h->Y, z1);
476 parity = (x[0] & 1) << 7;
484 Test if the public key can be uncommpressed and negate it (-X,Y,Z,-T)
487 int ge_frombytes_negate_vartime(ge_p3 *p,const unsigned char *s)
498 /* unpack the key s */
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);
511 fe_select(x, a, b, (a[0] ^ parity) & 1);
513 /* test that x^2 is equal to c */
514 fe_mul__distinct(a, x, x);
517 ret |= ConstantCompare(a, c, F25519_SIZE);
519 /* project the key s onto p */
523 fe_mul__distinct(p->T, x, y);
525 /* negate, the point becomes (-X,Y,Z,-T) */
533 int ge_double_scalarmult_vartime(ge_p2* R, const unsigned char *h,
534 const ge_p3 *inA,const unsigned char *sig)
539 XMEMCPY(&A, inA, sizeof(ge_p3));
542 ed25519_smult(&p, &ed25519_base, sig);
544 /* find H(R,A,M) * -A */
545 ed25519_smult(&A, &A, h);
547 /* SB + -H(R,A,M)A */
548 ed25519_add(&A, &p, &A);
557 #endif /* HAVE_ED25519 */