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 |
|
21376 |
x -= (unsigned int) b; /* 0..65535: no; 4294901761..4294967295: yes */ |
23 |
|
10688 |
x >>= 31; /* 0: no; 1: yes */ |
24 |
|
10688 |
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 |
|
456 |
unsigned char t[32]; |
35 |
|
|
|
36 |
✓✓ |
15048 |
for(i=0;i<32;i++) |
37 |
|
|
{ |
38 |
|
7296 |
pb += m[i]; |
39 |
|
7296 |
b = lt(r->v[i],pb); |
40 |
|
7296 |
t[i] = r->v[i]-pb+(b<<8); |
41 |
|
|
pb = b; |
42 |
|
|
} |
43 |
|
228 |
mask = b - 1; |
44 |
✓✓ |
15048 |
for(i=0;i<32;i++) |
45 |
|
7296 |
r->v[i] ^= mask & (r->v[i] ^ t[i]); |
46 |
|
228 |
} |
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 |
|
212 |
crypto_uint32 q2[66]; |
54 |
|
106 |
crypto_uint32 *q3 = q2 + 33; |
55 |
|
106 |
crypto_uint32 r1[33]; |
56 |
|
106 |
crypto_uint32 r2[33]; |
57 |
|
|
crypto_uint32 carry; |
58 |
|
|
crypto_uint32 pb = 0; |
59 |
|
|
crypto_uint32 b; |
60 |
|
|
|
61 |
✓✓ |
14204 |
for (i = 0;i < 66;++i) q2[i] = 0; |
62 |
✓✓ |
7208 |
for (i = 0;i < 33;++i) r2[i] = 0; |
63 |
|
|
|
64 |
✓✓ |
7208 |
for(i=0;i<33;i++) |
65 |
✓✓ |
237864 |
for(j=0;j<33;j++) |
66 |
✓✓ |
178292 |
if(i+j >= 31) q2[i+j] += mu[i]*x[j+31]; |
67 |
|
106 |
carry = q2[31] >> 8; |
68 |
|
106 |
q2[32] += carry; |
69 |
|
106 |
carry = q2[32] >> 8; |
70 |
|
106 |
q2[33] += carry; |
71 |
|
|
|
72 |
✓✓ |
7208 |
for(i=0;i<33;i++)r1[i] = x[i]; |
73 |
✓✓ |
6996 |
for(i=0;i<32;i++) |
74 |
✓✓ |
230656 |
for(j=0;j<33;j++) |
75 |
✓✓ |
171296 |
if(i+j < 33) r2[i+j] += m[i]*q3[j]; |
76 |
|
|
|
77 |
✓✓ |
6996 |
for(i=0;i<32;i++) |
78 |
|
|
{ |
79 |
|
3392 |
carry = r2[i] >> 8; |
80 |
|
3392 |
r2[i+1] += carry; |
81 |
|
3392 |
r2[i] &= 0xff; |
82 |
|
|
} |
83 |
|
|
|
84 |
✓✓ |
6996 |
for(i=0;i<32;i++) |
85 |
|
|
{ |
86 |
|
3392 |
pb += r2[i]; |
87 |
|
3392 |
b = lt(r1[i],pb); |
88 |
|
3392 |
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 |
|
106 |
reduce_add_sub(r); |
97 |
|
106 |
reduce_add_sub(r); |
98 |
|
106 |
} |
99 |
|
|
|
100 |
|
|
void sc25519_from32bytes(sc25519 *r, const unsigned char x[32]) |
101 |
|
|
{ |
102 |
|
|
int i; |
103 |
|
74 |
crypto_uint32 t[64]; |
104 |
✓✓ |
2442 |
for(i=0;i<32;i++) t[i] = x[i]; |
105 |
✓✓ |
2442 |
for(i=32;i<64;++i) t[i] = 0; |
106 |
|
37 |
barrett_reduce(r, t); |
107 |
|
37 |
} |
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 |
|
106 |
crypto_uint32 t[64]; |
119 |
✓✓ |
6890 |
for(i=0;i<64;i++) t[i] = x[i]; |
120 |
|
53 |
barrett_reduce(r, t); |
121 |
|
53 |
} |
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 |
✓✓ |
1072 |
for(i=0;i<32;i++) r[i] = x->v[i]; |
136 |
|
16 |
} |
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 |
✓✓ |
1072 |
for(i=0;i<32;i++) r->v[i] = x->v[i] + y->v[i]; |
169 |
✓✓ |
1024 |
for(i=0;i<31;i++) |
170 |
|
|
{ |
171 |
|
496 |
carry = r->v[i] >> 8; |
172 |
|
496 |
r->v[i+1] += carry; |
173 |
|
496 |
r->v[i] &= 0xff; |
174 |
|
|
} |
175 |
|
16 |
reduce_add_sub(r); |
176 |
|
16 |
} |
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 |
|
32 |
crypto_uint32 t[64]; |
195 |
✓✓ |
2080 |
for(i=0;i<64;i++)t[i] = 0; |
196 |
|
|
|
197 |
✓✓ |
1056 |
for(i=0;i<32;i++) |
198 |
✓✓ |
33792 |
for(j=0;j<32;j++) |
199 |
|
16384 |
t[i+j] += x->v[i] * y->v[j]; |
200 |
|
|
|
201 |
|
|
/* Reduce coefficients */ |
202 |
✓✓ |
2048 |
for(i=0;i<63;i++) |
203 |
|
|
{ |
204 |
|
1008 |
carry = t[i] >> 8; |
205 |
|
1008 |
t[i+1] += carry; |
206 |
|
1008 |
t[i] &= 0xff; |
207 |
|
|
} |
208 |
|
|
|
209 |
|
16 |
barrett_reduce(r, t); |
210 |
|
16 |
} |
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 |
✓✓ |
368 |
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 |
|
160 |
r[8*i+5] = (s->v[3*i+1] >> 7) & 7; |
232 |
|
160 |
r[8*i+5] ^= (s->v[3*i+2] << 1) & 7; |
233 |
|
160 |
r[8*i+6] = (s->v[3*i+2] >> 2) & 7; |
234 |
|
160 |
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 |
✓✓ |
2720 |
for(i=0;i<84;i++) |
246 |
|
|
{ |
247 |
|
1344 |
r[i] += carry; |
248 |
|
1344 |
r[i+1] += r[i] >> 3; |
249 |
|
1344 |
r[i] &= 7; |
250 |
|
1344 |
carry = r[i] >> 2; |
251 |
|
1344 |
r[i] -= carry<<3; |
252 |
|
|
} |
253 |
|
16 |
r[84] += carry; |
254 |
|
16 |
} |
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 |
✓✓ |
1365 |
for(i=0;i<31;i++) |
297 |
|
|
{ |
298 |
|
651 |
r[4*i] = ( s1->v[i] & 3) ^ (( s2->v[i] & 3) << 2); |
299 |
|
651 |
r[4*i+1] = ((s1->v[i] >> 2) & 3) ^ (((s2->v[i] >> 2) & 3) << 2); |
300 |
|
651 |
r[4*i+2] = ((s1->v[i] >> 4) & 3) ^ (((s2->v[i] >> 4) & 3) << 2); |
301 |
|
651 |
r[4*i+3] = ((s1->v[i] >> 6) & 3) ^ (((s2->v[i] >> 6) & 3) << 2); |
302 |
|
|
} |
303 |
|
21 |
r[124] = ( s1->v[31] & 3) ^ (( s2->v[31] & 3) << 2); |
304 |
|
21 |
r[125] = ((s1->v[31] >> 2) & 3) ^ (((s2->v[31] >> 2) & 3) << 2); |
305 |
|
21 |
r[126] = ((s1->v[31] >> 4) & 3) ^ (((s2->v[31] >> 4) & 3) << 2); |
306 |
|
21 |
} |