tsc25519.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
---
tsc25519.c (7243B)
---
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/sc25519.c
5 */
6
7 #include "sc25519.h"
8
9 /*Arithmetic modulo the group order m = 2^252 + 27742317777372353535851937790883648493 = 7237005577332262213973186563042994240857116359379907606001950938285454250989 */
10
11 static const crypto_uint32 m[32] = {0xED, 0xD3, 0xF5, 0x5C, 0x1A, 0x63, 0x12, 0x58, 0xD6, 0x9C, 0xF7, 0xA2, 0xDE, 0xF9, 0xDE, 0x14,
12 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10};
13
14 static const crypto_uint32 mu[33] = {0x1B, 0x13, 0x2C, 0x0A, 0xA3, 0xE5, 0x9C, 0xED, 0xA7, 0x29, 0x63, 0x08, 0x5D, 0x21, 0x06, 0x21,
15 0xEB, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x0F};
16
17 static crypto_uint32 lt(crypto_uint32 a,crypto_uint32 b) /* 16-bit inputs */
18 {
19 unsigned int x = a;
20 x -= (unsigned int) b; /* 0..65535: no; 4294901761..4294967295: yes */
21 x >>= 31; /* 0: no; 1: yes */
22 return x;
23 }
24
25 /* Reduce coefficients of r before calling reduce_add_sub */
26 static void reduce_add_sub(sc25519 *r)
27 {
28 crypto_uint32 pb = 0;
29 crypto_uint32 b;
30 crypto_uint32 mask;
31 int i;
32 unsigned char t[32];
33
34 for(i=0;i<32;i++)
35 {
36 pb += m[i];
37 b = lt(r->v[i],pb);
38 t[i] = r->v[i]-pb+(b<<8);
39 pb = b;
40 }
41 mask = b - 1;
42 for(i=0;i<32;i++)
43 r->v[i] ^= mask & (r->v[i] ^ t[i]);
44 }
45
46 /* Reduce coefficients of x before calling barrett_reduce */
47 static void barrett_reduce(sc25519 *r, const crypto_uint32 x[64])
48 {
49 /* See HAC, Alg. 14.42 */
50 int i,j;
51 crypto_uint32 q2[66];
52 crypto_uint32 *q3 = q2 + 33;
53 crypto_uint32 r1[33];
54 crypto_uint32 r2[33];
55 crypto_uint32 carry;
56 crypto_uint32 pb = 0;
57 crypto_uint32 b;
58
59 for (i = 0;i < 66;++i) q2[i] = 0;
60 for (i = 0;i < 33;++i) r2[i] = 0;
61
62 for(i=0;i<33;i++)
63 for(j=0;j<33;j++)
64 if(i+j >= 31) q2[i+j] += mu[i]*x[j+31];
65 carry = q2[31] >> 8;
66 q2[32] += carry;
67 carry = q2[32] >> 8;
68 q2[33] += carry;
69
70 for(i=0;i<33;i++)r1[i] = x[i];
71 for(i=0;i<32;i++)
72 for(j=0;j<33;j++)
73 if(i+j < 33) r2[i+j] += m[i]*q3[j];
74
75 for(i=0;i<32;i++)
76 {
77 carry = r2[i] >> 8;
78 r2[i+1] += carry;
79 r2[i] &= 0xff;
80 }
81
82 for(i=0;i<32;i++)
83 {
84 pb += r2[i];
85 b = lt(r1[i],pb);
86 r->v[i] = r1[i]-pb+(b<<8);
87 pb = b;
88 }
89
90 /* XXX: Can it really happen that r<0?, See HAC, Alg 14.42, Step 3
91 * If so: Handle it here!
92 */
93
94 reduce_add_sub(r);
95 reduce_add_sub(r);
96 }
97
98 void sc25519_from32bytes(sc25519 *r, const unsigned char x[32])
99 {
100 int i;
101 crypto_uint32 t[64];
102 for(i=0;i<32;i++) t[i] = x[i];
103 for(i=32;i<64;++i) t[i] = 0;
104 barrett_reduce(r, t);
105 }
106
107 void shortsc25519_from16bytes(shortsc25519 *r, const unsigned char x[16])
108 {
109 int i;
110 for(i=0;i<16;i++) r->v[i] = x[i];
111 }
112
113 void sc25519_from64bytes(sc25519 *r, const unsigned char x[64])
114 {
115 int i;
116 crypto_uint32 t[64];
117 for(i=0;i<64;i++) t[i] = x[i];
118 barrett_reduce(r, t);
119 }
120
121 void sc25519_from_shortsc(sc25519 *r, const shortsc25519 *x)
122 {
123 int i;
124 for(i=0;i<16;i++)
125 r->v[i] = x->v[i];
126 for(i=0;i<16;i++)
127 r->v[16+i] = 0;
128 }
129
130 void sc25519_to32bytes(unsigned char r[32], const sc25519 *x)
131 {
132 int i;
133 for(i=0;i<32;i++) r[i] = x->v[i];
134 }
135
136 int sc25519_iszero_vartime(const sc25519 *x)
137 {
138 int i;
139 for(i=0;i<32;i++)
140 if(x->v[i] != 0) return 0;
141 return 1;
142 }
143
144 int sc25519_isshort_vartime(const sc25519 *x)
145 {
146 int i;
147 for(i=31;i>15;i--)
148 if(x->v[i] != 0) return 0;
149 return 1;
150 }
151
152 int sc25519_lt_vartime(const sc25519 *x, const sc25519 *y)
153 {
154 int i;
155 for(i=31;i>=0;i--)
156 {
157 if(x->v[i] < y->v[i]) return 1;
158 if(x->v[i] > y->v[i]) return 0;
159 }
160 return 0;
161 }
162
163 void sc25519_add(sc25519 *r, const sc25519 *x, const sc25519 *y)
164 {
165 int i, carry;
166 for(i=0;i<32;i++) r->v[i] = x->v[i] + y->v[i];
167 for(i=0;i<31;i++)
168 {
169 carry = r->v[i] >> 8;
170 r->v[i+1] += carry;
171 r->v[i] &= 0xff;
172 }
173 reduce_add_sub(r);
174 }
175
176 void sc25519_sub_nored(sc25519 *r, const sc25519 *x, const sc25519 *y)
177 {
178 crypto_uint32 b = 0;
179 crypto_uint32 t;
180 int i;
181 for(i=0;i<32;i++)
182 {
183 t = x->v[i] - y->v[i] - b;
184 r->v[i] = t & 255;
185 b = (t >> 8) & 1;
186 }
187 }
188
189 void sc25519_mul(sc25519 *r, const sc25519 *x, const sc25519 *y)
190 {
191 int i,j,carry;
192 crypto_uint32 t[64];
193 for(i=0;i<64;i++)t[i] = 0;
194
195 for(i=0;i<32;i++)
196 for(j=0;j<32;j++)
197 t[i+j] += x->v[i] * y->v[j];
198
199 /* Reduce coefficients */
200 for(i=0;i<63;i++)
201 {
202 carry = t[i] >> 8;
203 t[i+1] += carry;
204 t[i] &= 0xff;
205 }
206
207 barrett_reduce(r, t);
208 }
209
210 void sc25519_mul_shortsc(sc25519 *r, const sc25519 *x, const shortsc25519 *y)
211 {
212 sc25519 t;
213 sc25519_from_shortsc(&t, y);
214 sc25519_mul(r, x, &t);
215 }
216
217 void sc25519_window3(signed char r[85], const sc25519 *s)
218 {
219 char carry;
220 int i;
221 for(i=0;i<10;i++)
222 {
223 r[8*i+0] = s->v[3*i+0] & 7;
224 r[8*i+1] = (s->v[3*i+0] >> 3) & 7;
225 r[8*i+2] = (s->v[3*i+0] >> 6) & 7;
226 r[8*i+2] ^= (s->v[3*i+1] << 2) & 7;
227 r[8*i+3] = (s->v[3*i+1] >> 1) & 7;
228 r[8*i+4] = (s->v[3*i+1] >> 4) & 7;
229 r[8*i+5] = (s->v[3*i+1] >> 7) & 7;
230 r[8*i+5] ^= (s->v[3*i+2] << 1) & 7;
231 r[8*i+6] = (s->v[3*i+2] >> 2) & 7;
232 r[8*i+7] = (s->v[3*i+2] >> 5) & 7;
233 }
234 r[8*i+0] = s->v[3*i+0] & 7;
235 r[8*i+1] = (s->v[3*i+0] >> 3) & 7;
236 r[8*i+2] = (s->v[3*i+0] >> 6) & 7;
237 r[8*i+2] ^= (s->v[3*i+1] << 2) & 7;
238 r[8*i+3] = (s->v[3*i+1] >> 1) & 7;
239 r[8*i+4] = (s->v[3*i+1] >> 4) & 7;
240
241 /* Making it signed */
242 carry = 0;
243 for(i=0;i<84;i++)
244 {
245 r[i] += carry;
246 r[i+1] += r[i] >> 3;
247 r[i] &= 7;
248 carry = r[i] >> 2;
249 r[i] -= carry<<3;
250 }
251 r[84] += carry;
252 }
253
254 void sc25519_window5(signed char r[51], const sc25519 *s)
255 {
256 char carry;
257 int i;
258 for(i=0;i<6;i++)
259 {
260 r[8*i+0] = s->v[5*i+0] & 31;
261 r[8*i+1] = (s->v[5*i+0] >> 5) & 31;
262 r[8*i+1] ^= (s->v[5*i+1] << 3) & 31;
263 r[8*i+2] = (s->v[5*i+1] >> 2) & 31;
264 r[8*i+3] = (s->v[5*i+1] >> 7) & 31;
265 r[8*i+3] ^= (s->v[5*i+2] << 1) & 31;
266 r[8*i+4] = (s->v[5*i+2] >> 4) & 31;
267 r[8*i+4] ^= (s->v[5*i+3] << 4) & 31;
268 r[8*i+5] = (s->v[5*i+3] >> 1) & 31;
269 r[8*i+6] = (s->v[5*i+3] >> 6) & 31;
270 r[8*i+6] ^= (s->v[5*i+4] << 2) & 31;
271 r[8*i+7] = (s->v[5*i+4] >> 3) & 31;
272 }
273 r[8*i+0] = s->v[5*i+0] & 31;
274 r[8*i+1] = (s->v[5*i+0] >> 5) & 31;
275 r[8*i+1] ^= (s->v[5*i+1] << 3) & 31;
276 r[8*i+2] = (s->v[5*i+1] >> 2) & 31;
277
278 /* Making it signed */
279 carry = 0;
280 for(i=0;i<50;i++)
281 {
282 r[i] += carry;
283 r[i+1] += r[i] >> 5;
284 r[i] &= 31;
285 carry = r[i] >> 4;
286 r[i] -= carry<<5;
287 }
288 r[50] += carry;
289 }
290
291 void sc25519_2interleave2(unsigned char r[127], const sc25519 *s1, const sc25519 *s2)
292 {
293 int i;
294 for(i=0;i<31;i++)
295 {
296 r[4*i] = ( s1->v[i] & 3) ^ (( s2->v[i] & 3) << 2);
297 r[4*i+1] = ((s1->v[i] >> 2) & 3) ^ (((s2->v[i] >> 2) & 3) << 2);
298 r[4*i+2] = ((s1->v[i] >> 4) & 3) ^ (((s2->v[i] >> 4) & 3) << 2);
299 r[4*i+3] = ((s1->v[i] >> 6) & 3) ^ (((s2->v[i] >> 6) & 3) << 2);
300 }
301 r[124] = ( s1->v[31] & 3) ^ (( s2->v[31] & 3) << 2);
302 r[125] = ((s1->v[31] >> 2) & 3) ^ (((s2->v[31] >> 2) & 3) << 2);
303 r[126] = ((s1->v[31] >> 4) & 3) ^ (((s2->v[31] >> 4) & 3) << 2);
304 }