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