crypto/openssh/fe25519.c

   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 }