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