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 "libwebsockets.h"
10
11 #define WINDOWSIZE 1 /* Should be 1,2, or 4 */
12 #define WINDOWMASK ((1<<WINDOWSIZE)-1)
13
14 #include "fe25519.h"
15
fe_equal(uint32_t a,uint32_t b)16 static uint32_t fe_equal(uint32_t a,uint32_t b) /* 16-bit inputs */
17 {
18 uint32_t 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(uint32_t a,uint32_t b)24 static uint32_t ge(uint32_t a,uint32_t 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(uint32_t a)33 static uint32_t times19(uint32_t a)
34 {
35 return (a << 4) + (a << 1) + a;
36 }
37
times38(uint32_t a)38 static uint32_t times38(uint32_t a)
39 {
40 return (a << 5) + (a << 2) + (a << 1);
41 }
42
fe_reduce_add_sub(fe25519 * r)43 static void fe_reduce_add_sub(fe25519 *r)
44 {
45 uint32_t 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 uint32_t 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 uint32_t m = fe_equal(r->v[31],127);
88
89 for(i=30;i>0;i--)
90 m &= fe_equal(r->v[i],255);
91 m &= ge(r->v[0],237);
92
93 m = -(int32_t)m;
94
95 r->v[31] -= m&127;
96 for(i=30;i>0;i--)
97 r->v[i] -= m&255;
98 r->v[0] -= m&237;
99 }
100
fe25519_unpack(fe25519 * r,const unsigned char x[32])101 void fe25519_unpack(fe25519 *r, const unsigned char x[32])
102 {
103 int i;
104 for(i=0;i<32;i++) r->v[i] = x[i];
105 r->v[31] &= 127;
106 }
107
108 /* Assumes input x being reduced below 2^255 */
fe25519_pack(unsigned char r[32],const fe25519 * x)109 void fe25519_pack(unsigned char r[32], const fe25519 *x)
110 {
111 int i;
112 fe25519 y = *x;
113 fe25519_freeze(&y);
114 for(i=0;i<32;i++)
115 r[i] = y.v[i];
116 }
117
fe25519_iszero(const fe25519 * x)118 int fe25519_iszero(const fe25519 *x)
119 {
120 int i;
121 int r;
122 fe25519 t = *x;
123 fe25519_freeze(&t);
124 r = fe_equal(t.v[0],0);
125 for(i=1;i<32;i++)
126 r &= fe_equal(t.v[i],0);
127 return r;
128 }
129
fe25519_iseq_vartime(const fe25519 * x,const fe25519 * y)130 int fe25519_iseq_vartime(const fe25519 *x, const fe25519 *y)
131 {
132 int i;
133 fe25519 t1 = *x;
134 fe25519 t2 = *y;
135 fe25519_freeze(&t1);
136 fe25519_freeze(&t2);
137 for(i=0;i<32;i++)
138 if(t1.v[i] != t2.v[i]) return 0;
139 return 1;
140 }
141
fe25519_cmov(fe25519 * r,const fe25519 * x,unsigned char b)142 void fe25519_cmov(fe25519 *r, const fe25519 *x, unsigned char b)
143 {
144 int i;
145 uint32_t mask = b;
146 mask = -(int32_t)mask;
147 for(i=0;i<32;i++) r->v[i] ^= mask & (x->v[i] ^ r->v[i]);
148 }
149
fe25519_getparity(const fe25519 * x)150 unsigned char fe25519_getparity(const fe25519 *x)
151 {
152 fe25519 t = *x;
153 fe25519_freeze(&t);
154 return (unsigned char)(t.v[0] & 1);
155 }
156
fe25519_setone(fe25519 * r)157 void fe25519_setone(fe25519 *r)
158 {
159 int i;
160 r->v[0] = 1;
161 for(i=1;i<32;i++) r->v[i]=0;
162 }
163
fe25519_setzero(fe25519 * r)164 void fe25519_setzero(fe25519 *r)
165 {
166 int i;
167 for(i=0;i<32;i++) r->v[i]=0;
168 }
169
fe25519_neg(fe25519 * r,const fe25519 * x)170 void fe25519_neg(fe25519 *r, const fe25519 *x)
171 {
172 fe25519 t;
173 int i;
174 for(i=0;i<32;i++) t.v[i]=x->v[i];
175 fe25519_setzero(r);
176 fe25519_sub(r, r, &t);
177 }
178
fe25519_add(fe25519 * r,const fe25519 * x,const fe25519 * y)179 void fe25519_add(fe25519 *r, const fe25519 *x, const fe25519 *y)
180 {
181 int i;
182 for(i=0;i<32;i++) r->v[i] = x->v[i] + y->v[i];
183 fe_reduce_add_sub(r);
184 }
185
fe25519_sub(fe25519 * r,const fe25519 * x,const fe25519 * y)186 void fe25519_sub(fe25519 *r, const fe25519 *x, const fe25519 *y)
187 {
188 int i;
189 uint32_t t[32];
190 t[0] = x->v[0] + 0x1da;
191 t[31] = x->v[31] + 0xfe;
192 for(i=1;i<31;i++) t[i] = x->v[i] + 0x1fe;
193 for(i=0;i<32;i++) r->v[i] = t[i] - y->v[i];
194 fe_reduce_add_sub(r);
195 }
196
fe25519_mul(fe25519 * r,const fe25519 * x,const fe25519 * y)197 void fe25519_mul(fe25519 *r, const fe25519 *x, const fe25519 *y)
198 {
199 int i,j;
200 uint32_t t[63];
201 for(i=0;i<63;i++)t[i] = 0;
202
203 for(i=0;i<32;i++)
204 for(j=0;j<32;j++)
205 t[i+j] += x->v[i] * y->v[j];
206
207 for(i=32;i<63;i++)
208 r->v[i-32] = t[i-32] + times38(t[i]);
209 r->v[31] = t[31]; /* result now in r[0]...r[31] */
210
211 reduce_mul(r);
212 }
213
fe25519_square(fe25519 * r,const fe25519 * x)214 void fe25519_square(fe25519 *r, const fe25519 *x)
215 {
216 fe25519_mul(r, x, x);
217 }
218
fe25519_invert(fe25519 * r,const fe25519 * x)219 void fe25519_invert(fe25519 *r, const fe25519 *x)
220 {
221 fe25519 z2;
222 fe25519 z9;
223 fe25519 z11;
224 fe25519 z2_5_0;
225 fe25519 z2_10_0;
226 fe25519 z2_20_0;
227 fe25519 z2_50_0;
228 fe25519 z2_100_0;
229 fe25519 t0;
230 fe25519 t1;
231 int i;
232
233 /* 2 */ fe25519_square(&z2,x);
234 /* 4 */ fe25519_square(&t1,&z2);
235 /* 8 */ fe25519_square(&t0,&t1);
236 /* 9 */ fe25519_mul(&z9,&t0,x);
237 /* 11 */ fe25519_mul(&z11,&z9,&z2);
238 /* 22 */ fe25519_square(&t0,&z11);
239 /* 2^5 - 2^0 = 31 */ fe25519_mul(&z2_5_0,&t0,&z9);
240
241 /* 2^6 - 2^1 */ fe25519_square(&t0,&z2_5_0);
242 /* 2^7 - 2^2 */ fe25519_square(&t1,&t0);
243 /* 2^8 - 2^3 */ fe25519_square(&t0,&t1);
244 /* 2^9 - 2^4 */ fe25519_square(&t1,&t0);
245 /* 2^10 - 2^5 */ fe25519_square(&t0,&t1);
246 /* 2^10 - 2^0 */ fe25519_mul(&z2_10_0,&t0,&z2_5_0);
247
248 /* 2^11 - 2^1 */ fe25519_square(&t0,&z2_10_0);
249 /* 2^12 - 2^2 */ fe25519_square(&t1,&t0);
250 /* 2^20 - 2^10 */ for (i = 2;i < 10;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
251 /* 2^20 - 2^0 */ fe25519_mul(&z2_20_0,&t1,&z2_10_0);
252
253 /* 2^21 - 2^1 */ fe25519_square(&t0,&z2_20_0);
254 /* 2^22 - 2^2 */ fe25519_square(&t1,&t0);
255 /* 2^40 - 2^20 */ for (i = 2;i < 20;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
256 /* 2^40 - 2^0 */ fe25519_mul(&t0,&t1,&z2_20_0);
257
258 /* 2^41 - 2^1 */ fe25519_square(&t1,&t0);
259 /* 2^42 - 2^2 */ fe25519_square(&t0,&t1);
260 /* 2^50 - 2^10 */ for (i = 2;i < 10;i += 2) { fe25519_square(&t1,&t0); fe25519_square(&t0,&t1); }
261 /* 2^50 - 2^0 */ fe25519_mul(&z2_50_0,&t0,&z2_10_0);
262
263 /* 2^51 - 2^1 */ fe25519_square(&t0,&z2_50_0);
264 /* 2^52 - 2^2 */ fe25519_square(&t1,&t0);
265 /* 2^100 - 2^50 */ for (i = 2;i < 50;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
266 /* 2^100 - 2^0 */ fe25519_mul(&z2_100_0,&t1,&z2_50_0);
267
268 /* 2^101 - 2^1 */ fe25519_square(&t1,&z2_100_0);
269 /* 2^102 - 2^2 */ fe25519_square(&t0,&t1);
270 /* 2^200 - 2^100 */ for (i = 2;i < 100;i += 2) { fe25519_square(&t1,&t0); fe25519_square(&t0,&t1); }
271 /* 2^200 - 2^0 */ fe25519_mul(&t1,&t0,&z2_100_0);
272
273 /* 2^201 - 2^1 */ fe25519_square(&t0,&t1);
274 /* 2^202 - 2^2 */ fe25519_square(&t1,&t0);
275 /* 2^250 - 2^50 */ for (i = 2;i < 50;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); }
276 /* 2^250 - 2^0 */ fe25519_mul(&t0,&t1,&z2_50_0);
277
278 /* 2^251 - 2^1 */ fe25519_square(&t1,&t0);
279 /* 2^252 - 2^2 */ fe25519_square(&t0,&t1);
280 /* 2^253 - 2^3 */ fe25519_square(&t1,&t0);
281 /* 2^254 - 2^4 */ fe25519_square(&t0,&t1);
282 /* 2^255 - 2^5 */ fe25519_square(&t1,&t0);
283 /* 2^255 - 21 */ fe25519_mul(r,&t1,&z11);
284 }
285
fe25519_pow2523(fe25519 * r,const fe25519 * x)286 void fe25519_pow2523(fe25519 *r, const fe25519 *x)
287 {
288 fe25519 z2;
289 fe25519 z9;
290 fe25519 z11;
291 fe25519 z2_5_0;
292 fe25519 z2_10_0;
293 fe25519 z2_20_0;
294 fe25519 z2_50_0;
295 fe25519 z2_100_0;
296 fe25519 t;
297 int i;
298
299 /* 2 */ fe25519_square(&z2,x);
300 /* 4 */ fe25519_square(&t,&z2);
301 /* 8 */ fe25519_square(&t,&t);
302 /* 9 */ fe25519_mul(&z9,&t,x);
303 /* 11 */ fe25519_mul(&z11,&z9,&z2);
304 /* 22 */ fe25519_square(&t,&z11);
305 /* 2^5 - 2^0 = 31 */ fe25519_mul(&z2_5_0,&t,&z9);
306
307 /* 2^6 - 2^1 */ fe25519_square(&t,&z2_5_0);
308 /* 2^10 - 2^5 */ for (i = 1;i < 5;i++) { fe25519_square(&t,&t); }
309 /* 2^10 - 2^0 */ fe25519_mul(&z2_10_0,&t,&z2_5_0);
310
311 /* 2^11 - 2^1 */ fe25519_square(&t,&z2_10_0);
312 /* 2^20 - 2^10 */ for (i = 1;i < 10;i++) { fe25519_square(&t,&t); }
313 /* 2^20 - 2^0 */ fe25519_mul(&z2_20_0,&t,&z2_10_0);
314
315 /* 2^21 - 2^1 */ fe25519_square(&t,&z2_20_0);
316 /* 2^40 - 2^20 */ for (i = 1;i < 20;i++) { fe25519_square(&t,&t); }
317 /* 2^40 - 2^0 */ fe25519_mul(&t,&t,&z2_20_0);
318
319 /* 2^41 - 2^1 */ fe25519_square(&t,&t);
320 /* 2^50 - 2^10 */ for (i = 1;i < 10;i++) { fe25519_square(&t,&t); }
321 /* 2^50 - 2^0 */ fe25519_mul(&z2_50_0,&t,&z2_10_0);
322
323 /* 2^51 - 2^1 */ fe25519_square(&t,&z2_50_0);
324 /* 2^100 - 2^50 */ for (i = 1;i < 50;i++) { fe25519_square(&t,&t); }
325 /* 2^100 - 2^0 */ fe25519_mul(&z2_100_0,&t,&z2_50_0);
326
327 /* 2^101 - 2^1 */ fe25519_square(&t,&z2_100_0);
328 /* 2^200 - 2^100 */ for (i = 1;i < 100;i++) { fe25519_square(&t,&t); }
329 /* 2^200 - 2^0 */ fe25519_mul(&t,&t,&z2_100_0);
330
331 /* 2^201 - 2^1 */ fe25519_square(&t,&t);
332 /* 2^250 - 2^50 */ for (i = 1;i < 50;i++) { fe25519_square(&t,&t); }
333 /* 2^250 - 2^0 */ fe25519_mul(&t,&t,&z2_50_0);
334
335 /* 2^251 - 2^1 */ fe25519_square(&t,&t);
336 /* 2^252 - 2^2 */ fe25519_square(&t,&t);
337 /* 2^252 - 3 */ fe25519_mul(r,&t,x);
338 }
339