1const std = @import("std");
2const crypto = std.crypto;
3const mem = std.mem;
4
5const NonCanonicalError = std.crypto.errors.NonCanonicalError;
6
7/// The scalar field order.
8pub const field_order: u256 = 7237005577332262213973186563042994240857116359379907606001950938285454250989;
9
10/// A compressed scalar
11pub const CompressedScalar = [32]u8;
12
13/// Zero
14pub const zero: [32]u8 = @splat(0);
15
16const field_order_s = s: {
17 var s: [32]u8 = undefined;
18 mem.writeInt(u256, &s, field_order, .little);
19 break :s s;
20};
21
22/// Reject a scalar whose encoding is not canonical.
23pub fn rejectNonCanonical(s: CompressedScalar) NonCanonicalError!void {
24 var c: u8 = 0;
25 var n: u8 = 1;
26 var i: usize = 31;
27 while (true) : (i -= 1) {
28 const xs = @as(u16, s[i]);
29 const xfield_order_s = @as(u16, field_order_s[i]);
30 c |= @as(u8, @intCast(((xs -% xfield_order_s) >> 8) & n));
31 n &= @as(u8, @intCast(((xs ^ xfield_order_s) -% 1) >> 8));
32 if (i == 0) break;
33 }
34 if (c == 0) {
35 return error.NonCanonical;
36 }
37}
38
39/// Reduce a scalar to the field size.
40pub fn reduce(s: CompressedScalar) CompressedScalar {
41 var scalar = Scalar.fromBytes(s);
42 return scalar.toBytes();
43}
44
45/// Reduce a 64-bytes scalar to the field size.
46pub fn reduce64(s: [64]u8) CompressedScalar {
47 var scalar = ScalarDouble.fromBytes64(s);
48 return scalar.toBytes();
49}
50
51/// Perform the X25519 "clamping" operation.
52/// The scalar is then guaranteed to be a multiple of the cofactor.
53pub fn clamp(s: *CompressedScalar) void {
54 s[0] &= 248;
55 s[31] = (s[31] & 127) | 64;
56}
57
58/// Return a*b (mod L)
59pub fn mul(a: CompressedScalar, b: CompressedScalar) CompressedScalar {
60 return Scalar.fromBytes(a).mul(Scalar.fromBytes(b)).toBytes();
61}
62
63/// Return a*b+c (mod L)
64pub fn mulAdd(a: CompressedScalar, b: CompressedScalar, c: CompressedScalar) CompressedScalar {
65 return Scalar.fromBytes(a).mul(Scalar.fromBytes(b)).add(Scalar.fromBytes(c)).toBytes();
66}
67
68/// Return a*8 (mod L)
69pub fn mul8(s: CompressedScalar) CompressedScalar {
70 var x = Scalar.fromBytes(s);
71 x = x.add(x);
72 x = x.add(x);
73 x = x.add(x);
74 return x.toBytes();
75}
76
77/// Return a+b (mod L)
78pub fn add(a: CompressedScalar, b: CompressedScalar) CompressedScalar {
79 return Scalar.fromBytes(a).add(Scalar.fromBytes(b)).toBytes();
80}
81
82/// Return -s (mod L)
83pub fn neg(s: CompressedScalar) CompressedScalar {
84 const fs: [64]u8 = field_order_s ++ @as([32]u8, @splat(0));
85 var sx: [64]u8 = undefined;
86 sx[0..32].* = s;
87 @memset(sx[32..], 0);
88 var carry: u32 = 0;
89 var i: usize = 0;
90 while (i < 64) : (i += 1) {
91 carry = @as(u32, fs[i]) -% sx[i] -% @as(u32, carry);
92 sx[i] = @as(u8, @truncate(carry));
93 carry = (carry >> 8) & 1;
94 }
95 return reduce64(sx);
96}
97
98/// Return (a-b) (mod L)
99pub fn sub(a: CompressedScalar, b: CompressedScalar) CompressedScalar {
100 return add(a, neg(b));
101}
102
103/// Return a random scalar < L
104pub fn random(io: std.Io) CompressedScalar {
105 return Scalar.random(io).toBytes();
106}
107
108/// A scalar in unpacked representation
109pub const Scalar = struct {
110 const Limbs = [5]u64;
111 limbs: Limbs = undefined,
112
113 /// Unpack a 32-byte representation of a scalar
114 pub fn fromBytes(bytes: CompressedScalar) Scalar {
115 var scalar = ScalarDouble.fromBytes32(bytes);
116 return scalar.reduce(5);
117 }
118
119 /// Unpack a 64-byte representation of a scalar
120 pub fn fromBytes64(bytes: [64]u8) Scalar {
121 var scalar = ScalarDouble.fromBytes64(bytes);
122 return scalar.reduce(5);
123 }
124
125 /// Pack a scalar into bytes
126 pub fn toBytes(expanded: *const Scalar) CompressedScalar {
127 var bytes: CompressedScalar = undefined;
128 var i: usize = 0;
129 while (i < 4) : (i += 1) {
130 mem.writeInt(u64, bytes[i * 7 ..][0..8], expanded.limbs[i], .little);
131 }
132 mem.writeInt(u32, bytes[i * 7 ..][0..4], @intCast(expanded.limbs[i]), .little);
133 return bytes;
134 }
135
136 /// Return true if the scalar is zero
137 pub fn isZero(n: Scalar) bool {
138 const limbs = n.limbs;
139 return (limbs[0] | limbs[1] | limbs[2] | limbs[3] | limbs[4]) == 0;
140 }
141
142 /// Return x+y (mod L)
143 pub fn add(x: Scalar, y: Scalar) Scalar {
144 const carry0 = (x.limbs[0] + y.limbs[0]) >> 56;
145 const t0 = (x.limbs[0] + y.limbs[0]) & 0xffffffffffffff;
146 const t00 = t0;
147 const c0 = carry0;
148 const carry1 = (x.limbs[1] + y.limbs[1] + c0) >> 56;
149 const t1 = (x.limbs[1] + y.limbs[1] + c0) & 0xffffffffffffff;
150 const t10 = t1;
151 const c1 = carry1;
152 const carry2 = (x.limbs[2] + y.limbs[2] + c1) >> 56;
153 const t2 = (x.limbs[2] + y.limbs[2] + c1) & 0xffffffffffffff;
154 const t20 = t2;
155 const c2 = carry2;
156 const carry = (x.limbs[3] + y.limbs[3] + c2) >> 56;
157 const t3 = (x.limbs[3] + y.limbs[3] + c2) & 0xffffffffffffff;
158 const t30 = t3;
159 const c3 = carry;
160 const t4 = x.limbs[4] + y.limbs[4] + c3;
161
162 const y01: u64 = 5175514460705773;
163 const y11: u64 = 70332060721272408;
164 const y21: u64 = 5342;
165 const y31: u64 = 0;
166 const y41: u64 = 268435456;
167
168 const b5 = (t00 -% y01) >> 63;
169 const t5 = ((b5 << 56) + t00) -% y01;
170 const b0 = b5;
171 const t01 = t5;
172 const b6 = (t10 -% (y11 + b0)) >> 63;
173 const t6 = ((b6 << 56) + t10) -% (y11 + b0);
174 const b1 = b6;
175 const t11 = t6;
176 const b7 = (t20 -% (y21 + b1)) >> 63;
177 const t7 = ((b7 << 56) + t20) -% (y21 + b1);
178 const b2 = b7;
179 const t21 = t7;
180 const b8 = (t30 -% (y31 + b2)) >> 63;
181 const t8 = ((b8 << 56) + t30) -% (y31 + b2);
182 const b3 = b8;
183 const t31 = t8;
184 const b = (t4 -% (y41 + b3)) >> 63;
185 const t = ((b << 56) + t4) -% (y41 + b3);
186 const b4 = b;
187 const t41 = t;
188
189 const mask = (b4 -% 1);
190 const z00 = t00 ^ (mask & (t00 ^ t01));
191 const z10 = t10 ^ (mask & (t10 ^ t11));
192 const z20 = t20 ^ (mask & (t20 ^ t21));
193 const z30 = t30 ^ (mask & (t30 ^ t31));
194 const z40 = t4 ^ (mask & (t4 ^ t41));
195
196 return Scalar{ .limbs = .{ z00, z10, z20, z30, z40 } };
197 }
198
199 /// Return x*r (mod L)
200 pub fn mul(x: Scalar, y: Scalar) Scalar {
201 const xy000 = @as(u128, x.limbs[0]) * @as(u128, y.limbs[0]);
202 const xy010 = @as(u128, x.limbs[0]) * @as(u128, y.limbs[1]);
203 const xy020 = @as(u128, x.limbs[0]) * @as(u128, y.limbs[2]);
204 const xy030 = @as(u128, x.limbs[0]) * @as(u128, y.limbs[3]);
205 const xy040 = @as(u128, x.limbs[0]) * @as(u128, y.limbs[4]);
206 const xy100 = @as(u128, x.limbs[1]) * @as(u128, y.limbs[0]);
207 const xy110 = @as(u128, x.limbs[1]) * @as(u128, y.limbs[1]);
208 const xy120 = @as(u128, x.limbs[1]) * @as(u128, y.limbs[2]);
209 const xy130 = @as(u128, x.limbs[1]) * @as(u128, y.limbs[3]);
210 const xy140 = @as(u128, x.limbs[1]) * @as(u128, y.limbs[4]);
211 const xy200 = @as(u128, x.limbs[2]) * @as(u128, y.limbs[0]);
212 const xy210 = @as(u128, x.limbs[2]) * @as(u128, y.limbs[1]);
213 const xy220 = @as(u128, x.limbs[2]) * @as(u128, y.limbs[2]);
214 const xy230 = @as(u128, x.limbs[2]) * @as(u128, y.limbs[3]);
215 const xy240 = @as(u128, x.limbs[2]) * @as(u128, y.limbs[4]);
216 const xy300 = @as(u128, x.limbs[3]) * @as(u128, y.limbs[0]);
217 const xy310 = @as(u128, x.limbs[3]) * @as(u128, y.limbs[1]);
218 const xy320 = @as(u128, x.limbs[3]) * @as(u128, y.limbs[2]);
219 const xy330 = @as(u128, x.limbs[3]) * @as(u128, y.limbs[3]);
220 const xy340 = @as(u128, x.limbs[3]) * @as(u128, y.limbs[4]);
221 const xy400 = @as(u128, x.limbs[4]) * @as(u128, y.limbs[0]);
222 const xy410 = @as(u128, x.limbs[4]) * @as(u128, y.limbs[1]);
223 const xy420 = @as(u128, x.limbs[4]) * @as(u128, y.limbs[2]);
224 const xy430 = @as(u128, x.limbs[4]) * @as(u128, y.limbs[3]);
225 const xy440 = @as(u128, x.limbs[4]) * @as(u128, y.limbs[4]);
226 const z00 = xy000;
227 const z10 = xy010 + xy100;
228 const z20 = xy020 + xy110 + xy200;
229 const z30 = xy030 + xy120 + xy210 + xy300;
230 const z40 = xy040 + xy130 + xy220 + xy310 + xy400;
231 const z50 = xy140 + xy230 + xy320 + xy410;
232 const z60 = xy240 + xy330 + xy420;
233 const z70 = xy340 + xy430;
234 const z80 = xy440;
235
236 const carry0 = z00 >> 56;
237 const t10 = @as(u64, @truncate(z00)) & 0xffffffffffffff;
238 const c00 = carry0;
239 const t00 = t10;
240 const carry1 = (z10 + c00) >> 56;
241 const t11 = @as(u64, @truncate((z10 + c00))) & 0xffffffffffffff;
242 const c10 = carry1;
243 const t12 = t11;
244 const carry2 = (z20 + c10) >> 56;
245 const t13 = @as(u64, @truncate((z20 + c10))) & 0xffffffffffffff;
246 const c20 = carry2;
247 const t20 = t13;
248 const carry3 = (z30 + c20) >> 56;
249 const t14 = @as(u64, @truncate((z30 + c20))) & 0xffffffffffffff;
250 const c30 = carry3;
251 const t30 = t14;
252 const carry4 = (z40 + c30) >> 56;
253 const t15 = @as(u64, @truncate((z40 + c30))) & 0xffffffffffffff;
254 const c40 = carry4;
255 const t40 = t15;
256 const carry5 = (z50 + c40) >> 56;
257 const t16 = @as(u64, @truncate((z50 + c40))) & 0xffffffffffffff;
258 const c50 = carry5;
259 const t50 = t16;
260 const carry6 = (z60 + c50) >> 56;
261 const t17 = @as(u64, @truncate((z60 + c50))) & 0xffffffffffffff;
262 const c60 = carry6;
263 const t60 = t17;
264 const carry7 = (z70 + c60) >> 56;
265 const t18 = @as(u64, @truncate((z70 + c60))) & 0xffffffffffffff;
266 const c70 = carry7;
267 const t70 = t18;
268 const carry8 = (z80 + c70) >> 56;
269 const t19 = @as(u64, @truncate((z80 + c70))) & 0xffffffffffffff;
270 const c80 = carry8;
271 const t80 = t19;
272 const t90 = (@as(u64, @truncate(c80)));
273 const r0 = t00;
274 const r1 = t12;
275 const r2 = t20;
276 const r3 = t30;
277 const r4 = t40;
278 const r5 = t50;
279 const r6 = t60;
280 const r7 = t70;
281 const r8 = t80;
282 const r9 = t90;
283
284 const m0: u64 = 5175514460705773;
285 const m1: u64 = 70332060721272408;
286 const m2: u64 = 5342;
287 const m3: u64 = 0;
288 const m4: u64 = 268435456;
289 const mu0: u64 = 44162584779952923;
290 const mu1: u64 = 9390964836247533;
291 const mu2: u64 = 72057594036560134;
292 const mu3: u64 = 72057594037927935;
293 const mu4: u64 = 68719476735;
294
295 const y_ = (r5 & 0xffffff) << 32;
296 const x_ = r4 >> 24;
297 const z01 = (x_ | y_);
298 const y_0 = (r6 & 0xffffff) << 32;
299 const x_0 = r5 >> 24;
300 const z11 = (x_0 | y_0);
301 const y_1 = (r7 & 0xffffff) << 32;
302 const x_1 = r6 >> 24;
303 const z21 = (x_1 | y_1);
304 const y_2 = (r8 & 0xffffff) << 32;
305 const x_2 = r7 >> 24;
306 const z31 = (x_2 | y_2);
307 const y_3 = (r9 & 0xffffff) << 32;
308 const x_3 = r8 >> 24;
309 const z41 = (x_3 | y_3);
310 const q0 = z01;
311 const q1 = z11;
312 const q2 = z21;
313 const q3 = z31;
314 const q4 = z41;
315 const xy001 = @as(u128, q0) * @as(u128, mu0);
316 const xy011 = @as(u128, q0) * @as(u128, mu1);
317 const xy021 = @as(u128, q0) * @as(u128, mu2);
318 const xy031 = @as(u128, q0) * @as(u128, mu3);
319 const xy041 = @as(u128, q0) * @as(u128, mu4);
320 const xy101 = @as(u128, q1) * @as(u128, mu0);
321 const xy111 = @as(u128, q1) * @as(u128, mu1);
322 const xy121 = @as(u128, q1) * @as(u128, mu2);
323 const xy131 = @as(u128, q1) * @as(u128, mu3);
324 const xy14 = @as(u128, q1) * @as(u128, mu4);
325 const xy201 = @as(u128, q2) * @as(u128, mu0);
326 const xy211 = @as(u128, q2) * @as(u128, mu1);
327 const xy221 = @as(u128, q2) * @as(u128, mu2);
328 const xy23 = @as(u128, q2) * @as(u128, mu3);
329 const xy24 = @as(u128, q2) * @as(u128, mu4);
330 const xy301 = @as(u128, q3) * @as(u128, mu0);
331 const xy311 = @as(u128, q3) * @as(u128, mu1);
332 const xy32 = @as(u128, q3) * @as(u128, mu2);
333 const xy33 = @as(u128, q3) * @as(u128, mu3);
334 const xy34 = @as(u128, q3) * @as(u128, mu4);
335 const xy401 = @as(u128, q4) * @as(u128, mu0);
336 const xy41 = @as(u128, q4) * @as(u128, mu1);
337 const xy42 = @as(u128, q4) * @as(u128, mu2);
338 const xy43 = @as(u128, q4) * @as(u128, mu3);
339 const xy44 = @as(u128, q4) * @as(u128, mu4);
340 const z02 = xy001;
341 const z12 = xy011 + xy101;
342 const z22 = xy021 + xy111 + xy201;
343 const z32 = xy031 + xy121 + xy211 + xy301;
344 const z42 = xy041 + xy131 + xy221 + xy311 + xy401;
345 const z5 = xy14 + xy23 + xy32 + xy41;
346 const z6 = xy24 + xy33 + xy42;
347 const z7 = xy34 + xy43;
348 const z8 = xy44;
349
350 const carry9 = z02 >> 56;
351 const c01 = carry9;
352 const carry10 = (z12 + c01) >> 56;
353 const c11 = carry10;
354 const carry11 = (z22 + c11) >> 56;
355 const c21 = carry11;
356 const carry12 = (z32 + c21) >> 56;
357 const c31 = carry12;
358 const carry13 = (z42 + c31) >> 56;
359 const t24 = @as(u64, @truncate(z42 + c31)) & 0xffffffffffffff;
360 const c41 = carry13;
361 const t41 = t24;
362 const carry14 = (z5 + c41) >> 56;
363 const t25 = @as(u64, @truncate(z5 + c41)) & 0xffffffffffffff;
364 const c5 = carry14;
365 const t5 = t25;
366 const carry15 = (z6 + c5) >> 56;
367 const t26 = @as(u64, @truncate(z6 + c5)) & 0xffffffffffffff;
368 const c6 = carry15;
369 const t6 = t26;
370 const carry16 = (z7 + c6) >> 56;
371 const t27 = @as(u64, @truncate(z7 + c6)) & 0xffffffffffffff;
372 const c7 = carry16;
373 const t7 = t27;
374 const carry17 = (z8 + c7) >> 56;
375 const t28 = @as(u64, @truncate(z8 + c7)) & 0xffffffffffffff;
376 const c8 = carry17;
377 const t8 = t28;
378 const t9 = @as(u64, @truncate(c8));
379
380 const qmu4_ = t41;
381 const qmu5_ = t5;
382 const qmu6_ = t6;
383 const qmu7_ = t7;
384 const qmu8_ = t8;
385 const qmu9_ = t9;
386 const y_4 = (qmu5_ & 0xffffffffff) << 16;
387 const x_4 = qmu4_ >> 40;
388 const z03 = (x_4 | y_4);
389 const y_5 = (qmu6_ & 0xffffffffff) << 16;
390 const x_5 = qmu5_ >> 40;
391 const z13 = (x_5 | y_5);
392 const y_6 = (qmu7_ & 0xffffffffff) << 16;
393 const x_6 = qmu6_ >> 40;
394 const z23 = (x_6 | y_6);
395 const y_7 = (qmu8_ & 0xffffffffff) << 16;
396 const x_7 = qmu7_ >> 40;
397 const z33 = (x_7 | y_7);
398 const y_8 = (qmu9_ & 0xffffffffff) << 16;
399 const x_8 = qmu8_ >> 40;
400 const z43 = (x_8 | y_8);
401 const qdiv0 = z03;
402 const qdiv1 = z13;
403 const qdiv2 = z23;
404 const qdiv3 = z33;
405 const qdiv4 = z43;
406 const r01 = r0;
407 const r11 = r1;
408 const r21 = r2;
409 const r31 = r3;
410 const r41 = (r4 & 0xffffffffff);
411
412 const xy00 = @as(u128, qdiv0) * @as(u128, m0);
413 const xy01 = @as(u128, qdiv0) * @as(u128, m1);
414 const xy02 = @as(u128, qdiv0) * @as(u128, m2);
415 const xy03 = @as(u128, qdiv0) * @as(u128, m3);
416 const xy04 = @as(u128, qdiv0) * @as(u128, m4);
417 const xy10 = @as(u128, qdiv1) * @as(u128, m0);
418 const xy11 = @as(u128, qdiv1) * @as(u128, m1);
419 const xy12 = @as(u128, qdiv1) * @as(u128, m2);
420 const xy13 = @as(u128, qdiv1) * @as(u128, m3);
421 const xy20 = @as(u128, qdiv2) * @as(u128, m0);
422 const xy21 = @as(u128, qdiv2) * @as(u128, m1);
423 const xy22 = @as(u128, qdiv2) * @as(u128, m2);
424 const xy30 = @as(u128, qdiv3) * @as(u128, m0);
425 const xy31 = @as(u128, qdiv3) * @as(u128, m1);
426 const xy40 = @as(u128, qdiv4) * @as(u128, m0);
427 const carry18 = xy00 >> 56;
428 const t29 = @as(u64, @truncate(xy00)) & 0xffffffffffffff;
429 const c0 = carry18;
430 const t01 = t29;
431 const carry19 = (xy01 + xy10 + c0) >> 56;
432 const t31 = @as(u64, @truncate(xy01 + xy10 + c0)) & 0xffffffffffffff;
433 const c12 = carry19;
434 const t110 = t31;
435 const carry20 = (xy02 + xy11 + xy20 + c12) >> 56;
436 const t32 = @as(u64, @truncate(xy02 + xy11 + xy20 + c12)) & 0xffffffffffffff;
437 const c22 = carry20;
438 const t210 = t32;
439 const carry = (xy03 + xy12 + xy21 + xy30 + c22) >> 56;
440 const t33 = @as(u64, @truncate(xy03 + xy12 + xy21 + xy30 + c22)) & 0xffffffffffffff;
441 const c32 = carry;
442 const t34 = t33;
443 const t42 = @as(u64, @truncate(xy04 + xy13 + xy22 + xy31 + xy40 + c32)) & 0xffffffffff;
444
445 const qmul0 = t01;
446 const qmul1 = t110;
447 const qmul2 = t210;
448 const qmul3 = t34;
449 const qmul4 = t42;
450 const b5 = (r01 -% qmul0) >> 63;
451 const t35 = ((b5 << 56) + r01) -% qmul0;
452 const c1 = b5;
453 const t02 = t35;
454 const b6 = (r11 -% (qmul1 + c1)) >> 63;
455 const t36 = ((b6 << 56) + r11) -% (qmul1 + c1);
456 const c2 = b6;
457 const t111 = t36;
458 const b7 = (r21 -% (qmul2 + c2)) >> 63;
459 const t37 = ((b7 << 56) + r21) -% (qmul2 + c2);
460 const c3 = b7;
461 const t211 = t37;
462 const b8 = (r31 -% (qmul3 + c3)) >> 63;
463 const t38 = ((b8 << 56) + r31) -% (qmul3 + c3);
464 const c4 = b8;
465 const t39 = t38;
466 const b9 = (r41 -% (qmul4 + c4)) >> 63;
467 const t43 = ((b9 << 40) + r41) -% (qmul4 + c4);
468 const t44 = t43;
469 const s0 = t02;
470 const s1 = t111;
471 const s2 = t211;
472 const s3 = t39;
473 const s4 = t44;
474
475 const y01: u64 = 5175514460705773;
476 const y11: u64 = 70332060721272408;
477 const y21: u64 = 5342;
478 const y31: u64 = 0;
479 const y41: u64 = 268435456;
480
481 const b10 = (s0 -% y01) >> 63;
482 const t45 = ((b10 << 56) + s0) -% y01;
483 const b0 = b10;
484 const t0 = t45;
485 const b11 = (s1 -% (y11 + b0)) >> 63;
486 const t46 = ((b11 << 56) + s1) -% (y11 + b0);
487 const b1 = b11;
488 const t1 = t46;
489 const b12 = (s2 -% (y21 + b1)) >> 63;
490 const t47 = ((b12 << 56) + s2) -% (y21 + b1);
491 const b2 = b12;
492 const t2 = t47;
493 const b13 = (s3 -% (y31 + b2)) >> 63;
494 const t48 = ((b13 << 56) + s3) -% (y31 + b2);
495 const b3 = b13;
496 const t3 = t48;
497 const b = (s4 -% (y41 + b3)) >> 63;
498 const t = ((b << 56) + s4) -% (y41 + b3);
499 const b4 = b;
500 const t4 = t;
501 const mask = (b4 -% @as(u64, @intCast(((1)))));
502 const z04 = s0 ^ (mask & (s0 ^ t0));
503 const z14 = s1 ^ (mask & (s1 ^ t1));
504 const z24 = s2 ^ (mask & (s2 ^ t2));
505 const z34 = s3 ^ (mask & (s3 ^ t3));
506 const z44 = s4 ^ (mask & (s4 ^ t4));
507
508 return Scalar{ .limbs = .{ z04, z14, z24, z34, z44 } };
509 }
510
511 /// Return x^2 (mod L)
512 pub fn sq(x: Scalar) Scalar {
513 return x.mul(x);
514 }
515
516 /// Square a scalar `n` times
517 fn sqn(x: Scalar, comptime n: comptime_int) Scalar {
518 var i: usize = 0;
519 var t = x;
520 while (i < n) : (i += 1) {
521 t = t.sq();
522 }
523 return t;
524 }
525
526 /// Square and multiply
527 fn sqn_mul(x: Scalar, comptime n: comptime_int, y: Scalar) Scalar {
528 return x.sqn(n).mul(y);
529 }
530
531 /// Return the inverse of a scalar (mod L), or 0 if x=0.
532 pub fn invert(x: Scalar) Scalar {
533 const _10 = x.sq();
534 const _11 = x.mul(_10);
535 const _100 = x.mul(_11);
536 const _1000 = _100.sq();
537 const _1010 = _10.mul(_1000);
538 const _1011 = x.mul(_1010);
539 const _10000 = _1000.sq();
540 const _10110 = _1011.sq();
541 const _100000 = _1010.mul(_10110);
542 const _100110 = _10000.mul(_10110);
543 const _1000000 = _100000.sq();
544 const _1010000 = _10000.mul(_1000000);
545 const _1010011 = _11.mul(_1010000);
546 const _1100011 = _10000.mul(_1010011);
547 const _1100111 = _100.mul(_1100011);
548 const _1101011 = _100.mul(_1100111);
549 const _10010011 = _1000000.mul(_1010011);
550 const _10010111 = _100.mul(_10010011);
551 const _10111101 = _100110.mul(_10010111);
552 const _11010011 = _10110.mul(_10111101);
553 const _11100111 = _1010000.mul(_10010111);
554 const _11101011 = _100.mul(_11100111);
555 const _11110101 = _1010.mul(_11101011);
556 return _1011.mul(_11110101).sqn_mul(126, _1010011).sqn_mul(9, _10).mul(_11110101)
557 .sqn_mul(7, _1100111).sqn_mul(9, _11110101).sqn_mul(11, _10111101).sqn_mul(8, _11100111)
558 .sqn_mul(9, _1101011).sqn_mul(6, _1011).sqn_mul(14, _10010011).sqn_mul(10, _1100011)
559 .sqn_mul(9, _10010111).sqn_mul(10, _11110101).sqn_mul(8, _11010011).sqn_mul(8, _11101011);
560 }
561
562 /// Return a random scalar < L.
563 pub fn random(io: std.Io) Scalar {
564 var s: [64]u8 = undefined;
565 while (true) {
566 io.random(&s);
567 const n = Scalar.fromBytes64(s);
568 if (!n.isZero()) {
569 return n;
570 }
571 }
572 }
573};
574
575const ScalarDouble = struct {
576 const Limbs = [10]u64;
577 limbs: Limbs = undefined,
578
579 fn fromBytes64(bytes: [64]u8) ScalarDouble {
580 var limbs: Limbs = undefined;
581 var i: usize = 0;
582 while (i < 9) : (i += 1) {
583 limbs[i] = mem.readInt(u64, bytes[i * 7 ..][0..8], .little) & 0xffffffffffffff;
584 }
585 limbs[i] = @as(u64, bytes[i * 7]);
586 return ScalarDouble{ .limbs = limbs };
587 }
588
589 fn fromBytes32(bytes: CompressedScalar) ScalarDouble {
590 var limbs: Limbs = undefined;
591 var i: usize = 0;
592 while (i < 4) : (i += 1) {
593 limbs[i] = mem.readInt(u64, bytes[i * 7 ..][0..8], .little) & 0xffffffffffffff;
594 }
595 limbs[i] = @as(u64, mem.readInt(u32, bytes[i * 7 ..][0..4], .little));
596 @memset(limbs[5..], 0);
597 return ScalarDouble{ .limbs = limbs };
598 }
599
600 fn toBytes(expanded_double: *ScalarDouble) CompressedScalar {
601 return expanded_double.reduce(10).toBytes();
602 }
603
604 /// Barrett reduction
605 fn reduce(expanded: *ScalarDouble, comptime limbs_count: usize) Scalar {
606 const t = expanded.limbs;
607 const t0 = if (limbs_count <= 0) 0 else t[0];
608 const t1 = if (limbs_count <= 1) 0 else t[1];
609 const t2 = if (limbs_count <= 2) 0 else t[2];
610 const t3 = if (limbs_count <= 3) 0 else t[3];
611 const t4 = if (limbs_count <= 4) 0 else t[4];
612 const t5 = if (limbs_count <= 5) 0 else t[5];
613 const t6 = if (limbs_count <= 6) 0 else t[6];
614 const t7 = if (limbs_count <= 7) 0 else t[7];
615 const t8 = if (limbs_count <= 8) 0 else t[8];
616 const t9 = if (limbs_count <= 9) 0 else t[9];
617
618 const m0: u64 = 5175514460705773;
619 const m1: u64 = 70332060721272408;
620 const m2: u64 = 5342;
621 const m3: u64 = 0;
622 const m4: u64 = 268435456;
623 const mu0: u64 = 44162584779952923;
624 const mu1: u64 = 9390964836247533;
625 const mu2: u64 = 72057594036560134;
626 const mu3: u64 = 0xffffffffffffff;
627 const mu4: u64 = 68719476735;
628
629 const y_ = (t5 & 0xffffff) << 32;
630 const x_ = t4 >> 24;
631 const z00 = x_ | y_;
632 const y_0 = (t6 & 0xffffff) << 32;
633 const x_0 = t5 >> 24;
634 const z10 = x_0 | y_0;
635 const y_1 = (t7 & 0xffffff) << 32;
636 const x_1 = t6 >> 24;
637 const z20 = x_1 | y_1;
638 const y_2 = (t8 & 0xffffff) << 32;
639 const x_2 = t7 >> 24;
640 const z30 = x_2 | y_2;
641 const y_3 = (t9 & 0xffffff) << 32;
642 const x_3 = t8 >> 24;
643 const z40 = x_3 | y_3;
644 const q0 = z00;
645 const q1 = z10;
646 const q2 = z20;
647 const q3 = z30;
648 const q4 = z40;
649
650 const xy000 = @as(u128, q0) * @as(u128, mu0);
651 const xy010 = @as(u128, q0) * @as(u128, mu1);
652 const xy020 = @as(u128, q0) * @as(u128, mu2);
653 const xy030 = @as(u128, q0) * @as(u128, mu3);
654 const xy040 = @as(u128, q0) * @as(u128, mu4);
655 const xy100 = @as(u128, q1) * @as(u128, mu0);
656 const xy110 = @as(u128, q1) * @as(u128, mu1);
657 const xy120 = @as(u128, q1) * @as(u128, mu2);
658 const xy130 = @as(u128, q1) * @as(u128, mu3);
659 const xy14 = @as(u128, q1) * @as(u128, mu4);
660 const xy200 = @as(u128, q2) * @as(u128, mu0);
661 const xy210 = @as(u128, q2) * @as(u128, mu1);
662 const xy220 = @as(u128, q2) * @as(u128, mu2);
663 const xy23 = @as(u128, q2) * @as(u128, mu3);
664 const xy24 = @as(u128, q2) * @as(u128, mu4);
665 const xy300 = @as(u128, q3) * @as(u128, mu0);
666 const xy310 = @as(u128, q3) * @as(u128, mu1);
667 const xy32 = @as(u128, q3) * @as(u128, mu2);
668 const xy33 = @as(u128, q3) * @as(u128, mu3);
669 const xy34 = @as(u128, q3) * @as(u128, mu4);
670 const xy400 = @as(u128, q4) * @as(u128, mu0);
671 const xy41 = @as(u128, q4) * @as(u128, mu1);
672 const xy42 = @as(u128, q4) * @as(u128, mu2);
673 const xy43 = @as(u128, q4) * @as(u128, mu3);
674 const xy44 = @as(u128, q4) * @as(u128, mu4);
675 const z01 = xy000;
676 const z11 = xy010 + xy100;
677 const z21 = xy020 + xy110 + xy200;
678 const z31 = xy030 + xy120 + xy210 + xy300;
679 const z41 = xy040 + xy130 + xy220 + xy310 + xy400;
680 const z5 = xy14 + xy23 + xy32 + xy41;
681 const z6 = xy24 + xy33 + xy42;
682 const z7 = xy34 + xy43;
683 const z8 = xy44;
684
685 const carry0 = z01 >> 56;
686 const c00 = carry0;
687 const carry1 = (z11 + c00) >> 56;
688 const c10 = carry1;
689 const carry2 = (z21 + c10) >> 56;
690 const c20 = carry2;
691 const carry3 = (z31 + c20) >> 56;
692 const c30 = carry3;
693 const carry4 = (z41 + c30) >> 56;
694 const t103 = @as(u64, @as(u64, @truncate(z41 + c30))) & 0xffffffffffffff;
695 const c40 = carry4;
696 const t410 = t103;
697 const carry5 = (z5 + c40) >> 56;
698 const t104 = @as(u64, @as(u64, @truncate(z5 + c40))) & 0xffffffffffffff;
699 const c5 = carry5;
700 const t51 = t104;
701 const carry6 = (z6 + c5) >> 56;
702 const t105 = @as(u64, @as(u64, @truncate(z6 + c5))) & 0xffffffffffffff;
703 const c6 = carry6;
704 const t61 = t105;
705 const carry7 = (z7 + c6) >> 56;
706 const t106 = @as(u64, @as(u64, @truncate(z7 + c6))) & 0xffffffffffffff;
707 const c7 = carry7;
708 const t71 = t106;
709 const carry8 = (z8 + c7) >> 56;
710 const t107 = @as(u64, @as(u64, @truncate(z8 + c7))) & 0xffffffffffffff;
711 const c8 = carry8;
712 const t81 = t107;
713 const t91 = @as(u64, @as(u64, @truncate(c8)));
714
715 const qmu4_ = t410;
716 const qmu5_ = t51;
717 const qmu6_ = t61;
718 const qmu7_ = t71;
719 const qmu8_ = t81;
720 const qmu9_ = t91;
721 const y_4 = (qmu5_ & 0xffffffffff) << 16;
722 const x_4 = qmu4_ >> 40;
723 const z02 = x_4 | y_4;
724 const y_5 = (qmu6_ & 0xffffffffff) << 16;
725 const x_5 = qmu5_ >> 40;
726 const z12 = x_5 | y_5;
727 const y_6 = (qmu7_ & 0xffffffffff) << 16;
728 const x_6 = qmu6_ >> 40;
729 const z22 = x_6 | y_6;
730 const y_7 = (qmu8_ & 0xffffffffff) << 16;
731 const x_7 = qmu7_ >> 40;
732 const z32 = x_7 | y_7;
733 const y_8 = (qmu9_ & 0xffffffffff) << 16;
734 const x_8 = qmu8_ >> 40;
735 const z42 = x_8 | y_8;
736 const qdiv0 = z02;
737 const qdiv1 = z12;
738 const qdiv2 = z22;
739 const qdiv3 = z32;
740 const qdiv4 = z42;
741 const r0 = t0;
742 const r1 = t1;
743 const r2 = t2;
744 const r3 = t3;
745 const r4 = t4 & 0xffffffffff;
746
747 const xy00 = @as(u128, qdiv0) * @as(u128, m0);
748 const xy01 = @as(u128, qdiv0) * @as(u128, m1);
749 const xy02 = @as(u128, qdiv0) * @as(u128, m2);
750 const xy03 = @as(u128, qdiv0) * @as(u128, m3);
751 const xy04 = @as(u128, qdiv0) * @as(u128, m4);
752 const xy10 = @as(u128, qdiv1) * @as(u128, m0);
753 const xy11 = @as(u128, qdiv1) * @as(u128, m1);
754 const xy12 = @as(u128, qdiv1) * @as(u128, m2);
755 const xy13 = @as(u128, qdiv1) * @as(u128, m3);
756 const xy20 = @as(u128, qdiv2) * @as(u128, m0);
757 const xy21 = @as(u128, qdiv2) * @as(u128, m1);
758 const xy22 = @as(u128, qdiv2) * @as(u128, m2);
759 const xy30 = @as(u128, qdiv3) * @as(u128, m0);
760 const xy31 = @as(u128, qdiv3) * @as(u128, m1);
761 const xy40 = @as(u128, qdiv4) * @as(u128, m0);
762 const carry9 = xy00 >> 56;
763 const t108 = @as(u64, @truncate(xy00)) & 0xffffffffffffff;
764 const c0 = carry9;
765 const t010 = t108;
766 const carry10 = (xy01 + xy10 + c0) >> 56;
767 const t109 = @as(u64, @truncate(xy01 + xy10 + c0)) & 0xffffffffffffff;
768 const c11 = carry10;
769 const t110 = t109;
770 const carry11 = (xy02 + xy11 + xy20 + c11) >> 56;
771 const t1010 = @as(u64, @truncate(xy02 + xy11 + xy20 + c11)) & 0xffffffffffffff;
772 const c21 = carry11;
773 const t210 = t1010;
774 const carry = (xy03 + xy12 + xy21 + xy30 + c21) >> 56;
775 const t1011 = @as(u64, @truncate(xy03 + xy12 + xy21 + xy30 + c21)) & 0xffffffffffffff;
776 const c31 = carry;
777 const t310 = t1011;
778 const t411 = @as(u64, @truncate(xy04 + xy13 + xy22 + xy31 + xy40 + c31)) & 0xffffffffff;
779
780 const qmul0 = t010;
781 const qmul1 = t110;
782 const qmul2 = t210;
783 const qmul3 = t310;
784 const qmul4 = t411;
785 const b5 = (r0 -% qmul0) >> 63;
786 const t1012 = ((b5 << 56) + r0) -% qmul0;
787 const c1 = b5;
788 const t011 = t1012;
789 const b6 = (r1 -% (qmul1 + c1)) >> 63;
790 const t1013 = ((b6 << 56) + r1) -% (qmul1 + c1);
791 const c2 = b6;
792 const t111 = t1013;
793 const b7 = (r2 -% (qmul2 + c2)) >> 63;
794 const t1014 = ((b7 << 56) + r2) -% (qmul2 + c2);
795 const c3 = b7;
796 const t211 = t1014;
797 const b8 = (r3 -% (qmul3 + c3)) >> 63;
798 const t1015 = ((b8 << 56) + r3) -% (qmul3 + c3);
799 const c4 = b8;
800 const t311 = t1015;
801 const b9 = (r4 -% (qmul4 + c4)) >> 63;
802 const t1016 = ((b9 << 40) + r4) -% (qmul4 + c4);
803 const t412 = t1016;
804 const s0 = t011;
805 const s1 = t111;
806 const s2 = t211;
807 const s3 = t311;
808 const s4 = t412;
809
810 const y0: u64 = 5175514460705773;
811 const y1: u64 = 70332060721272408;
812 const y2: u64 = 5342;
813 const y3: u64 = 0;
814 const y4: u64 = 268435456;
815
816 const b10 = (s0 -% y0) >> 63;
817 const t1017 = ((b10 << 56) + s0) -% y0;
818 const b0 = b10;
819 const t01 = t1017;
820 const b11 = (s1 -% (y1 + b0)) >> 63;
821 const t1018 = ((b11 << 56) + s1) -% (y1 + b0);
822 const b1 = b11;
823 const t11 = t1018;
824 const b12 = (s2 -% (y2 + b1)) >> 63;
825 const t1019 = ((b12 << 56) + s2) -% (y2 + b1);
826 const b2 = b12;
827 const t21 = t1019;
828 const b13 = (s3 -% (y3 + b2)) >> 63;
829 const t1020 = ((b13 << 56) + s3) -% (y3 + b2);
830 const b3 = b13;
831 const t31 = t1020;
832 const b = (s4 -% (y4 + b3)) >> 63;
833 const t10 = ((b << 56) + s4) -% (y4 + b3);
834 const b4 = b;
835 const t41 = t10;
836 const mask = b4 -% @as(u64, @as(u64, 1));
837 const z03 = s0 ^ (mask & (s0 ^ t01));
838 const z13 = s1 ^ (mask & (s1 ^ t11));
839 const z23 = s2 ^ (mask & (s2 ^ t21));
840 const z33 = s3 ^ (mask & (s3 ^ t31));
841 const z43 = s4 ^ (mask & (s4 ^ t41));
842
843 return Scalar{ .limbs = .{ z03, z13, z23, z33, z43 } };
844 }
845};
846
847test "scalar25519" {
848 const bytes: [32]u8 = .{ 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 255 };
849 var x = Scalar.fromBytes(bytes);
850 var y = x.toBytes();
851 try rejectNonCanonical(y);
852 var buf: [128]u8 = undefined;
853 try std.testing.expectEqualStrings(try std.mem.print(&buf, "{X}", .{&y}), "1E979B917937F3DE71D18077F961F6CEFF01030405060708010203040506070F");
854
855 const reduced = reduce(field_order_s);
856 try std.testing.expectEqualStrings(try std.mem.print(&buf, "{X}", .{&reduced}), "0000000000000000000000000000000000000000000000000000000000000000");
857}
858
859test "non-canonical scalar25519" {
860 const too_targe: [32]u8 = .{ 0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10 };
861 try std.testing.expectError(error.NonCanonical, rejectNonCanonical(too_targe));
862}
863
864test "mulAdd overflow check" {
865 const a: [32]u8 = @splat(0xff);
866 const b: [32]u8 = @splat(0xff);
867 const c: [32]u8 = @splat(0xff);
868 const x = mulAdd(a, b, c);
869 var buf: [128]u8 = undefined;
870 try std.testing.expectEqualStrings(try std.mem.print(&buf, "{X}", .{&x}), "D14DF91389432C25AD60FF9791B9FD1D67BEF517D273ECCE3D9A307C1B419903");
871}
872
873test "scalar field inversion" {
874 const bytes: [32]u8 = .{ 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 8 };
875 const x = Scalar.fromBytes(bytes);
876 const inv = x.invert();
877 const recovered_x = inv.invert();
878 try std.testing.expectEqualSlices(u8, &bytes, &recovered_x.toBytes());
879}
880
881test "random scalar" {
882 const io = std.testing.io;
883 const s1 = random(io);
884 const s2 = random(io);
885 try std.testing.expect(!mem.eql(u8, &s1, &s2));
886}
887
888test "64-bit reduction" {
889 const bytes = field_order_s ++ @as([32]u8, @splat(0));
890 const x = Scalar.fromBytes64(bytes);
891 try std.testing.expect(x.isZero());
892}