1261287Sdes/* $OpenBSD: fe25519.c,v 1.3 2013/12/09 11:03:45 markus Exp $ */ 2261287Sdes 3261287Sdes/* 4261287Sdes * Public Domain, Authors: Daniel J. Bernstein, Niels Duif, Tanja Lange, 5261287Sdes * Peter Schwabe, Bo-Yin Yang. 6261287Sdes * Copied from supercop-20130419/crypto_sign/ed25519/ref/fe25519.c 7261287Sdes */ 8261287Sdes 9261287Sdes#include "includes.h" 10261287Sdes 11261287Sdes#define WINDOWSIZE 1 /* Should be 1,2, or 4 */ 12261287Sdes#define WINDOWMASK ((1<<WINDOWSIZE)-1) 13261287Sdes 14261287Sdes#include "fe25519.h" 15261287Sdes 16261287Sdesstatic crypto_uint32 equal(crypto_uint32 a,crypto_uint32 b) /* 16-bit inputs */ 17261287Sdes{ 18261287Sdes crypto_uint32 x = a ^ b; /* 0: yes; 1..65535: no */ 19261287Sdes x -= 1; /* 4294967295: yes; 0..65534: no */ 20261287Sdes x >>= 31; /* 1: yes; 0: no */ 21261287Sdes return x; 22261287Sdes} 23261287Sdes 24261287Sdesstatic crypto_uint32 ge(crypto_uint32 a,crypto_uint32 b) /* 16-bit inputs */ 25261287Sdes{ 26261287Sdes unsigned int x = a; 27261287Sdes x -= (unsigned int) b; /* 0..65535: yes; 4294901761..4294967295: no */ 28261287Sdes x >>= 31; /* 0: yes; 1: no */ 29261287Sdes x ^= 1; /* 1: yes; 0: no */ 30261287Sdes return x; 31261287Sdes} 32261287Sdes 33261287Sdesstatic crypto_uint32 times19(crypto_uint32 a) 34261287Sdes{ 35261287Sdes return (a << 4) + (a << 1) + a; 36261287Sdes} 37261287Sdes 38261287Sdesstatic crypto_uint32 times38(crypto_uint32 a) 39261287Sdes{ 40261287Sdes return (a << 5) + (a << 2) + (a << 1); 41261287Sdes} 42261287Sdes 43261287Sdesstatic void reduce_add_sub(fe25519 *r) 44261287Sdes{ 45261287Sdes crypto_uint32 t; 46261287Sdes int i,rep; 47261287Sdes 48261287Sdes for(rep=0;rep<4;rep++) 49261287Sdes { 50261287Sdes t = r->v[31] >> 7; 51261287Sdes r->v[31] &= 127; 52261287Sdes t = times19(t); 53261287Sdes r->v[0] += t; 54261287Sdes for(i=0;i<31;i++) 55261287Sdes { 56261287Sdes t = r->v[i] >> 8; 57261287Sdes r->v[i+1] += t; 58261287Sdes r->v[i] &= 255; 59261287Sdes } 60261287Sdes } 61261287Sdes} 62261287Sdes 63261287Sdesstatic void reduce_mul(fe25519 *r) 64261287Sdes{ 65261287Sdes crypto_uint32 t; 66261287Sdes int i,rep; 67261287Sdes 68261287Sdes for(rep=0;rep<2;rep++) 69261287Sdes { 70261287Sdes t = r->v[31] >> 7; 71261287Sdes r->v[31] &= 127; 72261287Sdes t = times19(t); 73261287Sdes r->v[0] += t; 74261287Sdes for(i=0;i<31;i++) 75261287Sdes { 76261287Sdes t = r->v[i] >> 8; 77261287Sdes r->v[i+1] += t; 78261287Sdes r->v[i] &= 255; 79261287Sdes } 80261287Sdes } 81261287Sdes} 82261287Sdes 83261287Sdes/* reduction modulo 2^255-19 */ 84261287Sdesvoid fe25519_freeze(fe25519 *r) 85261287Sdes{ 86261287Sdes int i; 87261287Sdes crypto_uint32 m = equal(r->v[31],127); 88261287Sdes for(i=30;i>0;i--) 89261287Sdes m &= equal(r->v[i],255); 90261287Sdes m &= ge(r->v[0],237); 91261287Sdes 92261287Sdes m = -m; 93261287Sdes 94261287Sdes r->v[31] -= m&127; 95261287Sdes for(i=30;i>0;i--) 96261287Sdes r->v[i] -= m&255; 97261287Sdes r->v[0] -= m&237; 98261287Sdes} 99261287Sdes 100261287Sdesvoid fe25519_unpack(fe25519 *r, const unsigned char x[32]) 101261287Sdes{ 102261287Sdes int i; 103261287Sdes for(i=0;i<32;i++) r->v[i] = x[i]; 104261287Sdes r->v[31] &= 127; 105261287Sdes} 106261287Sdes 107261287Sdes/* Assumes input x being reduced below 2^255 */ 108261287Sdesvoid fe25519_pack(unsigned char r[32], const fe25519 *x) 109261287Sdes{ 110261287Sdes int i; 111261287Sdes fe25519 y = *x; 112261287Sdes fe25519_freeze(&y); 113261287Sdes for(i=0;i<32;i++) 114261287Sdes r[i] = y.v[i]; 115261287Sdes} 116261287Sdes 117261287Sdesint fe25519_iszero(const fe25519 *x) 118261287Sdes{ 119261287Sdes int i; 120261287Sdes int r; 121261287Sdes fe25519 t = *x; 122261287Sdes fe25519_freeze(&t); 123261287Sdes r = equal(t.v[0],0); 124261287Sdes for(i=1;i<32;i++) 125261287Sdes r &= equal(t.v[i],0); 126261287Sdes return r; 127261287Sdes} 128261287Sdes 129261287Sdesint fe25519_iseq_vartime(const fe25519 *x, const fe25519 *y) 130261287Sdes{ 131261287Sdes int i; 132261287Sdes fe25519 t1 = *x; 133261287Sdes fe25519 t2 = *y; 134261287Sdes fe25519_freeze(&t1); 135261287Sdes fe25519_freeze(&t2); 136261287Sdes for(i=0;i<32;i++) 137261287Sdes if(t1.v[i] != t2.v[i]) return 0; 138261287Sdes return 1; 139261287Sdes} 140261287Sdes 141261287Sdesvoid fe25519_cmov(fe25519 *r, const fe25519 *x, unsigned char b) 142261287Sdes{ 143261287Sdes int i; 144261287Sdes crypto_uint32 mask = b; 145261287Sdes mask = -mask; 146261287Sdes for(i=0;i<32;i++) r->v[i] ^= mask & (x->v[i] ^ r->v[i]); 147261287Sdes} 148261287Sdes 149261287Sdesunsigned char fe25519_getparity(const fe25519 *x) 150261287Sdes{ 151261287Sdes fe25519 t = *x; 152261287Sdes fe25519_freeze(&t); 153261287Sdes return t.v[0] & 1; 154261287Sdes} 155261287Sdes 156261287Sdesvoid fe25519_setone(fe25519 *r) 157261287Sdes{ 158261287Sdes int i; 159261287Sdes r->v[0] = 1; 160261287Sdes for(i=1;i<32;i++) r->v[i]=0; 161261287Sdes} 162261287Sdes 163261287Sdesvoid fe25519_setzero(fe25519 *r) 164261287Sdes{ 165261287Sdes int i; 166261287Sdes for(i=0;i<32;i++) r->v[i]=0; 167261287Sdes} 168261287Sdes 169261287Sdesvoid fe25519_neg(fe25519 *r, const fe25519 *x) 170261287Sdes{ 171261287Sdes fe25519 t; 172261287Sdes int i; 173261287Sdes for(i=0;i<32;i++) t.v[i]=x->v[i]; 174261287Sdes fe25519_setzero(r); 175261287Sdes fe25519_sub(r, r, &t); 176261287Sdes} 177261287Sdes 178261287Sdesvoid fe25519_add(fe25519 *r, const fe25519 *x, const fe25519 *y) 179261287Sdes{ 180261287Sdes int i; 181261287Sdes for(i=0;i<32;i++) r->v[i] = x->v[i] + y->v[i]; 182261287Sdes reduce_add_sub(r); 183261287Sdes} 184261287Sdes 185261287Sdesvoid fe25519_sub(fe25519 *r, const fe25519 *x, const fe25519 *y) 186261287Sdes{ 187261287Sdes int i; 188261287Sdes crypto_uint32 t[32]; 189261287Sdes t[0] = x->v[0] + 0x1da; 190261287Sdes t[31] = x->v[31] + 0xfe; 191261287Sdes for(i=1;i<31;i++) t[i] = x->v[i] + 0x1fe; 192261287Sdes for(i=0;i<32;i++) r->v[i] = t[i] - y->v[i]; 193261287Sdes reduce_add_sub(r); 194261287Sdes} 195261287Sdes 196261287Sdesvoid fe25519_mul(fe25519 *r, const fe25519 *x, const fe25519 *y) 197261287Sdes{ 198261287Sdes int i,j; 199261287Sdes crypto_uint32 t[63]; 200261287Sdes for(i=0;i<63;i++)t[i] = 0; 201261287Sdes 202261287Sdes for(i=0;i<32;i++) 203261287Sdes for(j=0;j<32;j++) 204261287Sdes t[i+j] += x->v[i] * y->v[j]; 205261287Sdes 206261287Sdes for(i=32;i<63;i++) 207261287Sdes r->v[i-32] = t[i-32] + times38(t[i]); 208261287Sdes r->v[31] = t[31]; /* result now in r[0]...r[31] */ 209261287Sdes 210261287Sdes reduce_mul(r); 211261287Sdes} 212261287Sdes 213261287Sdesvoid fe25519_square(fe25519 *r, const fe25519 *x) 214261287Sdes{ 215261287Sdes fe25519_mul(r, x, x); 216261287Sdes} 217261287Sdes 218261287Sdesvoid fe25519_invert(fe25519 *r, const fe25519 *x) 219261287Sdes{ 220261287Sdes fe25519 z2; 221261287Sdes fe25519 z9; 222261287Sdes fe25519 z11; 223261287Sdes fe25519 z2_5_0; 224261287Sdes fe25519 z2_10_0; 225261287Sdes fe25519 z2_20_0; 226261287Sdes fe25519 z2_50_0; 227261287Sdes fe25519 z2_100_0; 228261287Sdes fe25519 t0; 229261287Sdes fe25519 t1; 230261287Sdes int i; 231261287Sdes 232261287Sdes /* 2 */ fe25519_square(&z2,x); 233261287Sdes /* 4 */ fe25519_square(&t1,&z2); 234261287Sdes /* 8 */ fe25519_square(&t0,&t1); 235261287Sdes /* 9 */ fe25519_mul(&z9,&t0,x); 236261287Sdes /* 11 */ fe25519_mul(&z11,&z9,&z2); 237261287Sdes /* 22 */ fe25519_square(&t0,&z11); 238261287Sdes /* 2^5 - 2^0 = 31 */ fe25519_mul(&z2_5_0,&t0,&z9); 239261287Sdes 240261287Sdes /* 2^6 - 2^1 */ fe25519_square(&t0,&z2_5_0); 241261287Sdes /* 2^7 - 2^2 */ fe25519_square(&t1,&t0); 242261287Sdes /* 2^8 - 2^3 */ fe25519_square(&t0,&t1); 243261287Sdes /* 2^9 - 2^4 */ fe25519_square(&t1,&t0); 244261287Sdes /* 2^10 - 2^5 */ fe25519_square(&t0,&t1); 245261287Sdes /* 2^10 - 2^0 */ fe25519_mul(&z2_10_0,&t0,&z2_5_0); 246261287Sdes 247261287Sdes /* 2^11 - 2^1 */ fe25519_square(&t0,&z2_10_0); 248261287Sdes /* 2^12 - 2^2 */ fe25519_square(&t1,&t0); 249261287Sdes /* 2^20 - 2^10 */ for (i = 2;i < 10;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); } 250261287Sdes /* 2^20 - 2^0 */ fe25519_mul(&z2_20_0,&t1,&z2_10_0); 251261287Sdes 252261287Sdes /* 2^21 - 2^1 */ fe25519_square(&t0,&z2_20_0); 253261287Sdes /* 2^22 - 2^2 */ fe25519_square(&t1,&t0); 254261287Sdes /* 2^40 - 2^20 */ for (i = 2;i < 20;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); } 255261287Sdes /* 2^40 - 2^0 */ fe25519_mul(&t0,&t1,&z2_20_0); 256261287Sdes 257261287Sdes /* 2^41 - 2^1 */ fe25519_square(&t1,&t0); 258261287Sdes /* 2^42 - 2^2 */ fe25519_square(&t0,&t1); 259261287Sdes /* 2^50 - 2^10 */ for (i = 2;i < 10;i += 2) { fe25519_square(&t1,&t0); fe25519_square(&t0,&t1); } 260261287Sdes /* 2^50 - 2^0 */ fe25519_mul(&z2_50_0,&t0,&z2_10_0); 261261287Sdes 262261287Sdes /* 2^51 - 2^1 */ fe25519_square(&t0,&z2_50_0); 263261287Sdes /* 2^52 - 2^2 */ fe25519_square(&t1,&t0); 264261287Sdes /* 2^100 - 2^50 */ for (i = 2;i < 50;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); } 265261287Sdes /* 2^100 - 2^0 */ fe25519_mul(&z2_100_0,&t1,&z2_50_0); 266261287Sdes 267261287Sdes /* 2^101 - 2^1 */ fe25519_square(&t1,&z2_100_0); 268261287Sdes /* 2^102 - 2^2 */ fe25519_square(&t0,&t1); 269261287Sdes /* 2^200 - 2^100 */ for (i = 2;i < 100;i += 2) { fe25519_square(&t1,&t0); fe25519_square(&t0,&t1); } 270261287Sdes /* 2^200 - 2^0 */ fe25519_mul(&t1,&t0,&z2_100_0); 271261287Sdes 272261287Sdes /* 2^201 - 2^1 */ fe25519_square(&t0,&t1); 273261287Sdes /* 2^202 - 2^2 */ fe25519_square(&t1,&t0); 274261287Sdes /* 2^250 - 2^50 */ for (i = 2;i < 50;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); } 275261287Sdes /* 2^250 - 2^0 */ fe25519_mul(&t0,&t1,&z2_50_0); 276261287Sdes 277261287Sdes /* 2^251 - 2^1 */ fe25519_square(&t1,&t0); 278261287Sdes /* 2^252 - 2^2 */ fe25519_square(&t0,&t1); 279261287Sdes /* 2^253 - 2^3 */ fe25519_square(&t1,&t0); 280261287Sdes /* 2^254 - 2^4 */ fe25519_square(&t0,&t1); 281261287Sdes /* 2^255 - 2^5 */ fe25519_square(&t1,&t0); 282261287Sdes /* 2^255 - 21 */ fe25519_mul(r,&t1,&z11); 283261287Sdes} 284261287Sdes 285261287Sdesvoid fe25519_pow2523(fe25519 *r, const fe25519 *x) 286261287Sdes{ 287261287Sdes fe25519 z2; 288261287Sdes fe25519 z9; 289261287Sdes fe25519 z11; 290261287Sdes fe25519 z2_5_0; 291261287Sdes fe25519 z2_10_0; 292261287Sdes fe25519 z2_20_0; 293261287Sdes fe25519 z2_50_0; 294261287Sdes fe25519 z2_100_0; 295261287Sdes fe25519 t; 296261287Sdes int i; 297261287Sdes 298261287Sdes /* 2 */ fe25519_square(&z2,x); 299261287Sdes /* 4 */ fe25519_square(&t,&z2); 300261287Sdes /* 8 */ fe25519_square(&t,&t); 301261287Sdes /* 9 */ fe25519_mul(&z9,&t,x); 302261287Sdes /* 11 */ fe25519_mul(&z11,&z9,&z2); 303261287Sdes /* 22 */ fe25519_square(&t,&z11); 304261287Sdes /* 2^5 - 2^0 = 31 */ fe25519_mul(&z2_5_0,&t,&z9); 305261287Sdes 306261287Sdes /* 2^6 - 2^1 */ fe25519_square(&t,&z2_5_0); 307261287Sdes /* 2^10 - 2^5 */ for (i = 1;i < 5;i++) { fe25519_square(&t,&t); } 308261287Sdes /* 2^10 - 2^0 */ fe25519_mul(&z2_10_0,&t,&z2_5_0); 309261287Sdes 310261287Sdes /* 2^11 - 2^1 */ fe25519_square(&t,&z2_10_0); 311261287Sdes /* 2^20 - 2^10 */ for (i = 1;i < 10;i++) { fe25519_square(&t,&t); } 312261287Sdes /* 2^20 - 2^0 */ fe25519_mul(&z2_20_0,&t,&z2_10_0); 313261287Sdes 314261287Sdes /* 2^21 - 2^1 */ fe25519_square(&t,&z2_20_0); 315261287Sdes /* 2^40 - 2^20 */ for (i = 1;i < 20;i++) { fe25519_square(&t,&t); } 316261287Sdes /* 2^40 - 2^0 */ fe25519_mul(&t,&t,&z2_20_0); 317261287Sdes 318261287Sdes /* 2^41 - 2^1 */ fe25519_square(&t,&t); 319261287Sdes /* 2^50 - 2^10 */ for (i = 1;i < 10;i++) { fe25519_square(&t,&t); } 320261287Sdes /* 2^50 - 2^0 */ fe25519_mul(&z2_50_0,&t,&z2_10_0); 321261287Sdes 322261287Sdes /* 2^51 - 2^1 */ fe25519_square(&t,&z2_50_0); 323261287Sdes /* 2^100 - 2^50 */ for (i = 1;i < 50;i++) { fe25519_square(&t,&t); } 324261287Sdes /* 2^100 - 2^0 */ fe25519_mul(&z2_100_0,&t,&z2_50_0); 325261287Sdes 326261287Sdes /* 2^101 - 2^1 */ fe25519_square(&t,&z2_100_0); 327261287Sdes /* 2^200 - 2^100 */ for (i = 1;i < 100;i++) { fe25519_square(&t,&t); } 328261287Sdes /* 2^200 - 2^0 */ fe25519_mul(&t,&t,&z2_100_0); 329261287Sdes 330261287Sdes /* 2^201 - 2^1 */ fe25519_square(&t,&t); 331261287Sdes /* 2^250 - 2^50 */ for (i = 1;i < 50;i++) { fe25519_square(&t,&t); } 332261287Sdes /* 2^250 - 2^0 */ fe25519_mul(&t,&t,&z2_50_0); 333261287Sdes 334261287Sdes /* 2^251 - 2^1 */ fe25519_square(&t,&t); 335261287Sdes /* 2^252 - 2^2 */ fe25519_square(&t,&t); 336261287Sdes /* 2^252 - 3 */ fe25519_mul(r,&t,x); 337261287Sdes} 338