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
lt(crypto_uint32 a,crypto_uint32 b)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 */
reduce_add_sub(sc25519 * r)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 */
barrett_reduce(sc25519 * r,const crypto_uint32 x[64])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
sc25519_from32bytes(sc25519 * r,const unsigned char x[32])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
shortsc25519_from16bytes(shortsc25519 * r,const unsigned char x[16])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
sc25519_from64bytes(sc25519 * r,const unsigned char x[64])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
sc25519_from_shortsc(sc25519 * r,const shortsc25519 * x)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
sc25519_to32bytes(unsigned char r[32],const sc25519 * x)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
sc25519_iszero_vartime(const sc25519 * x)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
sc25519_isshort_vartime(const sc25519 * x)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
sc25519_lt_vartime(const sc25519 * x,const sc25519 * y)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
sc25519_add(sc25519 * r,const sc25519 * x,const sc25519 * y)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
sc25519_sub_nored(sc25519 * r,const sc25519 * x,const sc25519 * y)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
sc25519_mul(sc25519 * r,const sc25519 * x,const sc25519 * y)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
sc25519_mul_shortsc(sc25519 * r,const sc25519 * x,const shortsc25519 * y)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
sc25519_window3(signed char r[85],const sc25519 * s)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
sc25519_window5(signed char r[51],const sc25519 * s)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
sc25519_2interleave2(unsigned char r[127],const sc25519 * s1,const sc25519 * s2)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