Branch data Line data Source code
1 : : /* $OpenBSD: fe25519.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/fe25519.c
7 : : */
8 : :
9 : : #include "includes.h"
10 : :
11 : : #define WINDOWSIZE 1 /* Should be 1,2, or 4 */
12 : : #define WINDOWMASK ((1<<WINDOWSIZE)-1)
13 : :
14 : : #include "fe25519.h"
15 : :
16 : : static crypto_uint32 equal(crypto_uint32 a,crypto_uint32 b) /* 16-bit inputs */
17 : : {
18 : 7936 : crypto_uint32 x = a ^ b; /* 0: yes; 1..65535: no */
19 : 7936 : x -= 1; /* 4294967295: yes; 0..65534: no */
20 : 7936 : x >>= 31; /* 1: yes; 0: no */
21 : : return x;
22 : : }
23 : :
24 : : static crypto_uint32 ge(crypto_uint32 a,crypto_uint32 b) /* 16-bit inputs */
25 : : {
26 : 256 : unsigned int x = a;
27 : 256 : x -= (unsigned int) b; /* 0..65535: yes; 4294901761..4294967295: no */
28 : 256 : x >>= 31; /* 0: yes; 1: no */
29 : 256 : x ^= 1; /* 1: yes; 0: no */
30 : : return x;
31 : : }
32 : :
33 : : static crypto_uint32 times19(crypto_uint32 a)
34 : : {
35 : 715818 : return (a << 4) + (a << 1) + a;
36 : : }
37 : :
38 : : static crypto_uint32 times38(crypto_uint32 a)
39 : : {
40 : 3980989 : return (a << 5) + (a << 2) + (a << 1);
41 : : }
42 : :
43 : 114745 : static void reduce_add_sub(fe25519 *r)
44 : : {
45 : : crypto_uint32 t;
46 : : int i,rep;
47 : :
48 [ + + ]: 573725 : for(rep=0;rep<4;rep++)
49 : : {
50 : 458980 : t = r->v[31] >> 7;
51 : 458980 : r->v[31] &= 127;
52 : 458980 : t = times19(t);
53 : 458980 : r->v[0] += t;
54 [ + + ]: 14687360 : for(i=0;i<31;i++)
55 : : {
56 : 14228380 : t = r->v[i] >> 8;
57 : 14228380 : r->v[i+1] += t;
58 : 14228380 : r->v[i] &= 255;
59 : : }
60 : : }
61 : 114745 : }
62 : :
63 : 128419 : static void reduce_mul(fe25519 *r)
64 : : {
65 : : crypto_uint32 t;
66 : : int i,rep;
67 : :
68 [ + + ]: 385257 : for(rep=0;rep<2;rep++)
69 : : {
70 : 256838 : t = r->v[31] >> 7;
71 : 256838 : r->v[31] &= 127;
72 : 256838 : t = times19(t);
73 : 256838 : r->v[0] += t;
74 [ + + ]: 8218816 : for(i=0;i<31;i++)
75 : : {
76 : 7961978 : t = r->v[i] >> 8;
77 : 7961978 : r->v[i+1] += t;
78 : 7961978 : r->v[i] &= 255;
79 : : }
80 : : }
81 : 128419 : }
82 : :
83 : : /* reduction modulo 2^255-19 */
84 : 256 : void fe25519_freeze(fe25519 *r)
85 : : {
86 : : int i;
87 : 512 : crypto_uint32 m = equal(r->v[31],127);
88 [ + + ]: 7936 : for(i=30;i>0;i--)
89 : 15360 : m &= equal(r->v[i],255);
90 : 512 : m &= ge(r->v[0],237);
91 : :
92 : 256 : m = -m;
93 : :
94 : 256 : r->v[31] -= m&127;
95 [ + + ]: 7936 : for(i=30;i>0;i--)
96 : 7680 : r->v[i] -= m&255;
97 : 256 : r->v[0] -= m&237;
98 : 256 : }
99 : :
100 : 28 : void fe25519_unpack(fe25519 *r, const unsigned char x[32])
101 : : {
102 : : int i;
103 [ + + ]: 924 : for(i=0;i<32;i++) r->v[i] = x[i];
104 : 28 : r->v[31] &= 127;
105 : 28 : }
106 : :
107 : : /* Assumes input x being reduced below 2^255 */
108 : 58 : void fe25519_pack(unsigned char r[32], const fe25519 *x)
109 : : {
110 : : int i;
111 : 58 : fe25519 y = *x;
112 : 58 : fe25519_freeze(&y);
113 [ + + ]: 1914 : for(i=0;i<32;i++)
114 : 1856 : r[i] = y.v[i];
115 : 58 : }
116 : :
117 : 0 : int fe25519_iszero(const fe25519 *x)
118 : : {
119 : : int i;
120 : : int r;
121 : 0 : fe25519 t = *x;
122 : 0 : fe25519_freeze(&t);
123 : 0 : r = equal(t.v[0],0);
124 [ # # ]: 0 : for(i=1;i<32;i++)
125 : 0 : r &= equal(t.v[i],0);
126 : 0 : return r;
127 : : }
128 : :
129 : 56 : int fe25519_iseq_vartime(const fe25519 *x, const fe25519 *y)
130 : : {
131 : : int i;
132 : 56 : fe25519 t1 = *x;
133 : 56 : fe25519 t2 = *y;
134 : 56 : fe25519_freeze(&t1);
135 : 56 : fe25519_freeze(&t2);
136 [ + + ]: 952 : for(i=0;i<32;i++)
137 [ + + ]: 924 : if(t1.v[i] != t2.v[i]) return 0;
138 : : return 1;
139 : : }
140 : :
141 : 22950 : void fe25519_cmov(fe25519 *r, const fe25519 *x, unsigned char b)
142 : : {
143 : : int i;
144 : 22950 : crypto_uint32 mask = b;
145 : 22950 : mask = -mask;
146 [ + + ]: 757350 : for(i=0;i<32;i++) r->v[i] ^= mask & (x->v[i] ^ r->v[i]);
147 : 22950 : }
148 : :
149 : 86 : unsigned char fe25519_getparity(const fe25519 *x)
150 : : {
151 : 86 : fe25519 t = *x;
152 : 86 : fe25519_freeze(&t);
153 : 86 : return t.v[0] & 1;
154 : : }
155 : :
156 : 114 : void fe25519_setone(fe25519 *r)
157 : : {
158 : : int i;
159 : 114 : r->v[0] = 1;
160 [ + + ]: 3648 : for(i=1;i<32;i++) r->v[i]=0;
161 : 114 : }
162 : :
163 : 56 : void fe25519_setzero(fe25519 *r)
164 : : {
165 : : int i;
166 [ + + ][ + + ]: 322278 : for(i=0;i<32;i++) r->v[i]=0;
167 : 56 : }
168 : :
169 : 9710 : void fe25519_neg(fe25519 *r, const fe25519 *x)
170 : : {
171 : : fe25519 t;
172 : : int i;
173 [ + + ]: 320430 : for(i=0;i<32;i++) t.v[i]=x->v[i];
174 : : fe25519_setzero(r);
175 : 9710 : fe25519_sub(r, r, &t);
176 : 9710 : }
177 : :
178 : 52003 : void fe25519_add(fe25519 *r, const fe25519 *x, const fe25519 *y)
179 : : {
180 : : int i;
181 [ + + ]: 1716099 : for(i=0;i<32;i++) r->v[i] = x->v[i] + y->v[i];
182 : 52003 : reduce_add_sub(r);
183 : 52003 : }
184 : :
185 : 62742 : void fe25519_sub(fe25519 *r, const fe25519 *x, const fe25519 *y)
186 : : {
187 : : int i;
188 : : crypto_uint32 t[32];
189 : 62742 : t[0] = x->v[0] + 0x1da;
190 : 62742 : t[31] = x->v[31] + 0xfe;
191 [ + + ]: 1945002 : for(i=1;i<31;i++) t[i] = x->v[i] + 0x1fe;
192 [ + + ]: 2070486 : for(i=0;i<32;i++) r->v[i] = t[i] - y->v[i];
193 : 62742 : reduce_add_sub(r);
194 : 62742 : }
195 : :
196 : 128419 : void fe25519_mul(fe25519 *r, const fe25519 *x, const fe25519 *y)
197 : : {
198 : : int i,j;
199 : : crypto_uint32 t[63];
200 [ + + ]: 8218816 : for(i=0;i<63;i++)t[i] = 0;
201 : :
202 [ + + ]: 4237827 : for(i=0;i<32;i++)
203 [ + + ]: 135610464 : for(j=0;j<32;j++)
204 : 131501056 : t[i+j] += x->v[i] * y->v[j];
205 : :
206 [ + + ]: 4109408 : for(i=32;i<63;i++)
207 : 7961978 : r->v[i-32] = t[i-32] + times38(t[i]);
208 : 128419 : r->v[31] = t[31]; /* result now in r[0]...r[31] */
209 : :
210 : 128419 : reduce_mul(r);
211 : 128419 : }
212 : :
213 : 28700 : void fe25519_square(fe25519 *r, const fe25519 *x)
214 : : {
215 : 42640 : fe25519_mul(r, x, x);
216 : 28700 : }
217 : :
218 : 58 : void fe25519_invert(fe25519 *r, const fe25519 *x)
219 : : {
220 : : fe25519 z2;
221 : : fe25519 z9;
222 : : fe25519 z11;
223 : : fe25519 z2_5_0;
224 : : fe25519 z2_10_0;
225 : : fe25519 z2_20_0;
226 : : fe25519 z2_50_0;
227 : : fe25519 z2_100_0;
228 : : fe25519 t0;
229 : : fe25519 t1;
230 : : int i;
231 : :
232 : : /* 2 */ fe25519_square(&z2,x);
233 : : /* 4 */ fe25519_square(&t1,&z2);
234 : : /* 8 */ fe25519_square(&t0,&t1);
235 : 58 : /* 9 */ fe25519_mul(&z9,&t0,x);
236 : 58 : /* 11 */ fe25519_mul(&z11,&z9,&z2);
237 : : /* 22 */ fe25519_square(&t0,&z11);
238 : 58 : /* 2^5 - 2^0 = 31 */ fe25519_mul(&z2_5_0,&t0,&z9);
239 : :
240 : : /* 2^6 - 2^1 */ fe25519_square(&t0,&z2_5_0);
241 : : /* 2^7 - 2^2 */ fe25519_square(&t1,&t0);
242 : : /* 2^8 - 2^3 */ fe25519_square(&t0,&t1);
243 : : /* 2^9 - 2^4 */ fe25519_square(&t1,&t0);
244 : : /* 2^10 - 2^5 */ fe25519_square(&t0,&t1);
245 : 58 : /* 2^10 - 2^0 */ fe25519_mul(&z2_10_0,&t0,&z2_5_0);
246 : :
247 : : /* 2^11 - 2^1 */ fe25519_square(&t0,&z2_10_0);
248 : : /* 2^12 - 2^2 */ fe25519_square(&t1,&t0);
249 [ + + ]: 290 : /* 2^20 - 2^10 */ for (i = 2;i < 10;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
250 : 58 : /* 2^20 - 2^0 */ fe25519_mul(&z2_20_0,&t1,&z2_10_0);
251 : :
252 : : /* 2^21 - 2^1 */ fe25519_square(&t0,&z2_20_0);
253 : : /* 2^22 - 2^2 */ fe25519_square(&t1,&t0);
254 [ + + ]: 580 : /* 2^40 - 2^20 */ for (i = 2;i < 20;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
255 : 58 : /* 2^40 - 2^0 */ fe25519_mul(&t0,&t1,&z2_20_0);
256 : :
257 : : /* 2^41 - 2^1 */ fe25519_square(&t1,&t0);
258 : : /* 2^42 - 2^2 */ fe25519_square(&t0,&t1);
259 [ + + ]: 290 : /* 2^50 - 2^10 */ for (i = 2;i < 10;i += 2) { fe25519_square(&t1,&t0); fe25519_square(&t0,&t1); }
260 : 58 : /* 2^50 - 2^0 */ fe25519_mul(&z2_50_0,&t0,&z2_10_0);
261 : :
262 : : /* 2^51 - 2^1 */ fe25519_square(&t0,&z2_50_0);
263 : : /* 2^52 - 2^2 */ fe25519_square(&t1,&t0);
264 [ + + ]: 1450 : /* 2^100 - 2^50 */ for (i = 2;i < 50;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
265 : 58 : /* 2^100 - 2^0 */ fe25519_mul(&z2_100_0,&t1,&z2_50_0);
266 : :
267 : : /* 2^101 - 2^1 */ fe25519_square(&t1,&z2_100_0);
268 : : /* 2^102 - 2^2 */ fe25519_square(&t0,&t1);
269 [ + + ]: 2900 : /* 2^200 - 2^100 */ for (i = 2;i < 100;i += 2) { fe25519_square(&t1,&t0); fe25519_square(&t0,&t1); }
270 : 58 : /* 2^200 - 2^0 */ fe25519_mul(&t1,&t0,&z2_100_0);
271 : :
272 : : /* 2^201 - 2^1 */ fe25519_square(&t0,&t1);
273 : : /* 2^202 - 2^2 */ fe25519_square(&t1,&t0);
274 [ + + ]: 1450 : /* 2^250 - 2^50 */ for (i = 2;i < 50;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
275 : 58 : /* 2^250 - 2^0 */ fe25519_mul(&t0,&t1,&z2_50_0);
276 : :
277 : : /* 2^251 - 2^1 */ fe25519_square(&t1,&t0);
278 : : /* 2^252 - 2^2 */ fe25519_square(&t0,&t1);
279 : : /* 2^253 - 2^3 */ fe25519_square(&t1,&t0);
280 : : /* 2^254 - 2^4 */ fe25519_square(&t0,&t1);
281 : : /* 2^255 - 2^5 */ fe25519_square(&t1,&t0);
282 : 58 : /* 2^255 - 21 */ fe25519_mul(r,&t1,&z11);
283 : 58 : }
284 : :
285 : 28 : void fe25519_pow2523(fe25519 *r, const fe25519 *x)
286 : : {
287 : : fe25519 z2;
288 : : fe25519 z9;
289 : : fe25519 z11;
290 : : fe25519 z2_5_0;
291 : : fe25519 z2_10_0;
292 : : fe25519 z2_20_0;
293 : : fe25519 z2_50_0;
294 : : fe25519 z2_100_0;
295 : : fe25519 t;
296 : : int i;
297 : :
298 : : /* 2 */ fe25519_square(&z2,x);
299 : : /* 4 */ fe25519_square(&t,&z2);
300 : : /* 8 */ fe25519_square(&t,&t);
301 : 28 : /* 9 */ fe25519_mul(&z9,&t,x);
302 : 28 : /* 11 */ fe25519_mul(&z11,&z9,&z2);
303 : : /* 22 */ fe25519_square(&t,&z11);
304 : 28 : /* 2^5 - 2^0 = 31 */ fe25519_mul(&z2_5_0,&t,&z9);
305 : :
306 : : /* 2^6 - 2^1 */ fe25519_square(&t,&z2_5_0);
307 [ + + ]: 140 : /* 2^10 - 2^5 */ for (i = 1;i < 5;i++) { fe25519_square(&t,&t); }
308 : 28 : /* 2^10 - 2^0 */ fe25519_mul(&z2_10_0,&t,&z2_5_0);
309 : :
310 : : /* 2^11 - 2^1 */ fe25519_square(&t,&z2_10_0);
311 [ + + ]: 280 : /* 2^20 - 2^10 */ for (i = 1;i < 10;i++) { fe25519_square(&t,&t); }
312 : 28 : /* 2^20 - 2^0 */ fe25519_mul(&z2_20_0,&t,&z2_10_0);
313 : :
314 : : /* 2^21 - 2^1 */ fe25519_square(&t,&z2_20_0);
315 [ + + ]: 560 : /* 2^40 - 2^20 */ for (i = 1;i < 20;i++) { fe25519_square(&t,&t); }
316 : 28 : /* 2^40 - 2^0 */ fe25519_mul(&t,&t,&z2_20_0);
317 : :
318 : : /* 2^41 - 2^1 */ fe25519_square(&t,&t);
319 [ + + ]: 280 : /* 2^50 - 2^10 */ for (i = 1;i < 10;i++) { fe25519_square(&t,&t); }
320 : 28 : /* 2^50 - 2^0 */ fe25519_mul(&z2_50_0,&t,&z2_10_0);
321 : :
322 : : /* 2^51 - 2^1 */ fe25519_square(&t,&z2_50_0);
323 [ + + ]: 1400 : /* 2^100 - 2^50 */ for (i = 1;i < 50;i++) { fe25519_square(&t,&t); }
324 : 28 : /* 2^100 - 2^0 */ fe25519_mul(&z2_100_0,&t,&z2_50_0);
325 : :
326 : : /* 2^101 - 2^1 */ fe25519_square(&t,&z2_100_0);
327 [ + + ]: 2800 : /* 2^200 - 2^100 */ for (i = 1;i < 100;i++) { fe25519_square(&t,&t); }
328 : 28 : /* 2^200 - 2^0 */ fe25519_mul(&t,&t,&z2_100_0);
329 : :
330 : : /* 2^201 - 2^1 */ fe25519_square(&t,&t);
331 [ + + ]: 1400 : /* 2^250 - 2^50 */ for (i = 1;i < 50;i++) { fe25519_square(&t,&t); }
332 : 28 : /* 2^250 - 2^0 */ fe25519_mul(&t,&t,&z2_50_0);
333 : :
334 : : /* 2^251 - 2^1 */ fe25519_square(&t,&t);
335 : : /* 2^252 - 2^2 */ fe25519_square(&t,&t);
336 : 28 : /* 2^252 - 3 */ fe25519_mul(r,&t,x);
337 : 28 : }
|
