xref: /openssh-portable/fe25519.c (revision f45f78ae)
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