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