master
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 q.rejectIdentity() catch 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 zi = p.z.invert();
131 const x = p.x.mul(zi);
132 const y = p.y.mul(zi);
133 const x_neg = x.neg();
134 const iy = Fe.sqrtm1.mul(y);
135 if (x.isZero() or y.isZero() or iy.equivalent(x) or iy.equivalent(x_neg)) {
136 return error.WeakPublicKey;
137 }
138 }
139
140 /// Flip the sign of the X coordinate.
141 pub fn neg(p: Edwards25519) Edwards25519 {
142 return .{ .x = p.x.neg(), .y = p.y, .z = p.z, .t = p.t.neg() };
143 }
144
145 /// Double an Edwards25519 point.
146 pub fn dbl(p: Edwards25519) Edwards25519 {
147 const t0 = p.x.add(p.y).sq();
148 var x = p.x.sq();
149 var z = p.y.sq();
150 const y = z.add(x);
151 z = z.sub(x);
152 x = t0.sub(y);
153 const t = p.z.sq2().sub(z);
154 return .{
155 .x = x.mul(t),
156 .y = y.mul(z),
157 .z = z.mul(t),
158 .t = x.mul(y),
159 };
160 }
161
162 /// Add two Edwards25519 points.
163 pub fn add(p: Edwards25519, q: Edwards25519) Edwards25519 {
164 const a = p.y.sub(p.x).mul(q.y.sub(q.x));
165 const b = p.x.add(p.y).mul(q.x.add(q.y));
166 const c = p.t.mul(q.t).mul(Fe.edwards25519d2);
167 var d = p.z.mul(q.z);
168 d = d.add(d);
169 const x = b.sub(a);
170 const y = b.add(a);
171 const z = d.add(c);
172 const t = d.sub(c);
173 return .{
174 .x = x.mul(t),
175 .y = y.mul(z),
176 .z = z.mul(t),
177 .t = x.mul(y),
178 };
179 }
180
181 /// Subtract two Edwards25519 points.
182 pub fn sub(p: Edwards25519, q: Edwards25519) Edwards25519 {
183 return p.add(q.neg());
184 }
185
186 /// Double a point `n` times.
187 fn shift(p: Edwards25519, n: comptime_int) Edwards25519 {
188 var q = p;
189 for (0..n) |_| q = q.dbl();
190 return q;
191 }
192
193 fn cMov(p: *Edwards25519, a: Edwards25519, c: u64) void {
194 p.x.cMov(a.x, c);
195 p.y.cMov(a.y, c);
196 p.z.cMov(a.z, c);
197 p.t.cMov(a.t, c);
198 }
199
200 fn pcSelect(comptime n: usize, pc: *const [n]Edwards25519, b: u8) Edwards25519 {
201 var t = Edwards25519.identityElement;
202 comptime var i: u8 = 1;
203 inline while (i < pc.len) : (i += 1) {
204 t.cMov(pc[i], ((@as(usize, b ^ i) -% 1) >> 8) & 1);
205 }
206 return t;
207 }
208
209 fn slide(s: [32]u8) [2 * 32]i8 {
210 const reduced = if ((s[s.len - 1] & 0x80) == 0) s else scalar.reduce(s);
211 var e: [2 * 32]i8 = undefined;
212 for (reduced, 0..) |x, i| {
213 e[i * 2 + 0] = @as(i8, @as(u4, @truncate(x)));
214 e[i * 2 + 1] = @as(i8, @as(u4, @truncate(x >> 4)));
215 }
216 // Now, e[0..63] is between 0 and 15, e[63] is between 0 and 7
217 var carry: i8 = 0;
218 for (e[0..63]) |*x| {
219 x.* += carry;
220 carry = (x.* + 8) >> 4;
221 x.* -= carry * 16;
222 }
223 e[63] += carry;
224 // Now, e[*] is between -8 and 8, including e[63]
225 return e;
226 }
227
228 // Scalar multiplication with a 4-bit window and the first 8 multiples.
229 // This requires the scalar to be converted to non-adjacent form.
230 // Based on real-world benchmarks, we only use this for multi-scalar multiplication.
231 // NAF could be useful to half the size of precomputation tables, but we intentionally
232 // avoid these to keep the standard library lightweight.
233 fn pcMul(pc: *const [9]Edwards25519, s: [32]u8, comptime vartime: bool) IdentityElementError!Edwards25519 {
234 std.debug.assert(vartime);
235 const e = slide(s);
236 var q = Edwards25519.identityElement;
237 var pos: usize = 2 * 32 - 1;
238 while (true) : (pos -= 1) {
239 const slot = e[pos];
240 if (slot > 0) {
241 q = q.add(pc[@as(usize, @intCast(slot))]);
242 } else if (slot < 0) {
243 q = q.sub(pc[@as(usize, @intCast(-slot))]);
244 }
245 if (pos == 0) break;
246 q = q.dbl().dbl().dbl().dbl();
247 }
248 try q.rejectIdentity();
249 return q;
250 }
251
252 // Scalar multiplication with a 4-bit window and the first 15 multiples.
253 fn pcMul16(pc: *const [16]Edwards25519, s: [32]u8, comptime vartime: bool) IdentityElementError!Edwards25519 {
254 var q = Edwards25519.identityElement;
255 var pos: usize = 252;
256 while (true) : (pos -= 4) {
257 const slot: u4 = @truncate((s[pos >> 3] >> @as(u3, @truncate(pos))));
258 if (vartime) {
259 if (slot != 0) {
260 q = q.add(pc[slot]);
261 }
262 } else {
263 q = q.add(pcSelect(16, pc, slot));
264 }
265 if (pos == 0) break;
266 q = q.dbl().dbl().dbl().dbl();
267 }
268 try q.rejectIdentity();
269 return q;
270 }
271
272 fn precompute(p: Edwards25519, comptime count: usize) [1 + count]Edwards25519 {
273 var pc: [1 + count]Edwards25519 = undefined;
274 pc[0] = Edwards25519.identityElement;
275 pc[1] = p;
276 var i: usize = 2;
277 while (i <= count) : (i += 1) {
278 pc[i] = if (i % 2 == 0) pc[i / 2].dbl() else pc[i - 1].add(p);
279 }
280 return pc;
281 }
282
283 const basePointPc = pc: {
284 @setEvalBranchQuota(10000);
285 break :pc precompute(Edwards25519.basePoint, 15);
286 };
287
288 /// Multiply an Edwards25519 point by a scalar without clamping it.
289 /// Return error.WeakPublicKey if the base generates a small-order group,
290 /// and error.IdentityElement if the result is the identity element.
291 pub fn mul(p: Edwards25519, s: [32]u8) (IdentityElementError || WeakPublicKeyError)!Edwards25519 {
292 const pc = if (p.is_base) basePointPc else pc: {
293 const xpc = precompute(p, 15);
294 xpc[4].rejectIdentity() catch return error.WeakPublicKey;
295 break :pc xpc;
296 };
297 return pcMul16(&pc, s, false);
298 }
299
300 /// Multiply an Edwards25519 point by a *PUBLIC* scalar *IN VARIABLE TIME*
301 /// This can be used for signature verification.
302 pub fn mulPublic(p: Edwards25519, s: [32]u8) (IdentityElementError || WeakPublicKeyError)!Edwards25519 {
303 if (p.is_base) {
304 return pcMul16(&basePointPc, s, true);
305 } else {
306 const pc = precompute(p, 8);
307 pc[4].rejectIdentity() catch return error.WeakPublicKey;
308 return pcMul(&pc, s, true);
309 }
310 }
311
312 /// Double-base multiplication of public parameters - Compute (p1*s1)+(p2*s2) *IN VARIABLE TIME*
313 /// This can be used for signature verification.
314 pub fn mulDoubleBasePublic(p1: Edwards25519, s1: [32]u8, p2: Edwards25519, s2: [32]u8) WeakPublicKeyError!Edwards25519 {
315 var pc1_array: [9]Edwards25519 = undefined;
316 const pc1 = if (p1.is_base) basePointPc[0..9] else pc: {
317 pc1_array = precompute(p1, 8);
318 pc1_array[4].rejectIdentity() catch return error.WeakPublicKey;
319 break :pc &pc1_array;
320 };
321 var pc2_array: [9]Edwards25519 = undefined;
322 const pc2 = if (p2.is_base) basePointPc[0..9] else pc: {
323 pc2_array = precompute(p2, 8);
324 pc2_array[4].rejectIdentity() catch return error.WeakPublicKey;
325 break :pc &pc2_array;
326 };
327 const e1 = slide(s1);
328 const e2 = slide(s2);
329 var q = Edwards25519.identityElement;
330 var pos: usize = 2 * 32 - 1;
331 while (true) : (pos -= 1) {
332 const slot1 = e1[pos];
333 if (slot1 > 0) {
334 q = q.add(pc1[@as(usize, @intCast(slot1))]);
335 } else if (slot1 < 0) {
336 q = q.sub(pc1[@as(usize, @intCast(-slot1))]);
337 }
338 const slot2 = e2[pos];
339 if (slot2 > 0) {
340 q = q.add(pc2[@as(usize, @intCast(slot2))]);
341 } else if (slot2 < 0) {
342 q = q.sub(pc2[@as(usize, @intCast(-slot2))]);
343 }
344 if (pos == 0) break;
345 q = q.dbl().dbl().dbl().dbl();
346 }
347 return q;
348 }
349
350 /// Multiscalar multiplication *IN VARIABLE TIME* for public data
351 /// Computes ps0*ss0 + ps1*ss1 + ps2*ss2... faster than doing many of these operations individually
352 pub fn mulMulti(comptime count: usize, ps: [count]Edwards25519, ss: [count][32]u8) (IdentityElementError || WeakPublicKeyError)!Edwards25519 {
353 var pcs: [count][9]Edwards25519 = undefined;
354
355 var bpc: [9]Edwards25519 = undefined;
356 @memcpy(&bpc, basePointPc[0..bpc.len]);
357
358 for (ps, 0..) |p, i| {
359 if (p.is_base) {
360 pcs[i] = bpc;
361 } else {
362 pcs[i] = precompute(p, 8);
363 pcs[i][4].rejectIdentity() catch return error.WeakPublicKey;
364 }
365 }
366 var es: [count][2 * 32]i8 = undefined;
367 for (ss, 0..) |s, i| {
368 es[i] = slide(s);
369 }
370 var q = Edwards25519.identityElement;
371 var pos: usize = 2 * 32 - 1;
372 while (true) : (pos -= 1) {
373 for (es, 0..) |e, i| {
374 const slot = e[pos];
375 if (slot > 0) {
376 q = q.add(pcs[i][@as(usize, @intCast(slot))]);
377 } else if (slot < 0) {
378 q = q.sub(pcs[i][@as(usize, @intCast(-slot))]);
379 }
380 }
381 if (pos == 0) break;
382 q = q.dbl().dbl().dbl().dbl();
383 }
384 try q.rejectIdentity();
385 return q;
386 }
387
388 /// Multiply an Edwards25519 point by a scalar after "clamping" it.
389 /// Clamping forces the scalar to be a multiple of the cofactor in
390 /// order to prevent small subgroups attacks.
391 /// This is strongly recommended for DH operations.
392 /// Return error.WeakPublicKey if the resulting point is
393 /// the identity element.
394 pub fn clampedMul(p: Edwards25519, s: [32]u8) (IdentityElementError || WeakPublicKeyError)!Edwards25519 {
395 var t: [32]u8 = s;
396 scalar.clamp(&t);
397 return mul(p, t);
398 }
399
400 // montgomery -- recover y = sqrt(x^3 + A*x^2 + x)
401 fn xmontToYmont(x: Fe) NotSquareError!Fe {
402 var x2 = x.sq();
403 const x3 = x.mul(x2);
404 x2 = x2.mul32(Fe.edwards25519a_32);
405 return x.add(x2).add(x3).sqrt();
406 }
407
408 // montgomery affine coordinates to edwards extended coordinates
409 fn montToEd(x: Fe, y: Fe) Edwards25519 {
410 const x_plus_one = x.add(Fe.one);
411 const x_minus_one = x.sub(Fe.one);
412 const x_plus_one_y_inv = x_plus_one.mul(y).invert(); // 1/((x+1)*y)
413
414 // xed = sqrt(-A-2)*x/y
415 const xed = x.mul(Fe.edwards25519sqrtam2).mul(x_plus_one_y_inv).mul(x_plus_one);
416
417 // yed = (x-1)/(x+1) or 1 if the denominator is 0
418 var yed = x_plus_one_y_inv.mul(y).mul(x_minus_one);
419 yed.cMov(Fe.one, @intFromBool(x_plus_one_y_inv.isZero()));
420
421 return Edwards25519{
422 .x = xed,
423 .y = yed,
424 .z = Fe.one,
425 .t = xed.mul(yed),
426 };
427 }
428
429 /// Elligator2 map - Returns Montgomery affine coordinates
430 pub fn elligator2(r: Fe) struct { x: Fe, y: Fe, not_square: bool } {
431 const rr2 = r.sq2().add(Fe.one).invert();
432 var x = rr2.mul32(Fe.edwards25519a_32).neg(); // x=x1
433 var x2 = x.sq();
434 const x3 = x2.mul(x);
435 x2 = x2.mul32(Fe.edwards25519a_32); // x2 = A*x1^2
436 const gx1 = x3.add(x).add(x2); // gx1 = x1^3 + A*x1^2 + x1
437 const not_square = !gx1.isSquare();
438
439 // gx1 not a square => x = -x1-A
440 x.cMov(x.neg(), @intFromBool(not_square));
441 x2 = Fe.zero;
442 x2.cMov(Fe.edwards25519a, @intFromBool(not_square));
443 x = x.sub(x2);
444
445 // We have y = sqrt(gx1) or sqrt(gx2) with gx2 = gx1*(A+x1)/(-x1)
446 // but it is about as fast to just recompute y from the curve equation.
447 const y = xmontToYmont(x) catch unreachable;
448 return .{ .x = x, .y = y, .not_square = not_square };
449 }
450
451 /// Map a 64-bit hash into an Edwards25519 point
452 pub fn fromHash(h: [64]u8) Edwards25519 {
453 const fe_f = Fe.fromBytes64(h);
454 var elr = elligator2(fe_f);
455
456 const y_sign = !elr.not_square;
457 const y_neg = elr.y.neg();
458 elr.y.cMov(y_neg, @intFromBool(elr.y.isNegative()) ^ @intFromBool(y_sign));
459 return montToEd(elr.x, elr.y).clearCofactor();
460 }
461
462 fn stringToPoints(comptime n: usize, ctx: []const u8, s: []const u8) [n]Edwards25519 {
463 debug.assert(n <= 2);
464 const H = crypto.hash.sha2.Sha512;
465 const h_l: usize = 48;
466 var xctx = ctx;
467 var hctx: [H.digest_length]u8 = undefined;
468 if (ctx.len > 0xff) {
469 var st = H.init(.{});
470 st.update("H2C-OVERSIZE-DST-");
471 st.update(ctx);
472 st.final(&hctx);
473 xctx = hctx[0..];
474 }
475 const empty_block = [_]u8{0} ** H.block_length;
476 var t = [3]u8{ 0, n * h_l, 0 };
477 var xctx_len_u8 = [1]u8{@as(u8, @intCast(xctx.len))};
478 var st = H.init(.{});
479 st.update(empty_block[0..]);
480 st.update(s);
481 st.update(t[0..]);
482 st.update(xctx);
483 st.update(xctx_len_u8[0..]);
484 var u_0: [H.digest_length]u8 = undefined;
485 st.final(&u_0);
486 var u: [n * H.digest_length]u8 = undefined;
487 var i: usize = 0;
488 while (i < n * H.digest_length) : (i += H.digest_length) {
489 u[i..][0..H.digest_length].* = u_0;
490 var j: usize = 0;
491 while (i > 0 and j < H.digest_length) : (j += 1) {
492 u[i + j] ^= u[i + j - H.digest_length];
493 }
494 t[2] += 1;
495 st = H.init(.{});
496 st.update(u[i..][0..H.digest_length]);
497 st.update(t[2..3]);
498 st.update(xctx);
499 st.update(xctx_len_u8[0..]);
500 st.final(u[i..][0..H.digest_length]);
501 }
502 var px: [n]Edwards25519 = undefined;
503 i = 0;
504 while (i < n) : (i += 1) {
505 @memset(u_0[0 .. H.digest_length - h_l], 0);
506 u_0[H.digest_length - h_l ..][0..h_l].* = u[i * h_l ..][0..h_l].*;
507 px[i] = fromHash(u_0);
508 }
509 return px;
510 }
511
512 /// Hash a context `ctx` and a string `s` into an Edwards25519 point
513 ///
514 /// This function implements the edwards25519_XMD:SHA-512_ELL2_RO_ and edwards25519_XMD:SHA-512_ELL2_NU_
515 /// methods from the "Hashing to Elliptic Curves" standard document.
516 ///
517 /// Although not strictly required by the standard, it is recommended to avoid NUL characters in
518 /// the context in order to be compatible with other implementations.
519 pub fn fromString(comptime random_oracle: bool, ctx: []const u8, s: []const u8) Edwards25519 {
520 if (random_oracle) {
521 const px = stringToPoints(2, ctx, s);
522 return px[0].add(px[1]);
523 } else {
524 return stringToPoints(1, ctx, s)[0];
525 }
526 }
527
528 /// Map a 32 bit uniform bit string into an edwards25519 point
529 pub fn fromUniform(r: [32]u8) Edwards25519 {
530 var s = r;
531 const x_sign = s[31] >> 7;
532 s[31] &= 0x7f;
533 const elr = elligator2(Fe.fromBytes(s));
534 var p = montToEd(elr.x, elr.y);
535 const p_neg = p.neg();
536 p.cMov(p_neg, @intFromBool(p.x.isNegative()) ^ x_sign);
537 return p.clearCofactor();
538 }
539};
540
541const htest = @import("../test.zig");
542
543test "packing/unpacking" {
544 const s = [_]u8{170} ++ [_]u8{0} ** 31;
545 var b = Edwards25519.basePoint;
546 const pk = try b.mul(s);
547 var buf: [128]u8 = undefined;
548 try std.testing.expectEqualStrings(try std.fmt.bufPrint(&buf, "{X}", .{&pk.toBytes()}), "074BC7E0FCBD587FDBC0969444245FADC562809C8F6E97E949AF62484B5B81A6");
549
550 const small_order_ss: [7][32]u8 = .{
551 .{
552 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)
553 },
554 .{
555 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)
556 },
557 .{
558 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)
559 },
560 .{
561 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)
562 },
563 .{
564 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)
565 },
566 .{
567 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)
568 },
569 .{
570 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)
571 },
572 };
573 for (small_order_ss) |small_order_s| {
574 const small_p = try Edwards25519.fromBytes(small_order_s);
575 try std.testing.expectError(error.WeakPublicKey, small_p.mul(s));
576 }
577}
578
579test "point addition/subtraction" {
580 var s1: [32]u8 = undefined;
581 var s2: [32]u8 = undefined;
582 crypto.random.bytes(&s1);
583 crypto.random.bytes(&s2);
584 const p = try Edwards25519.basePoint.clampedMul(s1);
585 const q = try Edwards25519.basePoint.clampedMul(s2);
586 const r = p.add(q).add(q).sub(q).sub(q);
587 try r.rejectIdentity();
588 try std.testing.expectError(error.IdentityElement, r.sub(p).rejectIdentity());
589 try std.testing.expectError(error.IdentityElement, p.sub(p).rejectIdentity());
590 try std.testing.expectError(error.IdentityElement, p.sub(q).add(q).sub(p).rejectIdentity());
591}
592
593test "uniform-to-point" {
594 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 };
595 var p = Edwards25519.fromUniform(r);
596 try htest.assertEqual("0691eee3cf70a0056df6bfa03120635636581b5c4ea571dfc680f78c7e0b4137", p.toBytes()[0..]);
597
598 r[31] = 0xff;
599 p = Edwards25519.fromUniform(r);
600 try htest.assertEqual("f70718e68ef42d90ca1d936bb2d7e159be6c01d8095d39bd70487c82fe5c973a", p.toBytes()[0..]);
601}
602
603// Test vectors from draft-irtf-cfrg-hash-to-curve-12
604test "hash-to-curve operation" {
605 var p = Edwards25519.fromString(true, "QUUX-V01-CS02-with-edwards25519_XMD:SHA-512_ELL2_RO_", "abc");
606 try htest.assertEqual("31558a26887f23fb8218f143e69d5f0af2e7831130bd5b432ef23883b895839a", p.toBytes()[0..]);
607
608 p = Edwards25519.fromString(false, "QUUX-V01-CS02-with-edwards25519_XMD:SHA-512_ELL2_NU_", "abc");
609 try htest.assertEqual("42fa27c8f5a1ae0aa38bb59d5938e5145622ba5dedd11d11736fa2f9502d7367", p.toBytes()[0..]);
610}
611
612test "implicit reduction of invalid scalars" {
613 const s = [_]u8{0} ** 31 ++ [_]u8{255};
614 const p1 = try Edwards25519.basePoint.mulPublic(s);
615 const p2 = try Edwards25519.basePoint.mul(s);
616 const p3 = try p1.mulPublic(s);
617 const p4 = try p1.mul(s);
618
619 try std.testing.expectEqualSlices(u8, p1.toBytes()[0..], p2.toBytes()[0..]);
620 try std.testing.expectEqualSlices(u8, p3.toBytes()[0..], p4.toBytes()[0..]);
621
622 try htest.assertEqual("339f189ecc5fbebe9895345c72dc07bda6e615f8a40e768441b6f529cd6c671a", p1.toBytes()[0..]);
623 try htest.assertEqual("a501e4c595a3686d8bee7058c7e6af7fd237f945c47546910e37e0e79b1bafb0", p3.toBytes()[0..]);
624}
625
626test "subgroup check" {
627 for (0..100) |_| {
628 var p = Edwards25519.basePoint;
629 const s = Edwards25519.scalar.random();
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}