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 <libwebsockets.h> 10 11#include "sc25519.h" 12 13/*Arithmetic modulo the group order m = 2^252 + 27742317777372353535851937790883648493 = 7237005577332262213973186563042994240857116359379907606001950938285454250989 */ 14 15static const uint32_t 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 18static const uint32_t 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 21static uint32_t lt(uint32_t a,uint32_t 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 sc_reduce_add_sub */ 30static void sc_reduce_add_sub(sc25519 *r) 31{ 32 uint32_t pb = 0; 33 uint32_t b; 34 uint32_t 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] = (unsigned char)(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 */ 51static void barrett_reduce(sc25519 *r, const uint32_t x[64]) 52{ 53 /* See HAC, Alg. 14.42 */ 54 int i,j; 55 uint32_t q2[66]; 56 uint32_t *q3 = q2 + 33; 57 uint32_t r1[33]; 58 uint32_t r2[33]; 59 uint32_t carry; 60 uint32_t pb = 0; 61 uint32_t 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 sc_reduce_add_sub(r); 99 sc_reduce_add_sub(r); 100} 101 102void sc25519_from32bytes(sc25519 *r, const unsigned char x[32]) 103{ 104 int i; 105 uint32_t 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 111void 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 117void sc25519_from64bytes(sc25519 *r, const unsigned char x[64]) 118{ 119 int i; 120 uint32_t t[64]; 121 for(i=0;i<64;i++) t[i] = x[i]; 122 barrett_reduce(r, t); 123} 124 125void 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 134void sc25519_to32bytes(unsigned char r[32], const sc25519 *x) 135{ 136 int i; 137 for(i=0;i<32;i++) r[i] = (unsigned char)x->v[i]; 138} 139 140int 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 148int 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 156int 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 167void 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 = (int)r->v[i] >> 8; 174 r->v[i+1] += (uint32_t)carry; 175 r->v[i] &= 0xff; 176 } 177 sc_reduce_add_sub(r); 178} 179 180void sc25519_sub_nored(sc25519 *r, const sc25519 *x, const sc25519 *y) 181{ 182 uint32_t b = 0; 183 int i; 184 for(i=0;i<32;i++) 185 { 186 uint32_t t = x->v[i] - y->v[i] - b; 187 r->v[i] = t & 255; 188 b = (t >> 8) & 1; 189 } 190} 191 192void sc25519_mul(sc25519 *r, const sc25519 *x, const sc25519 *y) 193{ 194 int i,j,carry; 195 uint32_t t[64]; 196 for(i=0;i<64;i++)t[i] = 0; 197 198 for(i=0;i<32;i++) 199 for(j=0;j<32;j++) 200 t[i+j] += x->v[i] * y->v[j]; 201 202 /* Reduce coefficients */ 203 for(i=0;i<63;i++) 204 { 205 carry = (int)t[i] >> 8; 206 t[i+1] += (uint32_t)carry; 207 t[i] &= 0xff; 208 } 209 210 barrett_reduce(r, t); 211} 212 213void sc25519_mul_shortsc(sc25519 *r, const sc25519 *x, const shortsc25519 *y) 214{ 215 sc25519 t; 216 sc25519_from_shortsc(&t, y); 217 sc25519_mul(r, x, &t); 218} 219 220void sc25519_window3(signed char r[85], const sc25519 *s) 221{ 222 char carry; 223 int i; 224 for(i=0;i<10;i++) 225 { 226 r[8*i+0] = s->v[3*i+0] & 7; 227 r[8*i+1] = (s->v[3*i+0] >> 3) & 7; 228 r[8*i+2] = (s->v[3*i+0] >> 6) & 7; 229 r[8*i+2] = (signed char)(r[8*i+2] ^ (int)((s->v[3*i+1] << 2) & 7)); 230 r[8*i+3] = (s->v[3*i+1] >> 1) & 7; 231 r[8*i+4] = (s->v[3*i+1] >> 4) & 7; 232 r[8*i+5] = (s->v[3*i+1] >> 7) & 7; 233 r[8*i+5] = (signed char)(r[8*i+5] ^ (int)((s->v[3*i+2] << 1) & 7)); 234 r[8*i+6] = (s->v[3*i+2] >> 2) & 7; 235 r[8*i+7] = (s->v[3*i+2] >> 5) & 7; 236 } 237 r[8*i+0] = s->v[3*i+0] & 7; 238 r[8*i+1] = (s->v[3*i+0] >> 3) & 7; 239 r[8*i+2] = (s->v[3*i+0] >> 6) & 7; 240 r[8*i+2] = (signed char)(r[8*i+2] ^ (int)((s->v[3*i+1] << 2) & 7)); 241 r[8*i+3] = (s->v[3*i+1] >> 1) & 7; 242 r[8*i+4] = (s->v[3*i+1] >> 4) & 7; 243 244 /* Making it signed */ 245 carry = 0; 246 for(i=0;i<84;i++) 247 { 248 r[i] = (signed char)(r[i] + carry); 249 r[i+1] = (signed char)(r[i + 1] + (r[i] >> 3)); 250 r[i] &= 7; 251 carry = (char)(r[i] >> 2); 252 r[i] = (signed char)(r[i] - (carry<<3)); 253 } 254 r[84] = (signed char)(r[84] + (signed char)carry); 255} 256 257void sc25519_window5(signed char r[51], const sc25519 *s) 258{ 259 char carry; 260 int i; 261 for(i=0;i<6;i++) 262 { 263 r[8*i+0] = s->v[5*i+0] & 31; 264 r[8*i+1] = (s->v[5*i+0] >> 5) & 31; 265 r[8*i+1] = (signed char)(r[8*i+1] ^ (int)((s->v[5*i+1] << 3) & 31)); 266 r[8*i+2] = (s->v[5*i+1] >> 2) & 31; 267 r[8*i+3] = (s->v[5*i+1] >> 7) & 31; 268 r[8*i+3] = (signed char)(r[8*i+3] ^ (int)((s->v[5*i+2] << 1) & 31)); 269 r[8*i+4] = (s->v[5*i+2] >> 4) & 31; 270 r[8*i+4] = (signed char)(r[8*i+4] ^ (int)((s->v[5*i+3] << 4) & 31)); 271 r[8*i+5] = (s->v[5*i+3] >> 1) & 31; 272 r[8*i+6] = (s->v[5*i+3] >> 6) & 31; 273 r[8*i+6] = (signed char)(r[8*i+6] ^ (int)((s->v[5*i+4] << 2) & 31)); 274 r[8*i+7] = (s->v[5*i+4] >> 3) & 31; 275 } 276 r[8*i+0] = s->v[5*i+0] & 31; 277 r[8*i+1] = (s->v[5*i+0] >> 5) & 31; 278 r[8*i+1] = (signed char)(r[8*i+1] ^ (int)((s->v[5*i+1] << 3) & 31)); 279 r[8*i+2] = (s->v[5*i+1] >> 2) & 31; 280 281 /* Making it signed */ 282 carry = 0; 283 for(i=0;i<50;i++) 284 { 285 r[i] = (signed char)(r[i] + (signed char)carry); 286 r[i+1] = (signed char)(r[i + 1] + (r[i] >> 5)); 287 r[i] &= 31; 288 carry = (char)(r[i] >> 4); 289 r[i] = (signed char)(r[i] - (carry<<5)); 290 } 291 r[50] = (signed char)(r[50] + carry); 292} 293 294void sc25519_2interleave2(unsigned char r[127], const sc25519 *s1, const sc25519 *s2) 295{ 296 int i; 297 for(i=0;i<31;i++) 298 { 299 r[4*i] = (unsigned char)(( s1->v[i] & 3) ^ (( s2->v[i] & 3) << 2)); 300 r[4*i+1] = (unsigned char)(((s1->v[i] >> 2) & 3) ^ (((s2->v[i] >> 2) & 3) << 2)); 301 r[4*i+2] = (unsigned char)(((s1->v[i] >> 4) & 3) ^ (((s2->v[i] >> 4) & 3) << 2)); 302 r[4*i+3] = (unsigned char)(((s1->v[i] >> 6) & 3) ^ (((s2->v[i] >> 6) & 3) << 2)); 303 } 304 r[124] = (unsigned char)(( s1->v[31] & 3) ^ (( s2->v[31] & 3) << 2)); 305 r[125] = (unsigned char)(((s1->v[31] >> 2) & 3) ^ (((s2->v[31] >> 2) & 3) << 2)); 306 r[126] = (unsigned char)(((s1->v[31] >> 4) & 3) ^ (((s2->v[31] >> 4) & 3) << 2)); 307} 308