1const std = @import("std");
2const builtin = @import("builtin");
3const crypto = std.crypto;
4
5const NonCanonicalError = crypto.errors.NonCanonicalError;
6const NotSquareError = crypto.errors.NotSquareError;
7
8// Inline conditionally, when it can result in large code generation.
9const bloaty_inline: std.builtin.CallingConvention = switch (builtin.mode) {
10 .safe, .fast => .@"inline",
11 .debug, .small => .auto,
12};
13
14pub const Fe = struct {
15 limbs: [5]u64,
16
17 const MASK51: u64 = 0x7ffffffffffff;
18
19 /// 0
20 pub const zero = Fe{ .limbs = .{ 0, 0, 0, 0, 0 } };
21
22 /// 1
23 pub const one = Fe{ .limbs = .{ 1, 0, 0, 0, 0 } };
24
25 /// sqrt(-1)
26 pub const sqrtm1 = Fe{ .limbs = .{ 1718705420411056, 234908883556509, 2233514472574048, 2117202627021982, 765476049583133 } };
27
28 /// The Curve25519 base point
29 pub const curve25519BasePoint = Fe{ .limbs = .{ 9, 0, 0, 0, 0 } };
30
31 /// Edwards25519 d = 37095705934669439343138083508754565189542113879843219016388785533085940283555
32 pub const edwards25519d = Fe{ .limbs = .{ 929955233495203, 466365720129213, 1662059464998953, 2033849074728123, 1442794654840575 } };
33
34 /// Edwards25519 2d
35 pub const edwards25519d2 = Fe{ .limbs = .{ 1859910466990425, 932731440258426, 1072319116312658, 1815898335770999, 633789495995903 } };
36
37 /// Edwards25519 1/sqrt(a-d)
38 pub const edwards25519sqrtamd = Fe{ .limbs = .{ 278908739862762, 821645201101625, 8113234426968, 1777959178193151, 2118520810568447 } };
39
40 /// Edwards25519 1-d^2
41 pub const edwards25519eonemsqd = Fe{ .limbs = .{ 1136626929484150, 1998550399581263, 496427632559748, 118527312129759, 45110755273534 } };
42
43 /// Edwards25519 (d-1)^2
44 pub const edwards25519sqdmone = Fe{ .limbs = .{ 1507062230895904, 1572317787530805, 683053064812840, 317374165784489, 1572899562415810 } };
45
46 /// Edwards25519 sqrt(ad-1) with a = -1 (mod p)
47 pub const edwards25519sqrtadm1 = Fe{ .limbs = .{ 2241493124984347, 425987919032274, 2207028919301688, 1220490630685848, 974799131293748 } };
48
49 /// Edwards25519 A, as a single limb
50 pub const edwards25519a_32: u32 = 486662;
51
52 /// Edwards25519 A
53 pub const edwards25519a = Fe{ .limbs = .{ @as(u64, edwards25519a_32), 0, 0, 0, 0 } };
54
55 /// Edwards25519 sqrt(A-2)
56 pub const edwards25519sqrtam2 = Fe{ .limbs = .{ 1693982333959686, 608509411481997, 2235573344831311, 947681270984193, 266558006233600 } };
57
58 /// Return true if the field element is zero
59 pub fn isZero(fe: Fe) bool {
60 var reduced = fe;
61 reduced.reduce();
62 const limbs = reduced.limbs;
63 return (limbs[0] | limbs[1] | limbs[2] | limbs[3] | limbs[4]) == 0;
64 }
65
66 /// Return true if both field elements are equivalent
67 pub fn equivalent(a: Fe, b: Fe) bool {
68 return a.sub(b).isZero();
69 }
70
71 /// Unpack a field element
72 pub fn fromBytes(s: [32]u8) Fe {
73 var fe: Fe = undefined;
74 fe.limbs[0] = std.mem.readInt(u64, s[0..8], .little) & MASK51;
75 fe.limbs[1] = (std.mem.readInt(u64, s[6..14], .little) >> 3) & MASK51;
76 fe.limbs[2] = (std.mem.readInt(u64, s[12..20], .little) >> 6) & MASK51;
77 fe.limbs[3] = (std.mem.readInt(u64, s[19..27], .little) >> 1) & MASK51;
78 fe.limbs[4] = (std.mem.readInt(u64, s[24..32], .little) >> 12) & MASK51;
79
80 return fe;
81 }
82
83 /// Pack a field element
84 pub fn toBytes(fe: Fe) [32]u8 {
85 var reduced = fe;
86 reduced.reduce();
87 var s: [32]u8 = undefined;
88 std.mem.writeInt(u64, s[0..8], reduced.limbs[0] | (reduced.limbs[1] << 51), .little);
89 std.mem.writeInt(u64, s[8..16], (reduced.limbs[1] >> 13) | (reduced.limbs[2] << 38), .little);
90 std.mem.writeInt(u64, s[16..24], (reduced.limbs[2] >> 26) | (reduced.limbs[3] << 25), .little);
91 std.mem.writeInt(u64, s[24..32], (reduced.limbs[3] >> 39) | (reduced.limbs[4] << 12), .little);
92
93 return s;
94 }
95
96 /// Map a 64 bytes big endian string into a field element
97 pub fn fromBytes64(s: [64]u8) Fe {
98 var fl: [32]u8 = undefined;
99 var gl: [32]u8 = undefined;
100 var i: usize = 0;
101 while (i < 32) : (i += 1) {
102 fl[i] = s[63 - i];
103 gl[i] = s[31 - i];
104 }
105 fl[31] &= 0x7f;
106 gl[31] &= 0x7f;
107 var fe_f = fromBytes(fl);
108 const fe_g = fromBytes(gl);
109 fe_f.limbs[0] += (s[32] >> 7) * 19 + @as(u10, s[0] >> 7) * 722;
110 i = 0;
111 while (i < 5) : (i += 1) {
112 fe_f.limbs[i] += 38 * fe_g.limbs[i];
113 }
114 fe_f.reduce();
115 return fe_f;
116 }
117
118 /// Reject non-canonical encodings of an element, possibly ignoring the top bit
119 pub fn rejectNonCanonical(s: [32]u8, comptime ignore_extra_bit: bool) NonCanonicalError!void {
120 var c: u16 = (s[31] & 0x7f) ^ 0x7f;
121 comptime var i = 30;
122 inline while (i > 0) : (i -= 1) {
123 c |= s[i] ^ 0xff;
124 }
125 c = (c -% 1) >> 8;
126 const d = (@as(u16, 0xed - 1) -% @as(u16, s[0])) >> 8;
127 const x = if (ignore_extra_bit) 0 else s[31] >> 7;
128 if ((((c & d) | x) & 1) != 0) {
129 return error.NonCanonical;
130 }
131 }
132
133 /// Reduce a field element mod 2^255-19
134 fn reduce(fe: *Fe) void {
135 comptime var i = 0;
136 comptime var j = 0;
137 const limbs = &fe.limbs;
138 inline while (j < 2) : (j += 1) {
139 i = 0;
140 inline while (i < 4) : (i += 1) {
141 limbs[i + 1] += limbs[i] >> 51;
142 limbs[i] &= MASK51;
143 }
144 limbs[0] += 19 * (limbs[4] >> 51);
145 limbs[4] &= MASK51;
146 }
147 limbs[0] += 19;
148 i = 0;
149 inline while (i < 4) : (i += 1) {
150 limbs[i + 1] += limbs[i] >> 51;
151 limbs[i] &= MASK51;
152 }
153 limbs[0] += 19 * (limbs[4] >> 51);
154 limbs[4] &= MASK51;
155
156 limbs[0] += 0x8000000000000 - 19;
157 limbs[1] += 0x8000000000000 - 1;
158 limbs[2] += 0x8000000000000 - 1;
159 limbs[3] += 0x8000000000000 - 1;
160 limbs[4] += 0x8000000000000 - 1;
161
162 i = 0;
163 inline while (i < 4) : (i += 1) {
164 limbs[i + 1] += limbs[i] >> 51;
165 limbs[i] &= MASK51;
166 }
167 limbs[4] &= MASK51;
168 }
169
170 /// Add a field element
171 pub fn add(a: Fe, b: Fe) Fe {
172 var fe: Fe = undefined;
173 comptime var i = 0;
174 inline while (i < 5) : (i += 1) {
175 fe.limbs[i] = a.limbs[i] + b.limbs[i];
176 }
177 return fe;
178 }
179
180 /// Subtract a field element
181 pub fn sub(a: Fe, b: Fe) Fe {
182 var fe = b;
183 comptime var i = 0;
184 inline while (i < 4) : (i += 1) {
185 fe.limbs[i + 1] += fe.limbs[i] >> 51;
186 fe.limbs[i] &= MASK51;
187 }
188 fe.limbs[0] += 19 * (fe.limbs[4] >> 51);
189 fe.limbs[4] &= MASK51;
190 fe.limbs[0] = (a.limbs[0] + 0xfffffffffffda) - fe.limbs[0];
191 fe.limbs[1] = (a.limbs[1] + 0xffffffffffffe) - fe.limbs[1];
192 fe.limbs[2] = (a.limbs[2] + 0xffffffffffffe) - fe.limbs[2];
193 fe.limbs[3] = (a.limbs[3] + 0xffffffffffffe) - fe.limbs[3];
194 fe.limbs[4] = (a.limbs[4] + 0xffffffffffffe) - fe.limbs[4];
195
196 return fe;
197 }
198
199 /// Negate a field element
200 pub fn neg(a: Fe) Fe {
201 return zero.sub(a);
202 }
203
204 /// Return true if a field element is negative
205 pub fn isNegative(a: Fe) bool {
206 return (a.toBytes()[0] & 1) != 0;
207 }
208
209 /// Conditonally replace a field element with `a` if `c` is positive
210 pub fn cMov(fe: *Fe, a: Fe, c: u64) void {
211 const mask: u64 = 0 -% c;
212 var x = fe.*;
213 comptime var i = 0;
214 inline while (i < 5) : (i += 1) {
215 x.limbs[i] ^= a.limbs[i];
216 }
217 i = 0;
218 inline while (i < 5) : (i += 1) {
219 x.limbs[i] &= mask;
220 }
221 i = 0;
222 inline while (i < 5) : (i += 1) {
223 fe.limbs[i] ^= x.limbs[i];
224 }
225 }
226
227 /// Conditionally swap two pairs of field elements if `c` is positive
228 pub fn cSwap2(a0: *Fe, b0: *Fe, a1: *Fe, b1: *Fe, c: u64) void {
229 const mask: u64 = 0 -% c;
230 var x0 = a0.*;
231 var x1 = a1.*;
232 comptime var i = 0;
233 inline while (i < 5) : (i += 1) {
234 x0.limbs[i] ^= b0.limbs[i];
235 x1.limbs[i] ^= b1.limbs[i];
236 }
237 i = 0;
238 inline while (i < 5) : (i += 1) {
239 x0.limbs[i] &= mask;
240 x1.limbs[i] &= mask;
241 }
242 i = 0;
243 inline while (i < 5) : (i += 1) {
244 a0.limbs[i] ^= x0.limbs[i];
245 b0.limbs[i] ^= x0.limbs[i];
246 a1.limbs[i] ^= x1.limbs[i];
247 b1.limbs[i] ^= x1.limbs[i];
248 }
249 }
250
251 fn _carry128(r: *[5]u128) Fe {
252 var rs: [5]u64 = undefined;
253 comptime var i = 0;
254 inline while (i < 4) : (i += 1) {
255 rs[i] = @as(u64, @truncate(r[i])) & MASK51;
256 r[i + 1] += @as(u64, @intCast(r[i] >> 51));
257 }
258 rs[4] = @as(u64, @truncate(r[4])) & MASK51;
259 var carry = @as(u64, @intCast(r[4] >> 51));
260 rs[0] += 19 * carry;
261 carry = rs[0] >> 51;
262 rs[0] &= MASK51;
263 rs[1] += carry;
264 carry = rs[1] >> 51;
265 rs[1] &= MASK51;
266 rs[2] += carry;
267
268 return .{ .limbs = rs };
269 }
270
271 /// Multiply two field elements
272 pub fn mul(a: Fe, b: Fe) callconv(bloaty_inline) Fe {
273 var ax: [5]u128 = undefined;
274 var bx: [5]u128 = undefined;
275 var a19: [5]u128 = undefined;
276 var r: [5]u128 = undefined;
277 comptime var i = 0;
278 inline while (i < 5) : (i += 1) {
279 ax[i] = @as(u128, @intCast(a.limbs[i]));
280 bx[i] = @as(u128, @intCast(b.limbs[i]));
281 }
282 i = 1;
283 inline while (i < 5) : (i += 1) {
284 a19[i] = 19 * ax[i];
285 }
286 r[0] = ax[0] * bx[0] + a19[1] * bx[4] + a19[2] * bx[3] + a19[3] * bx[2] + a19[4] * bx[1];
287 r[1] = ax[0] * bx[1] + ax[1] * bx[0] + a19[2] * bx[4] + a19[3] * bx[3] + a19[4] * bx[2];
288 r[2] = ax[0] * bx[2] + ax[1] * bx[1] + ax[2] * bx[0] + a19[3] * bx[4] + a19[4] * bx[3];
289 r[3] = ax[0] * bx[3] + ax[1] * bx[2] + ax[2] * bx[1] + ax[3] * bx[0] + a19[4] * bx[4];
290 r[4] = ax[0] * bx[4] + ax[1] * bx[3] + ax[2] * bx[2] + ax[3] * bx[1] + ax[4] * bx[0];
291
292 return _carry128(&r);
293 }
294
295 fn _sq(a: Fe, comptime double: bool) Fe {
296 var ax: [5]u128 = undefined;
297 var r: [5]u128 = undefined;
298 comptime var i = 0;
299 inline while (i < 5) : (i += 1) {
300 ax[i] = @as(u128, @intCast(a.limbs[i]));
301 }
302 const a0_2 = 2 * ax[0];
303 const a1_2 = 2 * ax[1];
304 const a1_38 = 38 * ax[1];
305 const a2_38 = 38 * ax[2];
306 const a3_38 = 38 * ax[3];
307 const a3_19 = 19 * ax[3];
308 const a4_19 = 19 * ax[4];
309 r[0] = ax[0] * ax[0] + a1_38 * ax[4] + a2_38 * ax[3];
310 r[1] = a0_2 * ax[1] + a2_38 * ax[4] + a3_19 * ax[3];
311 r[2] = a0_2 * ax[2] + ax[1] * ax[1] + a3_38 * ax[4];
312 r[3] = a0_2 * ax[3] + a1_2 * ax[2] + a4_19 * ax[4];
313 r[4] = a0_2 * ax[4] + a1_2 * ax[3] + ax[2] * ax[2];
314 if (double) {
315 i = 0;
316 inline while (i < 5) : (i += 1) {
317 r[i] *= 2;
318 }
319 }
320 return _carry128(&r);
321 }
322
323 /// Square a field element
324 pub fn sq(a: Fe) Fe {
325 return _sq(a, false);
326 }
327
328 /// Square and double a field element
329 pub fn sq2(a: Fe) Fe {
330 return _sq(a, true);
331 }
332
333 /// Multiply a field element with a small (32-bit) integer
334 pub fn mul32(a: Fe, comptime n: u32) Fe {
335 const sn = @as(u128, @intCast(n));
336 var fe: Fe = undefined;
337 var x: u128 = 0;
338 comptime var i = 0;
339 inline while (i < 5) : (i += 1) {
340 x = a.limbs[i] * sn + (x >> 51);
341 fe.limbs[i] = @as(u64, @truncate(x)) & MASK51;
342 }
343 fe.limbs[0] += @as(u64, @intCast(x >> 51)) * 19;
344
345 return fe;
346 }
347
348 /// Square a field element `n` times
349 fn sqn(a: Fe, n: usize) Fe {
350 var i: usize = 0;
351 var fe = a;
352 while (i < n) : (i += 1) {
353 fe = fe.sq();
354 }
355 return fe;
356 }
357
358 /// Return the inverse of a field element, or 0 if a=0.
359 pub fn invert(a: Fe) Fe {
360 var t0 = a.sq();
361 var t1 = t0.sqn(2).mul(a);
362 t0 = t0.mul(t1);
363 t1 = t1.mul(t0.sq());
364 t1 = t1.mul(t1.sqn(5));
365 var t2 = t1.sqn(10).mul(t1);
366 t2 = t2.mul(t2.sqn(20)).sqn(10);
367 t1 = t1.mul(t2);
368 t2 = t1.sqn(50).mul(t1);
369 return t1.mul(t2.mul(t2.sqn(100)).sqn(50)).sqn(5).mul(t0);
370 }
371
372 /// Return a^((p-5)/8) = a^(2^252-3)
373 /// Used to compute square roots since we have p=5 (mod 8); see Cohen and Frey.
374 pub fn pow2523(a: Fe) Fe {
375 var t0 = a.mul(a.sq());
376 var t1 = t0.mul(t0.sqn(2)).sq().mul(a);
377 t0 = t1.sqn(5).mul(t1);
378 var t2 = t0.sqn(5).mul(t1);
379 t1 = t2.sqn(15).mul(t2);
380 t2 = t1.sqn(30).mul(t1);
381 t1 = t2.sqn(60).mul(t2);
382 return t1.sqn(120).mul(t1).sqn(10).mul(t0).sqn(2).mul(a);
383 }
384
385 /// Return the absolute value of a field element
386 pub fn abs(a: Fe) Fe {
387 var r = a;
388 r.cMov(a.neg(), @intFromBool(a.isNegative()));
389 return r;
390 }
391
392 /// Return true if the field element is a square
393 pub fn isSquare(a: Fe) bool {
394 // Compute the Jacobi symbol x^((p-1)/2)
395 const _11 = a.mul(a.sq());
396 const _1111 = _11.mul(_11.sq().sq());
397 const _11111111 = _1111.mul(_1111.sq().sq().sq().sq());
398 const u = _11111111.sqn(2).mul(_11);
399 const t = u.sqn(10).mul(u).sqn(10).mul(u);
400 const t2 = t.sqn(30).mul(t);
401 const t3 = t2.sqn(60).mul(t2);
402 const t4 = t3.sqn(120).mul(t3).sqn(10).mul(u).sqn(3).mul(_11).sq();
403 return @as(bool, @bitCast(@as(u1, @truncate(~(t4.toBytes()[1] & 1)))));
404 }
405
406 fn uncheckedSqrt(x2: Fe) Fe {
407 var e = x2.pow2523();
408 const p_root = e.mul(x2); // positive root
409 const m_root = p_root.mul(Fe.sqrtm1); // negative root
410 const m_root2 = m_root.sq();
411 e = x2.sub(m_root2);
412 var x = p_root;
413 x.cMov(m_root, @intFromBool(e.isZero()));
414 return x;
415 }
416
417 /// Compute the square root of `x2`, returning `error.NotSquare` if `x2` was not a square
418 pub fn sqrt(x2: Fe) NotSquareError!Fe {
419 const x2_copy = x2;
420 const x = x2.uncheckedSqrt();
421 const check = x.sq().sub(x2_copy);
422 if (check.isZero()) {
423 return x;
424 }
425 return error.NotSquare;
426 }
427};