Xuyi Wang / wolfSSL

Important changes to repositories hosted on mbed.com

Mbed hosted mercurial repositories are deprecated and are due to be permanently deleted in July 2026.

To keep a copy of this software download the repository Zip archive or clone locally using Mercurial.

It is also possible to export all your personal repositories from the account settings page.

Dependents:   OS

wolfcrypt/src/ge_low_mem.c@0:d92f9d21154c, 2015-06-26 (annotated)

Committer:
wolfSSL
Date:
Fri Jun 26 00:39:20 2015 +0000
Revision:
0:d92f9d21154c
wolfSSL 3.6.0

Who changed what in which revision?

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