release/src/router/dnscrypt/src/libnacl/crypto_sign/edwards25519sha512batch/ref/fe25519.c

   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   for(i=0;i<32;i++)
 104     r[i] = x->v[i];
 105
 106   /* freeze byte array */
 107   unsigned int m = (r[31] == 127); /* XXX: some compilers might use branches; fix */
 108   for(i=30;i>1;i--)
 109     m *= (r[i] == 255);
 110   m *= (r[0] >= 237);
 111   r[31] -= m*127;
 112   for(i=30;i>0;i--)
 113     r[i] -= m*255;
 114   r[0] -= m*237;
 115 }
 116
 117 void fe25519_cmov(fe25519 *r, const fe25519 *x, unsigned char b)
 118 {
 119   unsigned char nb = 1-b;
 120   int i;
 121   for(i=0;i<32;i++) r->v[i] = nb * r->v[i] + b * x->v[i];
 122 }
 123
 124 unsigned char fe25519_getparity(const fe25519 *x)
 125 {
 126   fe25519 t;
 127   int i;
 128   for(i=0;i<32;i++) t.v[i] = x->v[i];
 129   freeze(&t);
 130   return t.v[0] & 1;
 131 }
 132
 133 void fe25519_setone(fe25519 *r)
 134 {
 135   int i;
 136   r->v[0] = 1;
 137   for(i=1;i<32;i++) r->v[i]=0;
 138 }
 139
 140 void fe25519_setzero(fe25519 *r)
 141 {
 142   int i;
 143   for(i=0;i<32;i++) r->v[i]=0;
 144 }
 145
 146 void fe25519_neg(fe25519 *r, const fe25519 *x)
 147 {
 148   fe25519 t;
 149   int i;
 150   for(i=0;i<32;i++) t.v[i]=x->v[i];
 151   fe25519_setzero(r);
 152   fe25519_sub(r, r, &t);
 153 }
 154
 155 void fe25519_add(fe25519 *r, const fe25519 *x, const fe25519 *y)
 156 {
 157   int i;
 158   for(i=0;i<32;i++) r->v[i] = x->v[i] + y->v[i];
 159   reduce_add_sub(r);
 160 }
 161
 162 void fe25519_sub(fe25519 *r, const fe25519 *x, const fe25519 *y)
 163 {
 164   int i;
 165   crypto_uint32 t[32];
 166   t[0] = x->v[0] + 0x1da;
 167   t[31] = x->v[31] + 0xfe;
 168   for(i=1;i<31;i++) t[i] = x->v[i] + 0x1fe;
 169   for(i=0;i<32;i++) r->v[i] = t[i] - y->v[i];
 170   reduce_add_sub(r);
 171 }
 172
 173 void fe25519_mul(fe25519 *r, const fe25519 *x, const fe25519 *y)
 174 {
 175   int i,j;
 176   crypto_uint32 t[63];
 177   for(i=0;i<63;i++)t[i] = 0;
 178
 179   for(i=0;i<32;i++)
 180     for(j=0;j<32;j++)
 181       t[i+j] += x->v[i] * y->v[j];
 182
 183   for(i=32;i<63;i++)
 184     r->v[i-32] = t[i-32] + 38*t[i];
 185   r->v[31] = t[31]; /* result now in r[0]...r[31] */
 186
 187   reduce_mul(r);
 188 }
 189
 190 void fe25519_square(fe25519 *r, const fe25519 *x)
 191 {
 192   fe25519_mul(r, x, x);
 193 }
 194
 195 /*XXX: Make constant time! */
 196 void fe25519_pow(fe25519 *r, const fe25519 *x, const unsigned char *e)
 197 {
 198   /*
 199   fe25519 g;
 200   fe25519_setone(&g);
 201   int i;
 202   unsigned char j;
 203   for(i=32;i>0;i--)
 204   {
 205     for(j=128;j>0;j>>=1)
 206     {
 207       fe25519_square(&g,&g);
 208       if(e[i-1] & j)
 209         fe25519_mul(&g,&g,x);
 210     }
 211   }
 212   for(i=0;i<32;i++) r->v[i] = g.v[i];
 213   */
 214   fe25519 g;
 215   fe25519_setone(&g);
 216   int i,j,k;
 217   fe25519 pre[(1 << WINDOWSIZE)];
 218   fe25519 t;
 219   unsigned char w;
 220
 221   // Precomputation
 222   fe25519_setone(pre);
 223   pre[1] = *x;
 224   for(i=2;i<(1<<WINDOWSIZE);i+=2)
 225   {
 226     fe25519_square(pre+i, pre+i/2);
 227     fe25519_mul(pre+i+1, pre+i, pre+1);
 228   }
 229
 230   // Fixed-window scalar multiplication
 231   for(i=32;i>0;i--)
 232   {
 233     for(j=8-WINDOWSIZE;j>=0;j-=WINDOWSIZE)
 234     {
 235       for(k=0;k<WINDOWSIZE;k++)
 236         fe25519_square(&g, &g);
 237       // Cache-timing resistant loading of precomputed value:
 238       w = (e[i-1]>>j) & WINDOWMASK;
 239       t = pre[0];
 240       for(k=1;k<(1<<WINDOWSIZE);k++)
 241         fe25519_cmov(&t, &pre[k], k==w);
 242       fe25519_mul(&g, &g, &t);
 243     }
 244   }
 245   *r = g;
 246 }
 247
 248 /* Return 0 on success, 1 otherwise */
 249 int fe25519_sqrt_vartime(fe25519 *r, const fe25519 *x, unsigned char parity)
 250 {
 251   /* See HAC, Alg. 3.37 */
 252   if (!issquare(x)) return -1;
 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   fe25519_pow(&d,x,e);
 260   freeze(&d);
 261   if(isone(&d))
 262     fe25519_pow(r,x,e2);
 263   else
 264   {
 265     for(i=0;i<32;i++)
 266       d.v[i] = 4*x->v[i];
 267     fe25519_pow(&d,&d,e3);
 268     for(i=0;i<32;i++)
 269       r->v[i] = 2*x->v[i];
 270     fe25519_mul(r,r,&d);
 271   }
 272   freeze(r);
 273   if((r->v[0] & 1) != (parity & 1))
 274   {
 275     fe25519_sub(r,&p,r);
 276   }
 277   return 0;
 278 }
 279
 280 void fe25519_invert(fe25519 *r, const fe25519 *x)
 281 {
 282         fe25519 z2;
 283         fe25519 z9;
 284         fe25519 z11;
 285         fe25519 z2_5_0;
 286         fe25519 z2_10_0;
 287         fe25519 z2_20_0;
 288         fe25519 z2_50_0;
 289         fe25519 z2_100_0;
 290         fe25519 t0;
 291         fe25519 t1;
 292         int i;
 293
 294         /* 2 */ fe25519_square(&z2,x);
 295         /* 4 */ fe25519_square(&t1,&z2);
 296         /* 8 */ fe25519_square(&t0,&t1);
 297         /* 9 */ fe25519_mul(&z9,&t0,x);
 298         /* 11 */ fe25519_mul(&z11,&z9,&z2);
 299         /* 22 */ fe25519_square(&t0,&z11);
 300         /* 2^5 - 2^0 = 31 */ fe25519_mul(&z2_5_0,&t0,&z9);
 301
 302         /* 2^6 - 2^1 */ fe25519_square(&t0,&z2_5_0);
 303         /* 2^7 - 2^2 */ fe25519_square(&t1,&t0);
 304         /* 2^8 - 2^3 */ fe25519_square(&t0,&t1);
 305         /* 2^9 - 2^4 */ fe25519_square(&t1,&t0);
 306         /* 2^10 - 2^5 */ fe25519_square(&t0,&t1);
 307         /* 2^10 - 2^0 */ fe25519_mul(&z2_10_0,&t0,&z2_5_0);
 308
 309         /* 2^11 - 2^1 */ fe25519_square(&t0,&z2_10_0);
 310         /* 2^12 - 2^2 */ fe25519_square(&t1,&t0);
 311         /* 2^20 - 2^10 */ for (i = 2;i < 10;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
 312         /* 2^20 - 2^0 */ fe25519_mul(&z2_20_0,&t1,&z2_10_0);
 313
 314         /* 2^21 - 2^1 */ fe25519_square(&t0,&z2_20_0);
 315         /* 2^22 - 2^2 */ fe25519_square(&t1,&t0);
 316         /* 2^40 - 2^20 */ for (i = 2;i < 20;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
 317         /* 2^40 - 2^0 */ fe25519_mul(&t0,&t1,&z2_20_0);
 318
 319         /* 2^41 - 2^1 */ fe25519_square(&t1,&t0);
 320         /* 2^42 - 2^2 */ fe25519_square(&t0,&t1);
 321         /* 2^50 - 2^10 */ for (i = 2;i < 10;i += 2) { fe25519_square(&t1,&t0); fe25519_square(&t0,&t1); }
 322         /* 2^50 - 2^0 */ fe25519_mul(&z2_50_0,&t0,&z2_10_0);
 323
 324         /* 2^51 - 2^1 */ fe25519_square(&t0,&z2_50_0);
 325         /* 2^52 - 2^2 */ fe25519_square(&t1,&t0);
 326         /* 2^100 - 2^50 */ for (i = 2;i < 50;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
 327         /* 2^100 - 2^0 */ fe25519_mul(&z2_100_0,&t1,&z2_50_0);
 328
 329         /* 2^101 - 2^1 */ fe25519_square(&t1,&z2_100_0);
 330         /* 2^102 - 2^2 */ fe25519_square(&t0,&t1);
 331         /* 2^200 - 2^100 */ for (i = 2;i < 100;i += 2) { fe25519_square(&t1,&t0); fe25519_square(&t0,&t1); }
 332         /* 2^200 - 2^0 */ fe25519_mul(&t1,&t0,&z2_100_0);
 333
 334         /* 2^201 - 2^1 */ fe25519_square(&t0,&t1);
 335         /* 2^202 - 2^2 */ fe25519_square(&t1,&t0);
 336         /* 2^250 - 2^50 */ for (i = 2;i < 50;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
 337         /* 2^250 - 2^0 */ fe25519_mul(&t0,&t1,&z2_50_0);
 338
 339         /* 2^251 - 2^1 */ fe25519_square(&t1,&t0);
 340         /* 2^252 - 2^2 */ fe25519_square(&t0,&t1);
 341         /* 2^253 - 2^3 */ fe25519_square(&t1,&t0);
 342         /* 2^254 - 2^4 */ fe25519_square(&t0,&t1);
 343         /* 2^255 - 2^5 */ fe25519_square(&t1,&t0);
 344         /* 2^255 - 21 */ fe25519_mul(r,&t1,&z11);
 345 }