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
15 static 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
18 static 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
lt(uint32_t a,uint32_t b)21 static 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 */
sc_reduce_add_sub(sc25519 * r)30 static 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] = 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 */
barrett_reduce(sc25519 * r,const uint32_t x[64])51 static 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
sc25519_from32bytes(sc25519 * r,const unsigned char x[32])102 void 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
shortsc25519_from16bytes(shortsc25519 * r,const unsigned char x[16])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
sc25519_from64bytes(sc25519 * r,const unsigned char x[64])117 void 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
sc25519_from_shortsc(sc25519 * r,const shortsc25519 * x)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
sc25519_to32bytes(unsigned char r[32],const sc25519 * x)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
sc25519_iszero_vartime(const sc25519 * x)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
sc25519_isshort_vartime(const sc25519 * x)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
sc25519_lt_vartime(const sc25519 * x,const sc25519 * y)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
sc25519_add(sc25519 * r,const sc25519 * x,const sc25519 * y)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 sc_reduce_add_sub(r);
178 }
179
sc25519_sub_nored(sc25519 * r,const sc25519 * x,const sc25519 * y)180 void 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
sc25519_mul(sc25519 * r,const sc25519 * x,const sc25519 * y)192 void 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 = t[i] >> 8;
206 t[i+1] += carry;
207 t[i] &= 0xff;
208 }
209
210 barrett_reduce(r, t);
211 }
212
sc25519_mul_shortsc(sc25519 * r,const sc25519 * x,const shortsc25519 * y)213 void 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
sc25519_window3(signed char r[85],const sc25519 * s)220 void 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] ^= (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] ^= (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] ^= (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] += carry;
249 r[i+1] += r[i] >> 3;
250 r[i] &= 7;
251 carry = r[i] >> 2;
252 r[i] -= carry<<3;
253 }
254 r[84] += carry;
255 }
256
sc25519_window5(signed char r[51],const sc25519 * s)257 void 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] ^= (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] ^= (s->v[5*i+2] << 1) & 31;
269 r[8*i+4] = (s->v[5*i+2] >> 4) & 31;
270 r[8*i+4] ^= (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] ^= (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] ^= (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] += carry;
286 r[i+1] += r[i] >> 5;
287 r[i] &= 31;
288 carry = r[i] >> 4;
289 r[i] -= carry<<5;
290 }
291 r[50] += carry;
292 }
293
sc25519_2interleave2(unsigned char r[127],const sc25519 * s1,const sc25519 * s2)294 void 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] = ( s1->v[i] & 3) ^ (( s2->v[i] & 3) << 2);
300 r[4*i+1] = ((s1->v[i] >> 2) & 3) ^ (((s2->v[i] >> 2) & 3) << 2);
301 r[4*i+2] = ((s1->v[i] >> 4) & 3) ^ (((s2->v[i] >> 4) & 3) << 2);
302 r[4*i+3] = ((s1->v[i] >> 6) & 3) ^ (((s2->v[i] >> 6) & 3) << 2);
303 }
304 r[124] = ( s1->v[31] & 3) ^ (( s2->v[31] & 3) << 2);
305 r[125] = ((s1->v[31] >> 2) & 3) ^ (((s2->v[31] >> 2) & 3) << 2);
306 r[126] = ((s1->v[31] >> 4) & 3) ^ (((s2->v[31] >> 4) & 3) << 2);
307 }
308