1/* $OpenBSD: fe25519.c,v 1.1 2014/07/22 00:41:19 deraadt Exp $ */ 2 3/* 4 * Public Domain, Authors: Daniel J. Bernstein, Niels Duif, Tanja Lange, 5 * Peter Schwabe, Bo-Yin Yang. 6 * Copied from supercop-20130419/crypto_sign/ed25519/ref/fe25519.c 7 */ 8 9#define WINDOWSIZE 1 /* Should be 1,2, or 4 */ 10#define WINDOWMASK ((1<<WINDOWSIZE)-1) 11 12#include "fe25519.h" 13 14static crypto_uint32 equal(crypto_uint32 a,crypto_uint32 b) /* 16-bit inputs */ 15{ 16 crypto_uint32 x = a ^ b; /* 0: yes; 1..65535: no */ 17 x -= 1; /* 4294967295: yes; 0..65534: no */ 18 x >>= 31; /* 1: yes; 0: no */ 19 return x; 20} 21 22static crypto_uint32 ge(crypto_uint32 a,crypto_uint32 b) /* 16-bit inputs */ 23{ 24 unsigned int x = a; 25 x -= (unsigned int) b; /* 0..65535: yes; 4294901761..4294967295: no */ 26 x >>= 31; /* 0: yes; 1: no */ 27 x ^= 1; /* 1: yes; 0: no */ 28 return x; 29} 30 31static crypto_uint32 times19(crypto_uint32 a) 32{ 33 return (a << 4) + (a << 1) + a; 34} 35 36static crypto_uint32 times38(crypto_uint32 a) 37{ 38 return (a << 5) + (a << 2) + (a << 1); 39} 40 41static void reduce_add_sub(fe25519 *r) 42{ 43 crypto_uint32 t; 44 int i,rep; 45 46 for(rep=0;rep<4;rep++) 47 { 48 t = r->v[31] >> 7; 49 r->v[31] &= 127; 50 t = times19(t); 51 r->v[0] += t; 52 for(i=0;i<31;i++) 53 { 54 t = r->v[i] >> 8; 55 r->v[i+1] += t; 56 r->v[i] &= 255; 57 } 58 } 59} 60 61static void reduce_mul(fe25519 *r) 62{ 63 crypto_uint32 t; 64 int i,rep; 65 66 for(rep=0;rep<2;rep++) 67 { 68 t = r->v[31] >> 7; 69 r->v[31] &= 127; 70 t = times19(t); 71 r->v[0] += t; 72 for(i=0;i<31;i++) 73 { 74 t = r->v[i] >> 8; 75 r->v[i+1] += t; 76 r->v[i] &= 255; 77 } 78 } 79} 80 81/* reduction modulo 2^255-19 */ 82void fe25519_freeze(fe25519 *r) 83{ 84 int i; 85 crypto_uint32 m = equal(r->v[31],127); 86 for(i=30;i>0;i--) 87 m &= equal(r->v[i],255); 88 m &= ge(r->v[0],237); 89 90 m = -m; 91 92 r->v[31] -= m&127; 93 for(i=30;i>0;i--) 94 r->v[i] -= m&255; 95 r->v[0] -= m&237; 96} 97 98void fe25519_unpack(fe25519 *r, const unsigned char x[32]) 99{ 100 int i; 101 for(i=0;i<32;i++) r->v[i] = x[i]; 102 r->v[31] &= 127; 103} 104 105/* Assumes input x being reduced below 2^255 */ 106void fe25519_pack(unsigned char r[32], const fe25519 *x) 107{ 108 int i; 109 fe25519 y = *x; 110 fe25519_freeze(&y); 111 for(i=0;i<32;i++) 112 r[i] = y.v[i]; 113} 114 115int fe25519_iszero(const fe25519 *x) 116{ 117 int i; 118 int r; 119 fe25519 t = *x; 120 fe25519_freeze(&t); 121 r = equal(t.v[0],0); 122 for(i=1;i<32;i++) 123 r &= equal(t.v[i],0); 124 return r; 125} 126 127int fe25519_iseq_vartime(const fe25519 *x, const fe25519 *y) 128{ 129 int i; 130 fe25519 t1 = *x; 131 fe25519 t2 = *y; 132 fe25519_freeze(&t1); 133 fe25519_freeze(&t2); 134 for(i=0;i<32;i++) 135 if(t1.v[i] != t2.v[i]) return 0; 136 return 1; 137} 138 139void fe25519_cmov(fe25519 *r, const fe25519 *x, unsigned char b) 140{ 141 int i; 142 crypto_uint32 mask = b; 143 mask = -mask; 144 for(i=0;i<32;i++) r->v[i] ^= mask & (x->v[i] ^ r->v[i]); 145} 146 147unsigned char fe25519_getparity(const fe25519 *x) 148{ 149 fe25519 t = *x; 150 fe25519_freeze(&t); 151 return t.v[0] & 1; 152} 153 154void fe25519_setone(fe25519 *r) 155{ 156 int i; 157 r->v[0] = 1; 158 for(i=1;i<32;i++) r->v[i]=0; 159} 160 161void fe25519_setzero(fe25519 *r) 162{ 163 int i; 164 for(i=0;i<32;i++) r->v[i]=0; 165} 166 167void fe25519_neg(fe25519 *r, const fe25519 *x) 168{ 169 fe25519 t; 170 int i; 171 for(i=0;i<32;i++) t.v[i]=x->v[i]; 172 fe25519_setzero(r); 173 fe25519_sub(r, r, &t); 174} 175 176void fe25519_add(fe25519 *r, const fe25519 *x, const fe25519 *y) 177{ 178 int i; 179 for(i=0;i<32;i++) r->v[i] = x->v[i] + y->v[i]; 180 reduce_add_sub(r); 181} 182 183void fe25519_sub(fe25519 *r, const fe25519 *x, const fe25519 *y) 184{ 185 int i; 186 crypto_uint32 t[32]; 187 t[0] = x->v[0] + 0x1da; 188 t[31] = x->v[31] + 0xfe; 189 for(i=1;i<31;i++) t[i] = x->v[i] + 0x1fe; 190 for(i=0;i<32;i++) r->v[i] = t[i] - y->v[i]; 191 reduce_add_sub(r); 192} 193 194void fe25519_mul(fe25519 *r, const fe25519 *x, const fe25519 *y) 195{ 196 int i,j; 197 crypto_uint32 t[63]; 198 for(i=0;i<63;i++)t[i] = 0; 199 200 for(i=0;i<32;i++) 201 for(j=0;j<32;j++) 202 t[i+j] += x->v[i] * y->v[j]; 203 204 for(i=32;i<63;i++) 205 r->v[i-32] = t[i-32] + times38(t[i]); 206 r->v[31] = t[31]; /* result now in r[0]...r[31] */ 207 208 reduce_mul(r); 209} 210 211void fe25519_square(fe25519 *r, const fe25519 *x) 212{ 213 fe25519_mul(r, x, x); 214} 215 216void fe25519_invert(fe25519 *r, const fe25519 *x) 217{ 218 fe25519 z2; 219 fe25519 z9; 220 fe25519 z11; 221 fe25519 z2_5_0; 222 fe25519 z2_10_0; 223 fe25519 z2_20_0; 224 fe25519 z2_50_0; 225 fe25519 z2_100_0; 226 fe25519 t0; 227 fe25519 t1; 228 int i; 229 230 /* 2 */ fe25519_square(&z2,x); 231 /* 4 */ fe25519_square(&t1,&z2); 232 /* 8 */ fe25519_square(&t0,&t1); 233 /* 9 */ fe25519_mul(&z9,&t0,x); 234 /* 11 */ fe25519_mul(&z11,&z9,&z2); 235 /* 22 */ fe25519_square(&t0,&z11); 236 /* 2^5 - 2^0 = 31 */ fe25519_mul(&z2_5_0,&t0,&z9); 237 238 /* 2^6 - 2^1 */ fe25519_square(&t0,&z2_5_0); 239 /* 2^7 - 2^2 */ fe25519_square(&t1,&t0); 240 /* 2^8 - 2^3 */ fe25519_square(&t0,&t1); 241 /* 2^9 - 2^4 */ fe25519_square(&t1,&t0); 242 /* 2^10 - 2^5 */ fe25519_square(&t0,&t1); 243 /* 2^10 - 2^0 */ fe25519_mul(&z2_10_0,&t0,&z2_5_0); 244 245 /* 2^11 - 2^1 */ fe25519_square(&t0,&z2_10_0); 246 /* 2^12 - 2^2 */ fe25519_square(&t1,&t0); 247 /* 2^20 - 2^10 */ for (i = 2;i < 10;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); } 248 /* 2^20 - 2^0 */ fe25519_mul(&z2_20_0,&t1,&z2_10_0); 249 250 /* 2^21 - 2^1 */ fe25519_square(&t0,&z2_20_0); 251 /* 2^22 - 2^2 */ fe25519_square(&t1,&t0); 252 /* 2^40 - 2^20 */ for (i = 2;i < 20;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); } 253 /* 2^40 - 2^0 */ fe25519_mul(&t0,&t1,&z2_20_0); 254 255 /* 2^41 - 2^1 */ fe25519_square(&t1,&t0); 256 /* 2^42 - 2^2 */ fe25519_square(&t0,&t1); 257 /* 2^50 - 2^10 */ for (i = 2;i < 10;i += 2) { fe25519_square(&t1,&t0); fe25519_square(&t0,&t1); } 258 /* 2^50 - 2^0 */ fe25519_mul(&z2_50_0,&t0,&z2_10_0); 259 260 /* 2^51 - 2^1 */ fe25519_square(&t0,&z2_50_0); 261 /* 2^52 - 2^2 */ fe25519_square(&t1,&t0); 262 /* 2^100 - 2^50 */ for (i = 2;i < 50;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); } 263 /* 2^100 - 2^0 */ fe25519_mul(&z2_100_0,&t1,&z2_50_0); 264 265 /* 2^101 - 2^1 */ fe25519_square(&t1,&z2_100_0); 266 /* 2^102 - 2^2 */ fe25519_square(&t0,&t1); 267 /* 2^200 - 2^100 */ for (i = 2;i < 100;i += 2) { fe25519_square(&t1,&t0); fe25519_square(&t0,&t1); } 268 /* 2^200 - 2^0 */ fe25519_mul(&t1,&t0,&z2_100_0); 269 270 /* 2^201 - 2^1 */ fe25519_square(&t0,&t1); 271 /* 2^202 - 2^2 */ fe25519_square(&t1,&t0); 272 /* 2^250 - 2^50 */ for (i = 2;i < 50;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); } 273 /* 2^250 - 2^0 */ fe25519_mul(&t0,&t1,&z2_50_0); 274 275 /* 2^251 - 2^1 */ fe25519_square(&t1,&t0); 276 /* 2^252 - 2^2 */ fe25519_square(&t0,&t1); 277 /* 2^253 - 2^3 */ fe25519_square(&t1,&t0); 278 /* 2^254 - 2^4 */ fe25519_square(&t0,&t1); 279 /* 2^255 - 2^5 */ fe25519_square(&t1,&t0); 280 /* 2^255 - 21 */ fe25519_mul(r,&t1,&z11); 281} 282 283void fe25519_pow2523(fe25519 *r, const fe25519 *x) 284{ 285 fe25519 z2; 286 fe25519 z9; 287 fe25519 z11; 288 fe25519 z2_5_0; 289 fe25519 z2_10_0; 290 fe25519 z2_20_0; 291 fe25519 z2_50_0; 292 fe25519 z2_100_0; 293 fe25519 t; 294 int i; 295 296 /* 2 */ fe25519_square(&z2,x); 297 /* 4 */ fe25519_square(&t,&z2); 298 /* 8 */ fe25519_square(&t,&t); 299 /* 9 */ fe25519_mul(&z9,&t,x); 300 /* 11 */ fe25519_mul(&z11,&z9,&z2); 301 /* 22 */ fe25519_square(&t,&z11); 302 /* 2^5 - 2^0 = 31 */ fe25519_mul(&z2_5_0,&t,&z9); 303 304 /* 2^6 - 2^1 */ fe25519_square(&t,&z2_5_0); 305 /* 2^10 - 2^5 */ for (i = 1;i < 5;i++) { fe25519_square(&t,&t); } 306 /* 2^10 - 2^0 */ fe25519_mul(&z2_10_0,&t,&z2_5_0); 307 308 /* 2^11 - 2^1 */ fe25519_square(&t,&z2_10_0); 309 /* 2^20 - 2^10 */ for (i = 1;i < 10;i++) { fe25519_square(&t,&t); } 310 /* 2^20 - 2^0 */ fe25519_mul(&z2_20_0,&t,&z2_10_0); 311 312 /* 2^21 - 2^1 */ fe25519_square(&t,&z2_20_0); 313 /* 2^40 - 2^20 */ for (i = 1;i < 20;i++) { fe25519_square(&t,&t); } 314 /* 2^40 - 2^0 */ fe25519_mul(&t,&t,&z2_20_0); 315 316 /* 2^41 - 2^1 */ fe25519_square(&t,&t); 317 /* 2^50 - 2^10 */ for (i = 1;i < 10;i++) { fe25519_square(&t,&t); } 318 /* 2^50 - 2^0 */ fe25519_mul(&z2_50_0,&t,&z2_10_0); 319 320 /* 2^51 - 2^1 */ fe25519_square(&t,&z2_50_0); 321 /* 2^100 - 2^50 */ for (i = 1;i < 50;i++) { fe25519_square(&t,&t); } 322 /* 2^100 - 2^0 */ fe25519_mul(&z2_100_0,&t,&z2_50_0); 323 324 /* 2^101 - 2^1 */ fe25519_square(&t,&z2_100_0); 325 /* 2^200 - 2^100 */ for (i = 1;i < 100;i++) { fe25519_square(&t,&t); } 326 /* 2^200 - 2^0 */ fe25519_mul(&t,&t,&z2_100_0); 327 328 /* 2^201 - 2^1 */ fe25519_square(&t,&t); 329 /* 2^250 - 2^50 */ for (i = 1;i < 50;i++) { fe25519_square(&t,&t); } 330 /* 2^250 - 2^0 */ fe25519_mul(&t,&t,&z2_50_0); 331 332 /* 2^251 - 2^1 */ fe25519_square(&t,&t); 333 /* 2^252 - 2^2 */ fe25519_square(&t,&t); 334 /* 2^252 - 3 */ fe25519_mul(r,&t,x); 335} 336