gerrit.fd Code Review - trex.git/blob

   1 #include "fe25519.h"
   2
   3 #define WINDOWSIZE 4 /* Should be 1,2, or 4 */
   4 #define WINDOWMASK ((1<<WINDOWSIZE)-1)
   5
   6 static void reduce_add_sub(fe25519 *r)
   7 {
   8   crypto_uint32 t;
   9   int i,rep;
  10
  11   for(rep=0;rep<4;rep++)
  12   {
  13     t = r->v[31] >> 7;
  14     r->v[31] &= 127;
  15     t *= 19;
  16     r->v[0] += t;
  17     for(i=0;i<31;i++)
  18     {
  19       t = r->v[i] >> 8;
  20       r->v[i+1] += t;
  21       r->v[i] &= 255;
  22     }
  23   }
  24 }
  25
  26 static void reduce_mul(fe25519 *r)
  27 {
  28   crypto_uint32 t;
  29   int i,rep;
  30
  31   for(rep=0;rep<2;rep++)
  32   {
  33     t = r->v[31] >> 7;
  34     r->v[31] &= 127;
  35     t *= 19;
  36     r->v[0] += t;
  37     for(i=0;i<31;i++)
  38     {
  39       t = r->v[i] >> 8;
  40       r->v[i+1] += t;
  41       r->v[i] &= 255;
  42     }
  43   }
  44 }
  45
  46 /* reduction modulo 2^255-19 */
  47 static void freeze(fe25519 *r)
  48 {
  49   int i;
  50   unsigned int m = (r->v[31] == 127);
  51   for(i=30;i>1;i--)
  52     m *= (r->v[i] == 255);
  53   m *= (r->v[0] >= 237);
  54
  55   r->v[31] -= m*127;
  56   for(i=30;i>0;i--)
  57     r->v[i] -= m*255;
  58   r->v[0] -= m*237;
  59 }
  60
  61 /*freeze input before calling isone*/
  62 static int isone(const fe25519 *x)
  63 {
  64   int i;
  65   int r = (x->v[0] == 1);
  66   for(i=1;i<32;i++)
  67     r *= (x->v[i] == 0);
  68   return r;
  69 }
  70
  71 /*freeze input before calling iszero*/
  72 static int iszero(const fe25519 *x)
  73 {
  74   int i;
  75   int r = (x->v[0] == 0);
  76   for(i=1;i<32;i++)
  77     r *= (x->v[i] == 0);
  78   return r;
  79 }
  80
  81
  82 static int issquare(const fe25519 *x)
  83 {
  84   unsigned char e[32] = {0xf6,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0x3f}; /* (p-1)/2 */
  85   fe25519 t;
  86
  87   fe25519_pow(&t,x,e);
  88   freeze(&t);
  89   return isone(&t) || iszero(&t);
  90 }
  91
  92 void fe25519_unpack(fe25519 *r, const unsigned char x[32])
  93 {
  94   int i;
  95   for(i=0;i<32;i++) r->v[i] = x[i];
  96   r->v[31] &= 127;
  97 }
  98
  99 /* Assumes input x being reduced mod 2^255 */
 100 void fe25519_pack(unsigned char r[32], const fe25519 *x)
 101 {
 102   int i;
 103   unsigned int m;
 104   for(i=0;i<32;i++)
 105     r[i] = x->v[i];
 106
 107   /* freeze byte array */
 108   m = (r[31] == 127); /* XXX: some compilers might use branches; fix */
 109   for(i=30;i>1;i--)
 110     m *= (r[i] == 255);
 111   m *= (r[0] >= 237);
 112   r[31] -= m*127;
 113   for(i=30;i>0;i--)
 114     r[i] -= m*255;
 115   r[0] -= m*237;
 116 }
 117
 118 void fe25519_cmov(fe25519 *r, const fe25519 *x, unsigned char b)
 119 {
 120   unsigned char nb = 1-b;
 121   int i;
 122   for(i=0;i<32;i++) r->v[i] = nb * r->v[i] + b * x->v[i];
 123 }
 124
 125 unsigned char fe25519_getparity(const fe25519 *x)
 126 {
 127   fe25519 t;
 128   int i;
 129   for(i=0;i<32;i++) t.v[i] = x->v[i];
 130   freeze(&t);
 131   return t.v[0] & 1;
 132 }
 133
 134 void fe25519_setone(fe25519 *r)
 135 {
 136   int i;
 137   r->v[0] = 1;
 138   for(i=1;i<32;i++) r->v[i]=0;
 139 }
 140
 141 void fe25519_setzero(fe25519 *r)
 142 {
 143   int i;
 144   for(i=0;i<32;i++) r->v[i]=0;
 145 }
 146
 147 void fe25519_neg(fe25519 *r, const fe25519 *x)
 148 {
 149   fe25519 t;
 150   int i;
 151   for(i=0;i<32;i++) t.v[i]=x->v[i];
 152   fe25519_setzero(r);
 153   fe25519_sub(r, r, &t);
 154 }
 155
 156 void fe25519_add(fe25519 *r, const fe25519 *x, const fe25519 *y)
 157 {
 158   int i;
 159   for(i=0;i<32;i++) r->v[i] = x->v[i] + y->v[i];
 160   reduce_add_sub(r);
 161 }
 162
 163 void fe25519_sub(fe25519 *r, const fe25519 *x, const fe25519 *y)
 164 {
 165   int i;
 166   crypto_uint32 t[32];
 167   t[0] = x->v[0] + 0x1da;
 168   t[31] = x->v[31] + 0xfe;
 169   for(i=1;i<31;i++) t[i] = x->v[i] + 0x1fe;
 170   for(i=0;i<32;i++) r->v[i] = t[i] - y->v[i];
 171   reduce_add_sub(r);
 172 }
 173
 174 void fe25519_mul(fe25519 *r, const fe25519 *x, const fe25519 *y)
 175 {
 176   int i,j;
 177   crypto_uint32 t[63];
 178   for(i=0;i<63;i++)t[i] = 0;
 179
 180   for(i=0;i<32;i++)
 181     for(j=0;j<32;j++)
 182       t[i+j] += x->v[i] * y->v[j];
 183
 184   for(i=32;i<63;i++)
 185     r->v[i-32] = t[i-32] + 38*t[i];
 186   r->v[31] = t[31]; /* result now in r[0]...r[31] */
 187
 188   reduce_mul(r);
 189 }
 190
 191 void fe25519_square(fe25519 *r, const fe25519 *x)
 192 {
 193   fe25519_mul(r, x, x);
 194 }
 195
 196 /*XXX: Make constant time! */
 197 void fe25519_pow(fe25519 *r, const fe25519 *x, const unsigned char *e)
 198 {
 199   /*
 200   fe25519 g;
 201   fe25519_setone(&g);
 202   int i;
 203   unsigned char j;
 204   for(i=32;i>0;i--)
 205   {
 206     for(j=128;j>0;j>>=1)
 207     {
 208       fe25519_square(&g,&g);
 209       if(e[i-1] & j)
 210         fe25519_mul(&g,&g,x);
 211     }
 212   }
 213   for(i=0;i<32;i++) r->v[i] = g.v[i];
 214   */
 215   fe25519 g;
 216   int i,j,k;
 217   fe25519 t;
 218   unsigned char w;
 219   fe25519 pre[(1 << WINDOWSIZE)];
 220
 221   fe25519_setone(&g);
 222
 223   // Precomputation
 224   fe25519_setone(pre);
 225   pre[1] = *x;
 226   for(i=2;i<(1<<WINDOWSIZE);i+=2)
 227   {
 228     fe25519_square(pre+i, pre+i/2);
 229     fe25519_mul(pre+i+1, pre+i, pre+1);
 230   }
 231
 232   // Fixed-window scalar multiplication
 233   for(i=32;i>0;i--)
 234   {
 235     for(j=8-WINDOWSIZE;j>=0;j-=WINDOWSIZE)
 236     {
 237       for(k=0;k<WINDOWSIZE;k++)
 238         fe25519_square(&g, &g);
 239       // Cache-timing resistant loading of precomputed value:
 240       w = (e[i-1]>>j) & WINDOWMASK;
 241       t = pre[0];
 242       for(k=1;k<(1<<WINDOWSIZE);k++)
 243         fe25519_cmov(&t, &pre[k], k==w);
 244       fe25519_mul(&g, &g, &t);
 245     }
 246   }
 247   *r = g;
 248 }
 249
 250 /* Return 0 on success, 1 otherwise */
 251 int fe25519_sqrt_vartime(fe25519 *r, const fe25519 *x, unsigned char parity)
 252 {
 253   unsigned char e[32] = {0xfb,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0x1f}; /* (p-1)/4 */
 254   unsigned char e2[32] = {0xfe,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0x0f}; /* (p+3)/8 */
 255   unsigned char e3[32] = {0xfd,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0x0f}; /* (p-5)/8 */
 256   fe25519 p = {{0}};
 257   fe25519 d;
 258   int i;
 259
 260   /* See HAC, Alg. 3.37 */
 261   if (!issquare(x)) return -1;
 262   fe25519_pow(&d,x,e);
 263   freeze(&d);
 264   if(isone(&d))
 265     fe25519_pow(r,x,e2);
 266   else
 267   {
 268     for(i=0;i<32;i++)
 269       d.v[i] = 4*x->v[i];
 270     fe25519_pow(&d,&d,e3);
 271     for(i=0;i<32;i++)
 272       r->v[i] = 2*x->v[i];
 273     fe25519_mul(r,r,&d);
 274   }
 275   freeze(r);
 276   if((r->v[0] & 1) != (parity & 1))
 277   {
 278     fe25519_sub(r,&p,r);
 279   }
 280   return 0;
 281 }
 282
 283 void fe25519_invert(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 t0;
 294         fe25519 t1;
 295         int i;
 296
 297         /* 2 */ fe25519_square(&z2,x);
 298         /* 4 */ fe25519_square(&t1,&z2);
 299         /* 8 */ fe25519_square(&t0,&t1);
 300         /* 9 */ fe25519_mul(&z9,&t0,x);
 301         /* 11 */ fe25519_mul(&z11,&z9,&z2);
 302         /* 22 */ fe25519_square(&t0,&z11);
 303         /* 2^5 - 2^0 = 31 */ fe25519_mul(&z2_5_0,&t0,&z9);
 304
 305         /* 2^6 - 2^1 */ fe25519_square(&t0,&z2_5_0);
 306         /* 2^7 - 2^2 */ fe25519_square(&t1,&t0);
 307         /* 2^8 - 2^3 */ fe25519_square(&t0,&t1);
 308         /* 2^9 - 2^4 */ fe25519_square(&t1,&t0);
 309         /* 2^10 - 2^5 */ fe25519_square(&t0,&t1);
 310         /* 2^10 - 2^0 */ fe25519_mul(&z2_10_0,&t0,&z2_5_0);
 311
 312         /* 2^11 - 2^1 */ fe25519_square(&t0,&z2_10_0);
 313         /* 2^12 - 2^2 */ fe25519_square(&t1,&t0);
 314         /* 2^20 - 2^10 */ for (i = 2;i < 10;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
 315         /* 2^20 - 2^0 */ fe25519_mul(&z2_20_0,&t1,&z2_10_0);
 316
 317         /* 2^21 - 2^1 */ fe25519_square(&t0,&z2_20_0);
 318         /* 2^22 - 2^2 */ fe25519_square(&t1,&t0);
 319         /* 2^40 - 2^20 */ for (i = 2;i < 20;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
 320         /* 2^40 - 2^0 */ fe25519_mul(&t0,&t1,&z2_20_0);
 321
 322         /* 2^41 - 2^1 */ fe25519_square(&t1,&t0);
 323         /* 2^42 - 2^2 */ fe25519_square(&t0,&t1);
 324         /* 2^50 - 2^10 */ for (i = 2;i < 10;i += 2) { fe25519_square(&t1,&t0); fe25519_square(&t0,&t1); }
 325         /* 2^50 - 2^0 */ fe25519_mul(&z2_50_0,&t0,&z2_10_0);
 326
 327         /* 2^51 - 2^1 */ fe25519_square(&t0,&z2_50_0);
 328         /* 2^52 - 2^2 */ fe25519_square(&t1,&t0);
 329         /* 2^100 - 2^50 */ for (i = 2;i < 50;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
 330         /* 2^100 - 2^0 */ fe25519_mul(&z2_100_0,&t1,&z2_50_0);
 331
 332         /* 2^101 - 2^1 */ fe25519_square(&t1,&z2_100_0);
 333         /* 2^102 - 2^2 */ fe25519_square(&t0,&t1);
 334         /* 2^200 - 2^100 */ for (i = 2;i < 100;i += 2) { fe25519_square(&t1,&t0); fe25519_square(&t0,&t1); }
 335         /* 2^200 - 2^0 */ fe25519_mul(&t1,&t0,&z2_100_0);
 336
 337         /* 2^201 - 2^1 */ fe25519_square(&t0,&t1);
 338         /* 2^202 - 2^2 */ fe25519_square(&t1,&t0);
 339         /* 2^250 - 2^50 */ for (i = 2;i < 50;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
 340         /* 2^250 - 2^0 */ fe25519_mul(&t0,&t1,&z2_50_0);
 341
 342         /* 2^251 - 2^1 */ fe25519_square(&t1,&t0);
 343         /* 2^252 - 2^2 */ fe25519_square(&t0,&t1);
 344         /* 2^253 - 2^3 */ fe25519_square(&t1,&t0);
 345         /* 2^254 - 2^4 */ fe25519_square(&t0,&t1);
 346         /* 2^255 - 2^5 */ fe25519_square(&t1,&t0);
 347         /* 2^255 - 21 */ fe25519_mul(r,&t1,&z11);
 348 }