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
equal(crypto_uint32 a,crypto_uint32 b)16 static crypto_uint32 equal(crypto_uint32 a,crypto_uint32 b) /* 16-bit inputs */
17 {
18 crypto_uint32 x = a ^ b; /* 0: yes; 1..65535: no */
19 x -= 1; /* 4294967295: yes; 0..65534: no */
20 x >>= 31; /* 1: yes; 0: no */
21 return x;
22 }
23
ge(crypto_uint32 a,crypto_uint32 b)24 static crypto_uint32 ge(crypto_uint32 a,crypto_uint32 b) /* 16-bit inputs */
25 {
26 unsigned int x = a;
27 x -= (unsigned int) b; /* 0..65535: yes; 4294901761..4294967295: no */
28 x >>= 31; /* 0: yes; 1: no */
29 x ^= 1; /* 1: yes; 0: no */
30 return x;
31 }
32
times19(crypto_uint32 a)33 static crypto_uint32 times19(crypto_uint32 a)
34 {
35 return (a << 4) + (a << 1) + a;
36 }
37
times38(crypto_uint32 a)38 static crypto_uint32 times38(crypto_uint32 a)
39 {
40 return (a << 5) + (a << 2) + (a << 1);
41 }
42
reduce_add_sub(fe25519 * r)43 static void reduce_add_sub(fe25519 *r)
44 {
45 crypto_uint32 t;
46 int i,rep;
47
48 for(rep=0;rep<4;rep++)
49 {
50 t = r->v[31] >> 7;
51 r->v[31] &= 127;
52 t = times19(t);
53 r->v[0] += t;
54 for(i=0;i<31;i++)
55 {
56 t = r->v[i] >> 8;
57 r->v[i+1] += t;
58 r->v[i] &= 255;
59 }
60 }
61 }
62
reduce_mul(fe25519 * r)63 static void reduce_mul(fe25519 *r)
64 {
65 crypto_uint32 t;
66 int i,rep;
67
68 for(rep=0;rep<2;rep++)
69 {
70 t = r->v[31] >> 7;
71 r->v[31] &= 127;
72 t = times19(t);
73 r->v[0] += t;
74 for(i=0;i<31;i++)
75 {
76 t = r->v[i] >> 8;
77 r->v[i+1] += t;
78 r->v[i] &= 255;
79 }
80 }
81 }
82
83 /* reduction modulo 2^255-19 */
fe25519_freeze(fe25519 * r)84 void fe25519_freeze(fe25519 *r)
85 {
86 int i;
87 crypto_uint32 m = equal(r->v[31],127);
88 for(i=30;i>0;i--)
89 m &= equal(r->v[i],255);
90 m &= ge(r->v[0],237);
91
92 m = -m;
93
94 r->v[31] -= m&127;
95 for(i=30;i>0;i--)
96 r->v[i] -= m&255;
97 r->v[0] -= m&237;
98 }
99
fe25519_unpack(fe25519 * r,const unsigned char x[32])100 void fe25519_unpack(fe25519 *r, const unsigned char x[32])
101 {
102 int i;
103 for(i=0;i<32;i++) r->v[i] = x[i];
104 r->v[31] &= 127;
105 }
106
107 /* Assumes input x being reduced below 2^255 */
fe25519_pack(unsigned char r[32],const fe25519 * x)108 void fe25519_pack(unsigned char r[32], const fe25519 *x)
109 {
110 int i;
111 fe25519 y = *x;
112 fe25519_freeze(&y);
113 for(i=0;i<32;i++)
114 r[i] = y.v[i];
115 }
116
fe25519_iszero(const fe25519 * x)117 int fe25519_iszero(const fe25519 *x)
118 {
119 int i;
120 int r;
121 fe25519 t = *x;
122 fe25519_freeze(&t);
123 r = equal(t.v[0],0);
124 for(i=1;i<32;i++)
125 r &= equal(t.v[i],0);
126 return r;
127 }
128
fe25519_iseq_vartime(const fe25519 * x,const fe25519 * y)129 int fe25519_iseq_vartime(const fe25519 *x, const fe25519 *y)
130 {
131 int i;
132 fe25519 t1 = *x;
133 fe25519 t2 = *y;
134 fe25519_freeze(&t1);
135 fe25519_freeze(&t2);
136 for(i=0;i<32;i++)
137 if(t1.v[i] != t2.v[i]) return 0;
138 return 1;
139 }
140
fe25519_cmov(fe25519 * r,const fe25519 * x,unsigned char b)141 void fe25519_cmov(fe25519 *r, const fe25519 *x, unsigned char b)
142 {
143 int i;
144 crypto_uint32 mask = b;
145 mask = -mask;
146 for(i=0;i<32;i++) r->v[i] ^= mask & (x->v[i] ^ r->v[i]);
147 }
148
fe25519_getparity(const fe25519 * x)149 unsigned char fe25519_getparity(const fe25519 *x)
150 {
151 fe25519 t = *x;
152 fe25519_freeze(&t);
153 return t.v[0] & 1;
154 }
155
fe25519_setone(fe25519 * r)156 void fe25519_setone(fe25519 *r)
157 {
158 int i;
159 r->v[0] = 1;
160 for(i=1;i<32;i++) r->v[i]=0;
161 }
162
fe25519_setzero(fe25519 * r)163 void fe25519_setzero(fe25519 *r)
164 {
165 int i;
166 for(i=0;i<32;i++) r->v[i]=0;
167 }
168
fe25519_neg(fe25519 * r,const fe25519 * x)169 void fe25519_neg(fe25519 *r, const fe25519 *x)
170 {
171 fe25519 t;
172 int i;
173 for(i=0;i<32;i++) t.v[i]=x->v[i];
174 fe25519_setzero(r);
175 fe25519_sub(r, r, &t);
176 }
177
fe25519_add(fe25519 * r,const fe25519 * x,const fe25519 * y)178 void fe25519_add(fe25519 *r, const fe25519 *x, const fe25519 *y)
179 {
180 int i;
181 for(i=0;i<32;i++) r->v[i] = x->v[i] + y->v[i];
182 reduce_add_sub(r);
183 }
184
fe25519_sub(fe25519 * r,const fe25519 * x,const fe25519 * y)185 void fe25519_sub(fe25519 *r, const fe25519 *x, const fe25519 *y)
186 {
187 int i;
188 crypto_uint32 t[32];
189 t[0] = x->v[0] + 0x1da;
190 t[31] = x->v[31] + 0xfe;
191 for(i=1;i<31;i++) t[i] = x->v[i] + 0x1fe;
192 for(i=0;i<32;i++) r->v[i] = t[i] - y->v[i];
193 reduce_add_sub(r);
194 }
195
fe25519_mul(fe25519 * r,const fe25519 * x,const fe25519 * y)196 void fe25519_mul(fe25519 *r, const fe25519 *x, const fe25519 *y)
197 {
198 int i,j;
199 crypto_uint32 t[63];
200 for(i=0;i<63;i++)t[i] = 0;
201
202 for(i=0;i<32;i++)
203 for(j=0;j<32;j++)
204 t[i+j] += x->v[i] * y->v[j];
205
206 for(i=32;i<63;i++)
207 r->v[i-32] = t[i-32] + times38(t[i]);
208 r->v[31] = t[31]; /* result now in r[0]...r[31] */
209
210 reduce_mul(r);
211 }
212
fe25519_square(fe25519 * r,const fe25519 * x)213 void fe25519_square(fe25519 *r, const fe25519 *x)
214 {
215 fe25519_mul(r, x, x);
216 }
217
fe25519_invert(fe25519 * r,const fe25519 * x)218 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 /* 9 */ fe25519_mul(&z9,&t0,x);
236 /* 11 */ fe25519_mul(&z11,&z9,&z2);
237 /* 22 */ fe25519_square(&t0,&z11);
238 /* 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 /* 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 /* 2^20 - 2^10 */ for (i = 2;i < 10;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
250 /* 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 /* 2^40 - 2^20 */ for (i = 2;i < 20;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
255 /* 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 /* 2^50 - 2^10 */ for (i = 2;i < 10;i += 2) { fe25519_square(&t1,&t0); fe25519_square(&t0,&t1); }
260 /* 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 /* 2^100 - 2^50 */ for (i = 2;i < 50;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
265 /* 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 /* 2^200 - 2^100 */ for (i = 2;i < 100;i += 2) { fe25519_square(&t1,&t0); fe25519_square(&t0,&t1); }
270 /* 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 /* 2^250 - 2^50 */ for (i = 2;i < 50;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
275 /* 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 /* 2^255 - 21 */ fe25519_mul(r,&t1,&z11);
283 }
284
fe25519_pow2523(fe25519 * r,const fe25519 * x)285 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 /* 9 */ fe25519_mul(&z9,&t,x);
302 /* 11 */ fe25519_mul(&z11,&z9,&z2);
303 /* 22 */ fe25519_square(&t,&z11);
304 /* 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 /* 2^10 - 2^5 */ for (i = 1;i < 5;i++) { fe25519_square(&t,&t); }
308 /* 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 /* 2^20 - 2^10 */ for (i = 1;i < 10;i++) { fe25519_square(&t,&t); }
312 /* 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 /* 2^40 - 2^20 */ for (i = 1;i < 20;i++) { fe25519_square(&t,&t); }
316 /* 2^40 - 2^0 */ fe25519_mul(&t,&t,&z2_20_0);
317
318 /* 2^41 - 2^1 */ fe25519_square(&t,&t);
319 /* 2^50 - 2^10 */ for (i = 1;i < 10;i++) { fe25519_square(&t,&t); }
320 /* 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 /* 2^100 - 2^50 */ for (i = 1;i < 50;i++) { fe25519_square(&t,&t); }
324 /* 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 /* 2^200 - 2^100 */ for (i = 1;i < 100;i++) { fe25519_square(&t,&t); }
328 /* 2^200 - 2^0 */ fe25519_mul(&t,&t,&z2_100_0);
329
330 /* 2^201 - 2^1 */ fe25519_square(&t,&t);
331 /* 2^250 - 2^50 */ for (i = 1;i < 50;i++) { fe25519_square(&t,&t); }
332 /* 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 /* 2^252 - 3 */ fe25519_mul(r,&t,x);
337 }
338