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