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

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