1const std = @import("std");
2const crypto = std.crypto;
3const debug = std.debug;
4const fmt = std.fmt;
5const mem = std.mem;
6
7const EncodingError = crypto.errors.EncodingError;
8const IdentityElementError = crypto.errors.IdentityElementError;
9const NonCanonicalError = crypto.errors.NonCanonicalError;
10const NotSquareError = crypto.errors.NotSquareError;
11const WeakPublicKeyError = crypto.errors.WeakPublicKeyError;
12const UnexpectedSubgroupError = crypto.errors.UnexpectedSubgroupError;
13
14/// Group operations over Edwards25519.
15pub const Edwards25519 = struct {
16 /// The underlying prime field.
17 pub const Fe = @import("field.zig").Fe;
18 /// Field arithmetic mod the order of the main subgroup.
19 pub const scalar = @import("scalar.zig");
20 /// Length in bytes of a compressed representation of a point.
21 pub const encoded_length: usize = 32;
22
23 x: Fe,
24 y: Fe,
25 z: Fe,
26 t: Fe,
27
28 is_base: bool = false,
29
30 /// Decode an Edwards25519 point from its compressed (Y+sign) coordinates.
31 pub fn fromBytes(s: [encoded_length]u8) EncodingError!Edwards25519 {
32 const z = Fe.one;
33 const y = Fe.fromBytes(s);
34 var u = y.sq();
35 var v = u.mul(Fe.edwards25519d);
36 u = u.sub(z);
37 v = v.add(z);
38 var x = u.mul(v).pow2523().mul(u);
39 const vxx = x.sq().mul(v);
40 const has_m_root = vxx.sub(u).isZero();
41 const has_p_root = vxx.add(u).isZero();
42 if ((@intFromBool(has_m_root) | @intFromBool(has_p_root)) == 0) { // best-effort to avoid two conditional branches
43 return error.InvalidEncoding;
44 }
45 x.cMov(x.mul(Fe.sqrtm1), 1 - @intFromBool(has_m_root));
46 x.cMov(x.neg(), @intFromBool(x.isNegative()) ^ (s[31] >> 7));
47 const t = x.mul(y);
48 return Edwards25519{ .x = x, .y = y, .z = z, .t = t };
49 }
50
51 /// Encode an Edwards25519 point.
52 pub fn toBytes(p: Edwards25519) [encoded_length]u8 {
53 const zi = p.z.invert();
54 var s = p.y.mul(zi).toBytes();
55 s[31] ^= @as(u8, @intFromBool(p.x.mul(zi).isNegative())) << 7;
56 return s;
57 }
58
59 /// Check that the encoding of a point is canonical.
60 pub fn rejectNonCanonical(s: [32]u8) NonCanonicalError!void {
61 return Fe.rejectNonCanonical(s, true);
62 }
63
64 /// The edwards25519 base point.
65 pub const basePoint = Edwards25519{
66 .x = Fe{ .limbs = .{ 1738742601995546, 1146398526822698, 2070867633025821, 562264141797630, 587772402128613 } },
67 .y = Fe{ .limbs = .{ 1801439850948184, 1351079888211148, 450359962737049, 900719925474099, 1801439850948198 } },
68 .z = Fe.one,
69 .t = Fe{ .limbs = .{ 1841354044333475, 16398895984059, 755974180946558, 900171276175154, 1821297809914039 } },
70 .is_base = true,
71 };
72
73 pub const identityElement = Edwards25519{ .x = Fe.zero, .y = Fe.one, .z = Fe.one, .t = Fe.zero };
74
75 /// Reject the neutral element.
76 pub fn rejectIdentity(p: Edwards25519) IdentityElementError!void {
77 if (p.x.isZero()) {
78 return error.IdentityElement;
79 }
80 }
81
82 /// Reject a point if it is not in the prime order subgroup generated by the standard base point.
83 ///
84 /// If the point is not in the main subgroup:
85 ///
86 /// - `WeakPublicKeyError` is returned if the point belongs to a low-order subgroup.
87 /// - `UnexpectedSubgroupError` is returned otherwise.
88 pub fn rejectUnexpectedSubgroup(p: Edwards25519) (WeakPublicKeyError || UnexpectedSubgroupError)!void {
89 try p.rejectLowOrder();
90
91 // Multiply p by the order of subgroup - This is a prime order group, so the result should be the neutral element.
92 const _10 = p.dbl();
93 const _11 = p.add(_10);
94 const _100 = p.add(_11);
95 const _110 = _10.add(_100);
96 const _1000 = _10.add(_110);
97 const _1011 = _11.add(_1000);
98 const _10000 = _1000.dbl();
99 const _100000 = _10000.dbl();
100 const _100110 = _110.add(_100000);
101 const _1000000 = _100000.dbl();
102 const _1010000 = _10000.add(_1000000);
103 const _1010011 = _11.add(_1010000);
104 const _1100011 = _10000.add(_1010011);
105 const _1100111 = _100.add(_1100011);
106 const _1101011 = _100.add(_1100111);
107 const _10010011 = _1000000.add(_1010011);
108 const _10010111 = _100.add(_10010011);
109 const _10111101 = _100110.add(_10010111);
110 const _11010011 = _1000000.add(_10010011);
111 const _11100111 = _1010000.add(_10010111);
112 const _11101101 = _110.add(_11100111);
113 const _11110101 = _1000.add(_11101101);
114 const q = ((_11110101.add(((((_1101011.add(((((_10.add(((_1011.add(_11110101)).shift(126)
115 .add(_1010011)).shift(9).add(_11110101))).shift(7).add(_1100111)).shift(9).add(_11110101).shift(11)
116 .add(_10111101)).shift(8).add(_11100111)).shift(9))).shift(6).add(_1011)).shift(14).add(_10010011).shift(10)
117 .add(_1100011)).shift(9).add(_10010111)).shift(10))).shift(8).add(_11010011)).shift(8).add(_11101101);
118 if (q.x.isZero() and q.y.equivalent(q.z)) return;
119 return error.UnexpectedSubgroup;
120 }
121
122 /// Multiply a point by the cofactor
123 pub fn clearCofactor(p: Edwards25519) Edwards25519 {
124 return p.dbl().dbl().dbl();
125 }
126
127 /// Check that the point does not generate a low-order group.
128 /// Return a `WeakPublicKey` error if it does.
129 pub fn rejectLowOrder(p: Edwards25519) WeakPublicKeyError!void {
130 const y_sqrtm1 = Fe.sqrtm1.mul(p.y);
131 if (p.x.isZero() or p.y.isZero() or p.z.isZero() or
132 y_sqrtm1.sub(p.x).isZero() or y_sqrtm1.add(p.x).isZero())
133 {
134 return error.WeakPublicKey;
135 }
136 }
137
138 /// Flip the sign of the X coordinate.
139 pub fn neg(p: Edwards25519) Edwards25519 {
140 return .{ .x = p.x.neg(), .y = p.y, .z = p.z, .t = p.t.neg() };
141 }
142
143 /// Double an Edwards25519 point.
144 pub fn dbl(p: Edwards25519) Edwards25519 {
145 const t0 = p.x.add(p.y).sq();
146 var x = p.x.sq();
147 var z = p.y.sq();
148 const y = z.add(x);
149 z = z.sub(x);
150 x = t0.sub(y);
151 const t = p.z.sq2().sub(z);
152 return .{
153 .x = x.mul(t),
154 .y = y.mul(z),
155 .z = z.mul(t),
156 .t = x.mul(y),
157 };
158 }
159
160 /// Add two Edwards25519 points.
161 pub fn add(p: Edwards25519, q: Edwards25519) Edwards25519 {
162 const a = p.y.sub(p.x).mul(q.y.sub(q.x));
163 const b = p.x.add(p.y).mul(q.x.add(q.y));
164 const c = p.t.mul(q.t).mul(Fe.edwards25519d2);
165 var d = p.z.mul(q.z);
166 d = d.add(d);
167 const x = b.sub(a);
168 const y = b.add(a);
169 const z = d.add(c);
170 const t = d.sub(c);
171 return .{
172 .x = x.mul(t),
173 .y = y.mul(z),
174 .z = z.mul(t),
175 .t = x.mul(y),
176 };
177 }
178
179 /// Subtract two Edwards25519 points.
180 pub fn sub(p: Edwards25519, q: Edwards25519) Edwards25519 {
181 return p.add(q.neg());
182 }
183
184 /// Double a point `n` times.
185 fn shift(p: Edwards25519, n: comptime_int) Edwards25519 {
186 var q = p;
187 for (0..n) |_| q = q.dbl();
188 return q;
189 }
190
191 fn cMov(p: *Edwards25519, a: Edwards25519, c: u64) void {
192 p.x.cMov(a.x, c);
193 p.y.cMov(a.y, c);
194 p.z.cMov(a.z, c);
195 p.t.cMov(a.t, c);
196 }
197
198 fn pcSelect(comptime n: usize, pc: *const [n]Edwards25519, b: u8) Edwards25519 {
199 var t = Edwards25519.identityElement;
200 comptime var i: u8 = 1;
201 inline while (i < pc.len) : (i += 1) {
202 t.cMov(pc[i], ((@as(usize, b ^ i) -% 1) >> 8) & 1);
203 }
204 return t;
205 }
206
207 fn slide(s: [32]u8) [2 * 32]i8 {
208 const reduced = if ((s[s.len - 1] & 0x80) == 0) s else scalar.reduce(s);
209 var e: [2 * 32]i8 = undefined;
210 for (reduced, 0..) |x, i| {
211 e[i * 2 + 0] = @as(i8, @as(u4, @truncate(x)));
212 e[i * 2 + 1] = @as(i8, @as(u4, @truncate(x >> 4)));
213 }
214 // Now, e[0..63] is between 0 and 15, e[63] is between 0 and 7
215 var carry: i8 = 0;
216 for (e[0..63]) |*x| {
217 x.* += carry;
218 carry = (x.* + 8) >> 4;
219 x.* -= carry * 16;
220 }
221 e[63] += carry;
222 // Now, e[*] is between -8 and 8, including e[63]
223 return e;
224 }
225
226 // Scalar multiplication with a 4-bit window and the first 8 multiples.
227 // This requires the scalar to be converted to non-adjacent form.
228 // Based on real-world benchmarks, we only use this for multi-scalar multiplication.
229 // NAF could be useful to half the size of precomputation tables, but we intentionally
230 // avoid these to keep the standard library lightweight.
231 fn pcMul(pc: *const [9]Edwards25519, s: [32]u8, comptime vartime: bool) IdentityElementError!Edwards25519 {
232 std.debug.assert(vartime);
233 const e = slide(s);
234 var q = Edwards25519.identityElement;
235 var pos: usize = 2 * 32 - 1;
236 while (true) : (pos -= 1) {
237 const slot = e[pos];
238 if (slot > 0) {
239 q = q.add(pc[@as(usize, @intCast(slot))]);
240 } else if (slot < 0) {
241 q = q.sub(pc[@as(usize, @intCast(-slot))]);
242 }
243 if (pos == 0) break;
244 q = q.dbl().dbl().dbl().dbl();
245 }
246 try q.rejectIdentity();
247 return q;
248 }
249
250 // Scalar multiplication with a 4-bit window and the first 15 multiples.
251 fn pcMul16(pc: *const [16]Edwards25519, s: [32]u8, comptime vartime: bool) IdentityElementError!Edwards25519 {
252 var q = Edwards25519.identityElement;
253 var pos: usize = 252;
254 while (true) : (pos -= 4) {
255 const slot: u4 = @truncate((s[pos >> 3] >> @as(u3, @truncate(pos))));
256 if (vartime) {
257 if (slot != 0) {
258 q = q.add(pc[slot]);
259 }
260 } else {
261 q = q.add(pcSelect(16, pc, slot));
262 }
263 if (pos == 0) break;
264 q = q.dbl().dbl().dbl().dbl();
265 }
266 try q.rejectIdentity();
267 return q;
268 }
269
270 fn precompute(p: Edwards25519, comptime count: usize) [1 + count]Edwards25519 {
271 var pc: [1 + count]Edwards25519 = undefined;
272 pc[0] = Edwards25519.identityElement;
273 pc[1] = p;
274 var i: usize = 2;
275 while (i <= count) : (i += 1) {
276 pc[i] = if (i % 2 == 0) pc[i / 2].dbl() else pc[i - 1].add(p);
277 }
278 return pc;
279 }
280
281 const basePointPc = pc: {
282 @setEvalBranchQuota(10000);
283 break :pc precompute(Edwards25519.basePoint, 15);
284 };
285
286 /// Multiply an Edwards25519 point by a scalar without clamping it.
287 /// Return error.WeakPublicKey if the base generates a small-order group,
288 /// and error.IdentityElement if the result is the identity element.
289 pub fn mul(p: Edwards25519, s: [32]u8) (IdentityElementError || WeakPublicKeyError)!Edwards25519 {
290 const pc = if (p.is_base) basePointPc else pc: {
291 const xpc = precompute(p, 15);
292 xpc[4].rejectIdentity() catch return error.WeakPublicKey;
293 break :pc xpc;
294 };
295 return pcMul16(&pc, s, false);
296 }
297
298 /// Multiply an Edwards25519 point by a *PUBLIC* scalar *IN VARIABLE TIME*
299 /// This can be used for signature verification.
300 pub fn mulPublic(p: Edwards25519, s: [32]u8) (IdentityElementError || WeakPublicKeyError)!Edwards25519 {
301 if (p.is_base) {
302 return pcMul16(&basePointPc, s, true);
303 } else {
304 const pc = precompute(p, 8);
305 pc[4].rejectIdentity() catch return error.WeakPublicKey;
306 return pcMul(&pc, s, true);
307 }
308 }
309
310 /// Double-base multiplication of public parameters - Compute (p1*s1)+(p2*s2) *IN VARIABLE TIME*
311 /// This can be used for signature verification.
312 pub fn mulDoubleBasePublic(p1: Edwards25519, s1: [32]u8, p2: Edwards25519, s2: [32]u8) WeakPublicKeyError!Edwards25519 {
313 var pc1_array: [9]Edwards25519 = undefined;
314 const pc1 = if (p1.is_base) basePointPc[0..9] else pc: {
315 pc1_array = precompute(p1, 8);
316 pc1_array[4].rejectIdentity() catch return error.WeakPublicKey;
317 break :pc &pc1_array;
318 };
319 var pc2_array: [9]Edwards25519 = undefined;
320 const pc2 = if (p2.is_base) basePointPc[0..9] else pc: {
321 pc2_array = precompute(p2, 8);
322 pc2_array[4].rejectIdentity() catch return error.WeakPublicKey;
323 break :pc &pc2_array;
324 };
325 const e1 = slide(s1);
326 const e2 = slide(s2);
327 var q = Edwards25519.identityElement;
328 var pos: usize = 2 * 32 - 1;
329 while (true) : (pos -= 1) {
330 const slot1 = e1[pos];
331 if (slot1 > 0) {
332 q = q.add(pc1[@as(usize, @intCast(slot1))]);
333 } else if (slot1 < 0) {
334 q = q.sub(pc1[@as(usize, @intCast(-slot1))]);
335 }
336 const slot2 = e2[pos];
337 if (slot2 > 0) {
338 q = q.add(pc2[@as(usize, @intCast(slot2))]);
339 } else if (slot2 < 0) {
340 q = q.sub(pc2[@as(usize, @intCast(-slot2))]);
341 }
342 if (pos == 0) break;
343 q = q.dbl().dbl().dbl().dbl();
344 }
345 return q;
346 }
347
348 /// Multiscalar multiplication *IN VARIABLE TIME* for public data
349 /// Computes ps0*ss0 + ps1*ss1 + ps2*ss2... faster than doing many of these operations individually
350 pub fn mulMulti(comptime count: usize, ps: [count]Edwards25519, ss: [count][32]u8) (IdentityElementError || WeakPublicKeyError)!Edwards25519 {
351 var pcs: [count][9]Edwards25519 = undefined;
352
353 var bpc: [9]Edwards25519 = undefined;
354 @memcpy(&bpc, basePointPc[0..bpc.len]);
355
356 for (ps, 0..) |p, i| {
357 if (p.is_base) {
358 pcs[i] = bpc;
359 } else {
360 pcs[i] = precompute(p, 8);
361 pcs[i][4].rejectIdentity() catch return error.WeakPublicKey;
362 }
363 }
364 var es: [count][2 * 32]i8 = undefined;
365 for (ss, 0..) |s, i| {
366 es[i] = slide(s);
367 }
368 var q = Edwards25519.identityElement;
369 var pos: usize = 2 * 32 - 1;
370 while (true) : (pos -= 1) {
371 for (es, 0..) |e, i| {
372 const slot = e[pos];
373 if (slot > 0) {
374 q = q.add(pcs[i][@as(usize, @intCast(slot))]);
375 } else if (slot < 0) {
376 q = q.sub(pcs[i][@as(usize, @intCast(-slot))]);
377 }
378 }
379 if (pos == 0) break;
380 q = q.dbl().dbl().dbl().dbl();
381 }
382 try q.rejectIdentity();
383 return q;
384 }
385
386 /// Multiply an Edwards25519 point by a scalar after "clamping" it.
387 /// Clamping forces the scalar to be a multiple of the cofactor in
388 /// order to prevent small subgroups attacks.
389 /// This is strongly recommended for DH operations.
390 /// Return error.WeakPublicKey if the resulting point is
391 /// the identity element.
392 pub fn clampedMul(p: Edwards25519, s: [32]u8) (IdentityElementError || WeakPublicKeyError)!Edwards25519 {
393 var t: [32]u8 = s;
394 scalar.clamp(&t);
395 return mul(p, t);
396 }
397
398 // montgomery -- recover y = sqrt(x^3 + A*x^2 + x)
399 fn xmontToYmont(x: Fe) NotSquareError!Fe {
400 var x2 = x.sq();
401 const x3 = x.mul(x2);
402 x2 = x2.mul32(Fe.edwards25519a_32);
403 return x.add(x2).add(x3).sqrt();
404 }
405
406 // montgomery affine coordinates to edwards extended coordinates
407 fn montToEd(x: Fe, y: Fe) Edwards25519 {
408 const x_plus_one = x.add(Fe.one);
409 const x_minus_one = x.sub(Fe.one);
410 const x_plus_one_y_inv = x_plus_one.mul(y).invert(); // 1/((x+1)*y)
411
412 // xed = sqrt(-A-2)*x/y
413 const xed = x.mul(Fe.edwards25519sqrtam2).mul(x_plus_one_y_inv).mul(x_plus_one);
414
415 // yed = (x-1)/(x+1) or 1 if the denominator is 0
416 var yed = x_plus_one_y_inv.mul(y).mul(x_minus_one);
417 yed.cMov(Fe.one, @intFromBool(x_plus_one_y_inv.isZero()));
418
419 return Edwards25519{
420 .x = xed,
421 .y = yed,
422 .z = Fe.one,
423 .t = xed.mul(yed),
424 };
425 }
426
427 /// Elligator2 map - Returns Montgomery affine coordinates
428 pub fn elligator2(r: Fe) struct { x: Fe, y: Fe, not_square: bool } {
429 const rr2 = r.sq2().add(Fe.one).invert();
430 var x = rr2.mul32(Fe.edwards25519a_32).neg(); // x=x1
431 var x2 = x.sq();
432 const x3 = x2.mul(x);
433 x2 = x2.mul32(Fe.edwards25519a_32); // x2 = A*x1^2
434 const gx1 = x3.add(x).add(x2); // gx1 = x1^3 + A*x1^2 + x1
435 const not_square = !gx1.isSquare();
436
437 // gx1 not a square => x = -x1-A
438 x.cMov(x.neg(), @intFromBool(not_square));
439 x2 = Fe.zero;
440 x2.cMov(Fe.edwards25519a, @intFromBool(not_square));
441 x = x.sub(x2);
442
443 // We have y = sqrt(gx1) or sqrt(gx2) with gx2 = gx1*(A+x1)/(-x1)
444 // but it is about as fast to just recompute y from the curve equation.
445 const y = xmontToYmont(x) catch unreachable;
446 return .{ .x = x, .y = y, .not_square = not_square };
447 }
448
449 /// Map a 64-bit hash into an Edwards25519 point
450 pub fn fromHash(h: [64]u8) Edwards25519 {
451 const fe_f = Fe.fromBytes64(h);
452 var elr = elligator2(fe_f);
453
454 const y_sign = !elr.not_square;
455 const y_neg = elr.y.neg();
456 elr.y.cMov(y_neg, @intFromBool(elr.y.isNegative()) ^ @intFromBool(y_sign));
457 return montToEd(elr.x, elr.y).clearCofactor();
458 }
459
460 fn stringToPoints(comptime n: usize, ctx: []const u8, s: []const u8) [n]Edwards25519 {
461 debug.assert(n <= 2);
462 const H = crypto.hash.sha2.Sha512;
463 const h_l: usize = 48;
464 var xctx = ctx;
465 var hctx: [H.digest_length]u8 = undefined;
466 if (ctx.len > 0xff) {
467 var st = H.init(.{});
468 st.update("H2C-OVERSIZE-DST-");
469 st.update(ctx);
470 st.final(&hctx);
471 xctx = hctx[0..];
472 }
473 const empty_block: [H.block_length]u8 = @splat(0);
474 var t = [3]u8{ 0, n * h_l, 0 };
475 var xctx_len_u8 = [1]u8{@as(u8, @intCast(xctx.len))};
476 var st = H.init(.{});
477 st.update(empty_block[0..]);
478 st.update(s);
479 st.update(t[0..]);
480 st.update(xctx);
481 st.update(xctx_len_u8[0..]);
482 var u_0: [H.digest_length]u8 = undefined;
483 st.final(&u_0);
484 var u: [n * H.digest_length]u8 = undefined;
485 var i: usize = 0;
486 while (i < n * H.digest_length) : (i += H.digest_length) {
487 u[i..][0..H.digest_length].* = u_0;
488 var j: usize = 0;
489 while (i > 0 and j < H.digest_length) : (j += 1) {
490 u[i + j] ^= u[i + j - H.digest_length];
491 }
492 t[2] += 1;
493 st = H.init(.{});
494 st.update(u[i..][0..H.digest_length]);
495 st.update(t[2..3]);
496 st.update(xctx);
497 st.update(xctx_len_u8[0..]);
498 st.final(u[i..][0..H.digest_length]);
499 }
500 var px: [n]Edwards25519 = undefined;
501 i = 0;
502 while (i < n) : (i += 1) {
503 @memset(u_0[0 .. H.digest_length - h_l], 0);
504 u_0[H.digest_length - h_l ..][0..h_l].* = u[i * h_l ..][0..h_l].*;
505 px[i] = fromHash(u_0);
506 }
507 return px;
508 }
509
510 /// Hash a context `ctx` and a string `s` into an Edwards25519 point
511 ///
512 /// This function implements the edwards25519_XMD:SHA-512_ELL2_RO_ and edwards25519_XMD:SHA-512_ELL2_NU_
513 /// methods from the "Hashing to Elliptic Curves" standard document.
514 ///
515 /// Although not strictly required by the standard, it is recommended to avoid NUL characters in
516 /// the context in order to be compatible with other implementations.
517 pub fn fromString(comptime random_oracle: bool, ctx: []const u8, s: []const u8) Edwards25519 {
518 if (random_oracle) {
519 const px = stringToPoints(2, ctx, s);
520 return px[0].add(px[1]);
521 } else {
522 return stringToPoints(1, ctx, s)[0];
523 }
524 }
525
526 /// Map a 32 bit uniform bit string into an edwards25519 point
527 pub fn fromUniform(r: [32]u8) Edwards25519 {
528 var s = r;
529 const x_sign = s[31] >> 7;
530 s[31] &= 0x7f;
531 const elr = elligator2(Fe.fromBytes(s));
532 var p = montToEd(elr.x, elr.y);
533 const p_neg = p.neg();
534 p.cMov(p_neg, @intFromBool(p.x.isNegative()) ^ x_sign);
535 return p.clearCofactor();
536 }
537};
538
539const htest = @import("../test.zig");
540
541test "packing/unpacking" {
542 const s = [1]u8{170} ++ @as([31]u8, @splat(0));
543 var b = Edwards25519.basePoint;
544 const pk = try b.mul(s);
545 var buf: [128]u8 = undefined;
546 try std.testing.expectEqualStrings(try std.mem.print(&buf, "{X}", .{&pk.toBytes()}), "074BC7E0FCBD587FDBC0969444245FADC562809C8F6E97E949AF62484B5B81A6");
547
548 const small_order_ss: [7][32]u8 = .{
549 .{
550 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // 0 (order 4)
551 },
552 .{
553 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // 1 (order 1)
554 },
555 .{
556 0x26, 0xe8, 0x95, 0x8f, 0xc2, 0xb2, 0x27, 0xb0, 0x45, 0xc3, 0xf4, 0x89, 0xf2, 0xef, 0x98, 0xf0, 0xd5, 0xdf, 0xac, 0x05, 0xd3, 0xc6, 0x33, 0x39, 0xb1, 0x38, 0x02, 0x88, 0x6d, 0x53, 0xfc, 0x05, // 270738550114484064931822528722565878893680426757531351946374360975030340202(order 8)
557 },
558 .{
559 0xc7, 0x17, 0x6a, 0x70, 0x3d, 0x4d, 0xd8, 0x4f, 0xba, 0x3c, 0x0b, 0x76, 0x0d, 0x10, 0x67, 0x0f, 0x2a, 0x20, 0x53, 0xfa, 0x2c, 0x39, 0xcc, 0xc6, 0x4e, 0xc7, 0xfd, 0x77, 0x92, 0xac, 0x03, 0x7a, // 55188659117513257062467267217118295137698188065244968500265048394206261417927 (order 8)
560 },
561 .{
562 0xec, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f, // p-1 (order 2)
563 },
564 .{
565 0xed, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f, // p (=0, order 4)
566 },
567 .{
568 0xee, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f, // p+1 (=1, order 1)
569 },
570 };
571 for (small_order_ss) |small_order_s| {
572 const small_p = try Edwards25519.fromBytes(small_order_s);
573 try std.testing.expectError(error.WeakPublicKey, small_p.mul(s));
574 }
575}
576
577test "point addition/subtraction" {
578 const io = std.testing.io;
579 var s1: [32]u8 = undefined;
580 var s2: [32]u8 = undefined;
581 io.random(&s1);
582 io.random(&s2);
583 const p = try Edwards25519.basePoint.clampedMul(s1);
584 const q = try Edwards25519.basePoint.clampedMul(s2);
585 const r = p.add(q).add(q).sub(q).sub(q);
586 try r.rejectIdentity();
587 try std.testing.expectError(error.IdentityElement, r.sub(p).rejectIdentity());
588 try std.testing.expectError(error.IdentityElement, p.sub(p).rejectIdentity());
589 try std.testing.expectError(error.IdentityElement, p.sub(q).add(q).sub(p).rejectIdentity());
590}
591
592test "uniform-to-point" {
593 var r = [32]u8{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31 };
594 var p = Edwards25519.fromUniform(r);
595 try htest.assertEqual("0691eee3cf70a0056df6bfa03120635636581b5c4ea571dfc680f78c7e0b4137", p.toBytes()[0..]);
596
597 r[31] = 0xff;
598 p = Edwards25519.fromUniform(r);
599 try htest.assertEqual("f70718e68ef42d90ca1d936bb2d7e159be6c01d8095d39bd70487c82fe5c973a", p.toBytes()[0..]);
600}
601
602// Test vectors from draft-irtf-cfrg-hash-to-curve-12
603test "hash-to-curve operation" {
604 var p = Edwards25519.fromString(true, "QUUX-V01-CS02-with-edwards25519_XMD:SHA-512_ELL2_RO_", "abc");
605 try htest.assertEqual("31558a26887f23fb8218f143e69d5f0af2e7831130bd5b432ef23883b895839a", p.toBytes()[0..]);
606
607 p = Edwards25519.fromString(false, "QUUX-V01-CS02-with-edwards25519_XMD:SHA-512_ELL2_NU_", "abc");
608 try htest.assertEqual("42fa27c8f5a1ae0aa38bb59d5938e5145622ba5dedd11d11736fa2f9502d7367", p.toBytes()[0..]);
609}
610
611test "implicit reduction of invalid scalars" {
612 const s = @as([31]u8, @splat(0)) ++ [1]u8{255};
613 const p1 = try Edwards25519.basePoint.mulPublic(s);
614 const p2 = try Edwards25519.basePoint.mul(s);
615 const p3 = try p1.mulPublic(s);
616 const p4 = try p1.mul(s);
617
618 try std.testing.expectEqualSlices(u8, p1.toBytes()[0..], p2.toBytes()[0..]);
619 try std.testing.expectEqualSlices(u8, p3.toBytes()[0..], p4.toBytes()[0..]);
620
621 try htest.assertEqual("339f189ecc5fbebe9895345c72dc07bda6e615f8a40e768441b6f529cd6c671a", p1.toBytes()[0..]);
622 try htest.assertEqual("a501e4c595a3686d8bee7058c7e6af7fd237f945c47546910e37e0e79b1bafb0", p3.toBytes()[0..]);
623}
624
625test "subgroup check" {
626 const io = std.testing.io;
627 for (0..100) |_| {
628 var p = Edwards25519.basePoint;
629 const s = Edwards25519.scalar.random(io);
630 p = try p.mulPublic(s);
631 try p.rejectUnexpectedSubgroup();
632 }
633 var bogus: [Edwards25519.encoded_length]u8 = undefined;
634 _ = try std.fmt.hexToBytes(&bogus, "4dc95e3c28d78c48a60531525e6327e259b7ba0d2f5c81b694052c766a14b625");
635 const p = try Edwards25519.fromBytes(bogus);
636 try std.testing.expectError(error.UnexpectedSubgroup, p.rejectUnexpectedSubgroup());
637
638 var torsion2L: [Edwards25519.encoded_length]u8 = undefined;
639 _ = try std.fmt.hexToBytes(&torsion2L, "9599999999999999999999999999999999999999999999999999999999999999");
640 const p2L = try Edwards25519.fromBytes(torsion2L);
641 try std.testing.expectError(error.UnexpectedSubgroup, p2L.rejectUnexpectedSubgroup());
642}