wolf SSL / wolfSSL

wolfSSL SSL/TLS library, support up to TLS1.3

Dependents:   CyaSSL-Twitter-OAuth4Tw Example-client-tls-cert TwitterReader TweetTest ... more

wolfcrypt/src/ge_low_mem.c@13:f67a6c6013ca, 2017-08-22 (annotated)

Committer:
wolfSSL
Date:
Tue Aug 22 10:48:22 2017 +0000
Revision:
13:f67a6c6013ca
wolfSSL3.12.0 with TLS1.3

Who changed what in which revision?

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