Debian Codegraph @

crypto/ed25519/edwards25519.ha

raw
1 // SPDX-License-Identifier: MPL-2.0
2 // (c) Hare authors <https://harelang.org>
3
4 def FIELDSZ: size = 16;
5 export type elem = [FIELDSZ]i64;
6
7 const feZero: elem = [0...];
8 const feOne: elem = [1, 0...];
9 const D: elem = [0x78a3, 0x1359, 0x4dca, 0x75eb, 0xd8ab, 0x4141, 0x0a4d, 0x0070, 0xe898, 0x7779, 0x4079, 0x8cc7, 0xfe73, 0x2b6f, 0x6cee, 0x5203];
10 const D2: elem = [0xf159, 0x26b2, 0x9b94, 0xebd6, 0xb156, 0x8283, 0x149a, 0x00e0, 0xd130, 0xeef3, 0x80f2, 0x198e, 0xfce7, 0x56df, 0xd9dc, 0x2406];
11 const X: elem = [0xd51a, 0x8f25, 0x2d60, 0xc956, 0xa7b2, 0x9525, 0xc760, 0x692c, 0xdc5c, 0xfdd6, 0xe231, 0xc0a4, 0x53fe, 0xcd6e, 0x36d3, 0x2169];
12 const Y: elem = [0x6658, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666];
13 const I: elem = [0xa0b0, 0x4a0e, 0x1b27, 0xc4ee, 0xe478, 0xad2f, 0x1806, 0x2f43, 0xd7a7, 0x3dfb, 0x0099, 0x2b4d, 0xdf0b, 0x4fc1, 0x2480, 0x2b83];
14
15 fn fe_reduce(fe: *elem) void = {
16 let carry: i64 = 0;
17 for (let i = 0z; i < FIELDSZ; i += 1) {
18 carry = fe[i] >> 16;
19 fe[i] -= (carry << 16);
20 if (i+1 < FIELDSZ) {
21 fe[i + 1] += carry;
22 } else {
23 fe[0] += (38 * carry);
24 };
25 };
26 };
27
28 fn fe_add(out: *elem, a: const *elem, b: const *elem) *elem = {
29 for (let i = 0z; i < FIELDSZ; i += 1) {
30 out[i] = a[i] + b[i];
31 };
32 return out;
33 };
34
35 fn fe_sub(out: *elem, a: const *elem, b: const *elem) *elem = {
36 for (let i = 0z; i < FIELDSZ; i += 1) {
37 out[i] = a[i] - b[i];
38 };
39 return out;
40 };
41
42 fn fe_negate(out: *elem, a: const *elem) *elem = {
43 return fe_sub(out, &feZero, a);
44 };
45
46 fn fe_mul(out: *elem, a: const *elem, b: const *elem) *elem = {
47 let prod: [31]i64 = [0...];
48 for (let i = 0z; i < FIELDSZ; i += 1) {
49 for (let j = 0z; j < FIELDSZ; j += 1) {
50 prod[i + j] += a[i] * b[j];
51 };
52 };
53 for (let i = 0; i < 15; i += 1) {
54 prod[i] += (38 * prod[i + 16]);
55 };
56 out[0..FIELDSZ] = prod[0..FIELDSZ];
57 fe_reduce(out);
58 fe_reduce(out);
59 return out;
60 };
61
62 fn fe_square(out: *elem, a: const *elem) *elem = {
63 return fe_mul(out, a, a);
64 };
65
66 // out = i ** (2**252 - 3)
67 fn fe_pow2523(out: *elem, a: *elem) *elem = {
68 let c: elem = [0...];
69 c[..] = a[..];
70 for (let i = 250i; i >= 0; i -= 1) {
71 fe_square(&c, &c);
72 if (i != 1) {
73 fe_mul(&c, &c, a);
74 };
75 };
76 out[..] = c[..];
77 return out;
78 };
79
80 fn fe_inv(out: *elem, a: const *elem) *elem = {
81 let c: elem = [0...];
82 c[..] = a[..];
83 for (let i = 253i; i >= 0; i -= 1) {
84 fe_square(&c, &c);
85 if (i != 2 && i != 4) {
86 fe_mul(&c, &c, a);
87 };
88 };
89 out[..] = c[..];
90 return out;
91 };
92
93 fn fe_parity(a: const *elem) u8 = {
94 let d: scalar = [0...];
95 fe_encode(&d, a);
96 return d[0]&1;
97 };
98
99 // a == b -> 0
100 // a != b -> 1
101 fn fe_cmp(a: const *elem, b: const *elem) u8 = {
102 let x: scalar = [0...];
103 fe_encode(&x, a);
104 let y: scalar = [0...];
105 fe_encode(&y, b);
106
107 // constant-time compare
108 let d: u32 = 0;
109 for (let i = 0z; i < SCALARSZ; i += 1) {
110 d |= x[i] ^ y[i];
111 };
112 return (1 & ((d - 1) >> 8): u8) - 1;
113 };
114
115 // swap p and q if bit is 1, otherwise noop
116 fn fe_swap(p: *elem, q: *elem, bit: u8) void = {
117 let c = ~(bit: u64 - 1): i64;
118 for (let i = 0z; i < FIELDSZ; i += 1) {
119 let t = c & (p[i] ^ q[i]);
120 p[i] ^= t;
121 q[i] ^= t;
122 };
123 };
124
125 fn fe_encode(out: *scalar, a: const *elem) void = {
126 let m: elem = [0...];
127 let t: elem = *a;
128
129 fe_reduce(&t);
130 fe_reduce(&t);
131 fe_reduce(&t);
132
133 for (let _i = 0; _i < 2; _i += 1) {
134 m[0] = t[0] - 0xffed;
135 for (let i = 1z; i < 15; i += 1) {
136 m[i] = t[i] - 0xffff - ((m[i - 1] >> 16) & 1);
137 m[i - 1] &= 0xffff;
138 };
139 m[15] = t[15] - 0x7fff - ((m[14] >> 16) & 1);
140 let b = ((m[15] >> 16): u8) & 1;
141 m[14] &= 0xffff;
142 fe_swap(&t, &m, 1-b);
143 };
144
145 for (let i = 0z; i < FIELDSZ; i += 1) {
146 out[2*i+0] = (t[i] & 0xff): u8;
147 out[2*i+1] = (t[i] >> 8): u8;
148 };
149 };
150
151 // len(in) must be SCALARSZ
152 fn fe_decode(fe: *elem, in: []u8) *elem = {
153 for (let i = 0z; i < FIELDSZ; i += 1) {
154 fe[i] = in[2 * i]: i64 + ((in[2 * i + 1]: i64) << 8);
155 };
156 fe[15] &= 0x7fff;
157 return fe;
158 };
159
160
161 def SCALARSZ: size = 32;
162 type scalar = [SCALARSZ]u8;
163
164 const L: scalar = [
165 0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7, 0xa2,
166 0xde, 0xf9, 0xde, 0x14, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
167 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10,
168 ];
169
170 fn scalar_clamp(s: *scalar) void = {
171 s[0] &= 248;
172 s[31] &= 127;
173 s[31] |= 64;
174 };
175
176 // r = x % -1
177 fn scalar_mod_L(r: *scalar, x: *[64]i64) void = {
178 for (let i: i64 = 63; i >= 32; i -= 1) {
179 let carry: i64 = 0;
180 let j = i - 32;
181 for (j < i - 12; j += 1) {
182 x[j] += carry - 16 * x[i] * (L[j - (i - 32)]: i64);
183 carry = (x[j] + 128) >> 8;
184 x[j] -= carry << 8;
185 };
186 x[j] += carry;
187 x[i] = 0;
188 };
189
190 let carry: i64 = 0;
191 for (let j = 0; j < 32; j += 1) {
192 x[j] += carry - (x[31] >> 4) * (L[j]: i64);
193 carry = x[j] >> 8;
194 x[j] &= 255;
195 };
196 for (let j = 0; j < 32; j += 1) {
197 x[j] -= carry * (L[j]: i64);
198 };
199 for (let i = 0; i < 32; i += 1) {
200 x[i+1] += x[i] >> 8;
201 r[i] = (x[i]&255): u8;
202 };
203 };
204
205 fn scalar_reduce(r: *scalar, h: *[64]u8) void = {
206 let x: [64]i64 = [0...];
207 for (let i = 0; i < 64; i += 1) {
208 x[i] = h[i]: i64;
209 };
210 scalar_mod_L(r, &x);
211 };
212
213 // s = a*b + c
214 fn scalar_multiply_add(s: *scalar, a: *scalar, b: *scalar, c: *scalar) void = {
215 let x: [64]i64 = [0...];
216 for (let i = 0; i < 32; i += 1) {
217 for (let j = 0; j < 32; j += 1) {
218 x[i+j] += (a[i]: i64) * (b[j]: i64);
219 };
220 };
221 for (let i = 0; i < 32; i += 1) {
222 x[i] += (c[i]: i64);
223 };
224 scalar_mod_L(s, &x);
225 };
226
227
228 def POINTSZ: size = 32;
229
230 export type point = struct {
231 x: elem,
232 y: elem,
233 z: elem,
234 t: elem,
235 };
236
237 // out = p += q
238 fn point_add(out: *point, p: *point, q: *point) *point = {
239 let a: elem = [0...];
240 let b: elem = [0...];
241 let c: elem = [0...];
242 let d: elem = [0...];
243 let t: elem = [0...];
244 let e: elem = [0...];
245 let f: elem = [0...];
246 let g: elem = [0...];
247 let h: elem = [0...];
248
249 fe_sub(&a, &p.y, &p.x);
250 fe_sub(&t, &q.y, &q.x);
251 fe_mul(&a, &a, &t);
252 fe_add(&b, &p.x, &p.y);
253 fe_add(&t, &q.x, &q.y);
254 fe_mul(&b, &b, &t);
255 fe_mul(&c, &p.t, &q.t);
256 fe_mul(&c, &c, &D2);
257 fe_mul(&d, &p.z, &q.z);
258 fe_add(&d, &d, &d);
259 fe_sub(&e, &b, &a);
260 fe_sub(&f, &d, &c);
261 fe_add(&g, &d, &c);
262 fe_add(&h, &b, &a);
263
264 fe_mul(&out.x, &e, &f);
265 fe_mul(&out.y, &h, &g);
266 fe_mul(&out.z, &g, &f);
267 fe_mul(&out.t, &e, &h);
268 return out;
269 };
270
271 // swap p and q if bit is 1, otherwise noop
272 fn point_swap(p: *point, q: *point, bit: u8) void = {
273 fe_swap(&p.x, &q.x, bit);
274 fe_swap(&p.y, &q.y, bit);
275 fe_swap(&p.z, &q.z, bit);
276 fe_swap(&p.t, &q.t, bit);
277 };
278
279 // p = q * s
280 fn scalarmult(p: *point, q: *point, s: const *scalar) *point = {
281 p.x[..] = feZero[..];
282 p.y[..] = feOne[..];
283 p.z[..] = feOne[..];
284 p.t[..] = feZero[..];
285 for (let i = 255; i >= 0; i -= 1) {
286 let b: u8 = (s[i/8]>>((i: u8)&7))&1;
287 point_swap(p, q, b);
288 point_add(q, q, p);
289 point_add(p, p, p);
290 point_swap(p, q, b);
291 };
292 return p;
293 };
294
295 // p = B * s
296 fn scalarmult_base(p: *point, s: const *scalar) *point = {
297 let B = point {...};
298 B.x[..] = X[..];
299 B.y[..] = Y[..];
300 B.z[..] = feOne[..];
301 fe_mul(&B.t, &X, &Y);
302
303 return scalarmult(p, &B, s);
304 };
305
306 fn point_encode(out: *scalar, p: *point) void = {
307 let tx: elem = [0...];
308 let ty: elem = [0...];
309 let zi: elem = [0...];
310 fe_inv(&zi, &p.z);
311 fe_mul(&tx, &p.x, &zi);
312 fe_mul(&ty, &p.y, &zi);
313 fe_encode(out, &ty);
314 out[31] ^= fe_parity(&tx) << 7;
315 };
316
317 // len(in) must be POINTSZ
318 fn point_decode(p: *point, in: []u8) bool = {
319 let t: elem = [0...];
320 let chk: elem = [0...];
321 let num: elem = [0...];
322 let den: elem = [0...];
323 let den2: elem = [0...];
324 let den4: elem = [0...];
325 let den6: elem = [0...];
326 p.z[..] = feOne[..];
327 fe_decode(&p.y, in);
328 fe_square(&num, &p.y);
329 fe_mul(&den, &num, &D);
330 fe_sub(&num, &num, &p.z);
331 fe_add(&den, &p.z, &den);
332
333 fe_square(&den2, &den);
334 fe_square(&den4, &den2);
335 fe_mul(&den6, &den4, &den2);
336 fe_mul(&t, &den6, &num);
337 fe_mul(&t, &t, &den);
338
339 fe_pow2523(&t, &t);
340 fe_mul(&t, &t, &num);
341 fe_mul(&t, &t, &den);
342 fe_mul(&t, &t, &den);
343 fe_mul(&p.x, &t, &den);
344
345 fe_square(&chk, &p.x);
346 fe_mul(&chk, &chk, &den);
347 if (fe_cmp(&chk, &num) != 0) {
348 fe_mul(&p.x, &p.x, &I);
349 };
350
351 fe_square(&chk, &p.x);
352 fe_mul(&chk, &chk, &den);
353 if (fe_cmp(&chk, &num) != 0) {
354 return false;
355 };
356
357 if (fe_parity(&p.x) == (in[31]>>7)) {
358 fe_negate(&p.x, &p.x);
359 };
360
361 fe_mul(&p.t, &p.x, &p.y);
362 return true;
363 };