crypto/openssh/sc25519.c

   1 /* $OpenBSD: sc25519.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/sc25519.c
   7  */
   8
   9 #include "includes.h"
  10
  11 #include "sc25519.h"
  12
  13 /*Arithmetic modulo the group order m = 2^252 +  27742317777372353535851937790883648493 = 7237005577332262213973186563042994240857116359379907606001950938285454250989 */
  14
  15 static const crypto_uint32 m[32] = {0xED, 0xD3, 0xF5, 0x5C, 0x1A, 0x63, 0x12, 0x58, 0xD6, 0x9C, 0xF7, 0xA2, 0xDE, 0xF9, 0xDE, 0x14,
  16                                     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10};
  17
  18 static const crypto_uint32 mu[33] = {0x1B, 0x13, 0x2C, 0x0A, 0xA3, 0xE5, 0x9C, 0xED, 0xA7, 0x29, 0x63, 0x08, 0x5D, 0x21, 0x06, 0x21,
  19                                      0xEB, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x0F};
  20
  21 static crypto_uint32 lt(crypto_uint32 a,crypto_uint32 b) /* 16-bit inputs */
  22 {
  23   unsigned int x = a;
  24   x -= (unsigned int) b; /* 0..65535: no; 4294901761..4294967295: yes */
  25   x >>= 31; /* 0: no; 1: yes */
  26   return x;
  27 }
  28
  29 /* Reduce coefficients of r before calling reduce_add_sub */
  30 static void reduce_add_sub(sc25519 *r)
  31 {
  32   crypto_uint32 pb = 0;
  33   crypto_uint32 b;
  34   crypto_uint32 mask;
  35   int i;
  36   unsigned char t[32];
  37
  38   for(i=0;i<32;i++)
  39   {
  40     pb += m[i];
  41     b = lt(r->v[i],pb);
  42     t[i] = r->v[i]-pb+(b<<8);
  43     pb = b;
  44   }
  45   mask = b - 1;
  46   for(i=0;i<32;i++)
  47     r->v[i] ^= mask & (r->v[i] ^ t[i]);
  48 }
  49
  50 /* Reduce coefficients of x before calling barrett_reduce */
  51 static void barrett_reduce(sc25519 *r, const crypto_uint32 x[64])
  52 {
  53   /* See HAC, Alg. 14.42 */
  54   int i,j;
  55   crypto_uint32 q2[66];
  56   crypto_uint32 *q3 = q2 + 33;
  57   crypto_uint32 r1[33];
  58   crypto_uint32 r2[33];
  59   crypto_uint32 carry;
  60   crypto_uint32 pb = 0;
  61   crypto_uint32 b;
  62
  63   for (i = 0;i < 66;++i) q2[i] = 0;
  64   for (i = 0;i < 33;++i) r2[i] = 0;
  65
  66   for(i=0;i<33;i++)
  67     for(j=0;j<33;j++)
  68       if(i+j >= 31) q2[i+j] += mu[i]*x[j+31];
  69   carry = q2[31] >> 8;
  70   q2[32] += carry;
  71   carry = q2[32] >> 8;
  72   q2[33] += carry;
  73
  74   for(i=0;i<33;i++)r1[i] = x[i];
  75   for(i=0;i<32;i++)
  76     for(j=0;j<33;j++)
  77       if(i+j < 33) r2[i+j] += m[i]*q3[j];
  78
  79   for(i=0;i<32;i++)
  80   {
  81     carry = r2[i] >> 8;
  82     r2[i+1] += carry;
  83     r2[i] &= 0xff;
  84   }
  85
  86   for(i=0;i<32;i++)
  87   {
  88     pb += r2[i];
  89     b = lt(r1[i],pb);
  90     r->v[i] = r1[i]-pb+(b<<8);
  91     pb = b;
  92   }
  93
  94   /* XXX: Can it really happen that r<0?, See HAC, Alg 14.42, Step 3
  95    * If so: Handle  it here!
  96    */
  97
  98   reduce_add_sub(r);
  99   reduce_add_sub(r);
 100 }
 101
 102 void sc25519_from32bytes(sc25519 *r, const unsigned char x[32])
 103 {
 104   int i;
 105   crypto_uint32 t[64];
 106   for(i=0;i<32;i++) t[i] = x[i];
 107   for(i=32;i<64;++i) t[i] = 0;
 108   barrett_reduce(r, t);
 109 }
 110
 111 void shortsc25519_from16bytes(shortsc25519 *r, const unsigned char x[16])
 112 {
 113   int i;
 114   for(i=0;i<16;i++) r->v[i] = x[i];
 115 }
 116
 117 void sc25519_from64bytes(sc25519 *r, const unsigned char x[64])
 118 {
 119   int i;
 120   crypto_uint32 t[64];
 121   for(i=0;i<64;i++) t[i] = x[i];
 122   barrett_reduce(r, t);
 123 }
 124
 125 void sc25519_from_shortsc(sc25519 *r, const shortsc25519 *x)
 126 {
 127   int i;
 128   for(i=0;i<16;i++)
 129     r->v[i] = x->v[i];
 130   for(i=0;i<16;i++)
 131     r->v[16+i] = 0;
 132 }
 133
 134 void sc25519_to32bytes(unsigned char r[32], const sc25519 *x)
 135 {
 136   int i;
 137   for(i=0;i<32;i++) r[i] = x->v[i];
 138 }
 139
 140 int sc25519_iszero_vartime(const sc25519 *x)
 141 {
 142   int i;
 143   for(i=0;i<32;i++)
 144     if(x->v[i] != 0) return 0;
 145   return 1;
 146 }
 147
 148 int sc25519_isshort_vartime(const sc25519 *x)
 149 {
 150   int i;
 151   for(i=31;i>15;i--)
 152     if(x->v[i] != 0) return 0;
 153   return 1;
 154 }
 155
 156 int sc25519_lt_vartime(const sc25519 *x, const sc25519 *y)
 157 {
 158   int i;
 159   for(i=31;i>=0;i--)
 160   {
 161     if(x->v[i] < y->v[i]) return 1;
 162     if(x->v[i] > y->v[i]) return 0;
 163   }
 164   return 0;
 165 }
 166
 167 void sc25519_add(sc25519 *r, const sc25519 *x, const sc25519 *y)
 168 {
 169   int i, carry;
 170   for(i=0;i<32;i++) r->v[i] = x->v[i] + y->v[i];
 171   for(i=0;i<31;i++)
 172   {
 173     carry = r->v[i] >> 8;
 174     r->v[i+1] += carry;
 175     r->v[i] &= 0xff;
 176   }
 177   reduce_add_sub(r);
 178 }
 179
 180 void sc25519_sub_nored(sc25519 *r, const sc25519 *x, const sc25519 *y)
 181 {
 182   crypto_uint32 b = 0;
 183   crypto_uint32 t;
 184   int i;
 185   for(i=0;i<32;i++)
 186   {
 187     t = x->v[i] - y->v[i] - b;
 188     r->v[i] = t & 255;
 189     b = (t >> 8) & 1;
 190   }
 191 }
 192
 193 void sc25519_mul(sc25519 *r, const sc25519 *x, const sc25519 *y)
 194 {
 195   int i,j,carry;
 196   crypto_uint32 t[64];
 197   for(i=0;i<64;i++)t[i] = 0;
 198
 199   for(i=0;i<32;i++)
 200     for(j=0;j<32;j++)
 201       t[i+j] += x->v[i] * y->v[j];
 202
 203   /* Reduce coefficients */
 204   for(i=0;i<63;i++)
 205   {
 206     carry = t[i] >> 8;
 207     t[i+1] += carry;
 208     t[i] &= 0xff;
 209   }
 210
 211   barrett_reduce(r, t);
 212 }
 213
 214 void sc25519_mul_shortsc(sc25519 *r, const sc25519 *x, const shortsc25519 *y)
 215 {
 216   sc25519 t;
 217   sc25519_from_shortsc(&t, y);
 218   sc25519_mul(r, x, &t);
 219 }
 220
 221 void sc25519_window3(signed char r[85], const sc25519 *s)
 222 {
 223   char carry;
 224   int i;
 225   for(i=0;i<10;i++)
 226   {
 227     r[8*i+0]  =  s->v[3*i+0]       & 7;
 228     r[8*i+1]  = (s->v[3*i+0] >> 3) & 7;
 229     r[8*i+2]  = (s->v[3*i+0] >> 6) & 7;
 230     r[8*i+2] ^= (s->v[3*i+1] << 2) & 7;
 231     r[8*i+3]  = (s->v[3*i+1] >> 1) & 7;
 232     r[8*i+4]  = (s->v[3*i+1] >> 4) & 7;
 233     r[8*i+5]  = (s->v[3*i+1] >> 7) & 7;
 234     r[8*i+5] ^= (s->v[3*i+2] << 1) & 7;
 235     r[8*i+6]  = (s->v[3*i+2] >> 2) & 7;
 236     r[8*i+7]  = (s->v[3*i+2] >> 5) & 7;
 237   }
 238   r[8*i+0]  =  s->v[3*i+0]       & 7;
 239   r[8*i+1]  = (s->v[3*i+0] >> 3) & 7;
 240   r[8*i+2]  = (s->v[3*i+0] >> 6) & 7;
 241   r[8*i+2] ^= (s->v[3*i+1] << 2) & 7;
 242   r[8*i+3]  = (s->v[3*i+1] >> 1) & 7;
 243   r[8*i+4]  = (s->v[3*i+1] >> 4) & 7;
 244
 245   /* Making it signed */
 246   carry = 0;
 247   for(i=0;i<84;i++)
 248   {
 249     r[i] += carry;
 250     r[i+1] += r[i] >> 3;
 251     r[i] &= 7;
 252     carry = r[i] >> 2;
 253     r[i] -= carry<<3;
 254   }
 255   r[84] += carry;
 256 }
 257
 258 void sc25519_window5(signed char r[51], const sc25519 *s)
 259 {
 260   char carry;
 261   int i;
 262   for(i=0;i<6;i++)
 263   {
 264     r[8*i+0]  =  s->v[5*i+0]       & 31;
 265     r[8*i+1]  = (s->v[5*i+0] >> 5) & 31;
 266     r[8*i+1] ^= (s->v[5*i+1] << 3) & 31;
 267     r[8*i+2]  = (s->v[5*i+1] >> 2) & 31;
 268     r[8*i+3]  = (s->v[5*i+1] >> 7) & 31;
 269     r[8*i+3] ^= (s->v[5*i+2] << 1) & 31;
 270     r[8*i+4]  = (s->v[5*i+2] >> 4) & 31;
 271     r[8*i+4] ^= (s->v[5*i+3] << 4) & 31;
 272     r[8*i+5]  = (s->v[5*i+3] >> 1) & 31;
 273     r[8*i+6]  = (s->v[5*i+3] >> 6) & 31;
 274     r[8*i+6] ^= (s->v[5*i+4] << 2) & 31;
 275     r[8*i+7]  = (s->v[5*i+4] >> 3) & 31;
 276   }
 277   r[8*i+0]  =  s->v[5*i+0]       & 31;
 278   r[8*i+1]  = (s->v[5*i+0] >> 5) & 31;
 279   r[8*i+1] ^= (s->v[5*i+1] << 3) & 31;
 280   r[8*i+2]  = (s->v[5*i+1] >> 2) & 31;
 281
 282   /* Making it signed */
 283   carry = 0;
 284   for(i=0;i<50;i++)
 285   {
 286     r[i] += carry;
 287     r[i+1] += r[i] >> 5;
 288     r[i] &= 31;
 289     carry = r[i] >> 4;
 290     r[i] -= carry<<5;
 291   }
 292   r[50] += carry;
 293 }
 294
 295 void sc25519_2interleave2(unsigned char r[127], const sc25519 *s1, const sc25519 *s2)
 296 {
 297   int i;
 298   for(i=0;i<31;i++)
 299   {
 300     r[4*i]   = ( s1->v[i]       & 3) ^ (( s2->v[i]       & 3) << 2);
 301     r[4*i+1] = ((s1->v[i] >> 2) & 3) ^ (((s2->v[i] >> 2) & 3) << 2);
 302     r[4*i+2] = ((s1->v[i] >> 4) & 3) ^ (((s2->v[i] >> 4) & 3) << 2);
 303     r[4*i+3] = ((s1->v[i] >> 6) & 3) ^ (((s2->v[i] >> 6) & 3) << 2);
 304   }
 305   r[124] = ( s1->v[31]       & 3) ^ (( s2->v[31]       & 3) << 2);
 306   r[125] = ((s1->v[31] >> 2) & 3) ^ (((s2->v[31] >> 2) & 3) << 2);
 307   r[126] = ((s1->v[31] >> 4) & 3) ^ (((s2->v[31] >> 4) & 3) << 2);
 308 }