1const std = @import("std");
2const crypto = std.crypto;
3
4const IdentityElementError = crypto.errors.IdentityElementError;
5const NonCanonicalError = crypto.errors.NonCanonicalError;
6const WeakPublicKeyError = crypto.errors.WeakPublicKeyError;
7
8/// Group operations over Curve25519.
9pub const Curve25519 = struct {
10 /// The underlying prime field.
11 pub const Fe = @import("field.zig").Fe;
12 /// Field arithmetic mod the order of the main subgroup.
13 pub const scalar = @import("scalar.zig");
14
15 x: Fe,
16
17 /// Decode a Curve25519 point from its compressed (X) coordinates.
18 pub fn fromBytes(s: [32]u8) Curve25519 {
19 return .{ .x = Fe.fromBytes(s) };
20 }
21
22 /// Encode a Curve25519 point.
23 pub fn toBytes(p: Curve25519) [32]u8 {
24 return p.x.toBytes();
25 }
26
27 /// The Curve25519 base point.
28 pub const basePoint = Curve25519{ .x = Fe.curve25519BasePoint };
29
30 /// Check that the encoding of a Curve25519 point is canonical.
31 pub fn rejectNonCanonical(s: [32]u8) NonCanonicalError!void {
32 return Fe.rejectNonCanonical(s, false);
33 }
34
35 /// Reject the neutral element.
36 pub fn rejectIdentity(p: Curve25519) IdentityElementError!void {
37 if (p.x.isZero()) {
38 return error.IdentityElement;
39 }
40 }
41
42 /// Multiply a point by the cofactor, returning WeakPublicKey if the element is in a small-order group.
43 pub fn clearCofactor(p: Curve25519) WeakPublicKeyError!Curve25519 {
44 const cofactor = [_]u8{8} ++ @as([31]u8, @splat(0));
45 return ladder(p, cofactor, 4) catch return error.WeakPublicKey;
46 }
47
48 fn ladder(p: Curve25519, s: [32]u8, comptime bits: usize) IdentityElementError!Curve25519 {
49 var x1 = p.x;
50 var x2 = Fe.one;
51 var z2 = Fe.zero;
52 var x3 = x1;
53 var z3 = Fe.one;
54 var swap: u8 = 0;
55 var pos: usize = bits - 1;
56 while (true) : (pos -= 1) {
57 const bit = (s[pos >> 3] >> @as(u3, @truncate(pos))) & 1;
58 swap ^= bit;
59 Fe.cSwap2(&x2, &x3, &z2, &z3, swap);
60 swap = bit;
61 const a = x2.add(z2);
62 const b = x2.sub(z2);
63 const aa = a.sq();
64 const bb = b.sq();
65 x2 = aa.mul(bb);
66 const e = aa.sub(bb);
67 const da = x3.sub(z3).mul(a);
68 const cb = x3.add(z3).mul(b);
69 x3 = da.add(cb).sq();
70 z3 = x1.mul(da.sub(cb).sq());
71 z2 = e.mul(bb.add(e.mul32(121666)));
72 if (pos == 0) break;
73 }
74 Fe.cSwap2(&x2, &x3, &z2, &z3, swap);
75 z2 = z2.invert();
76 x2 = x2.mul(z2);
77 if (x2.isZero()) {
78 return error.IdentityElement;
79 }
80 return Curve25519{ .x = x2 };
81 }
82
83 /// Multiply a Curve25519 point by a scalar after "clamping" it.
84 /// Clamping forces the scalar to be a multiple of the cofactor in
85 /// order to prevent small subgroups attacks. This is the standard
86 /// way to use Curve25519 for a DH operation.
87 /// Return error.IdentityElement if the resulting point is
88 /// the identity element.
89 pub fn clampedMul(p: Curve25519, s: [32]u8) IdentityElementError!Curve25519 {
90 var t: [32]u8 = s;
91 scalar.clamp(&t);
92 return try ladder(p, t, 255);
93 }
94
95 /// Multiply a Curve25519 point by a scalar without clamping it.
96 /// Return error.IdentityElement if the resulting point is
97 /// the identity element or error.WeakPublicKey if the public
98 /// key is a low-order point.
99 pub fn mul(p: Curve25519, s: [32]u8) (IdentityElementError || WeakPublicKeyError)!Curve25519 {
100 _ = try p.clearCofactor();
101 return try ladder(p, s, 256);
102 }
103
104 /// Elligator2 map for Curve25519.
105 pub fn elligator2(r: Fe) Curve25519 {
106 return .{ .x = crypto.ecc.Edwards25519.elligator2(r).x };
107 }
108
109 /// Compute the Curve25519 equivalent to an Edwards25519 point.
110 ///
111 /// Note that the function doesn't check that the input point is
112 /// on the prime order group, e.g. that it is an Ed25519 public key
113 /// for which an Ed25519 secret key exists.
114 ///
115 /// If this is required, for example for compatibility with libsodium's strict
116 /// validation policy, the caller can call the `rejectUnexpectedSubgroup` function
117 /// on the input point before calling this function.
118 pub fn fromEdwards25519(p: crypto.ecc.Edwards25519) IdentityElementError!Curve25519 {
119 try p.clearCofactor().rejectIdentity();
120 const one = crypto.ecc.Edwards25519.Fe.one;
121 const py = p.y.mul(p.z.invert());
122 const x = one.add(py).mul(one.sub(py).invert()); // xMont=(1+yEd)/(1-yEd)
123 return Curve25519{ .x = x };
124 }
125};
126
127test "curve25519" {
128 var s = [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 };
129 const p = try Curve25519.basePoint.clampedMul(s);
130 try p.rejectIdentity();
131 var buf: [128]u8 = undefined;
132 try std.testing.expectEqualStrings(try std.mem.print(&buf, "{X}", .{&p.toBytes()}), "E6F2A4D1C28EE5C7AD0329268255A468AD407D2672824C0C0EB30EA6EF450145");
133 const q = try p.clampedMul(s);
134 try std.testing.expectEqualStrings(try std.mem.print(&buf, "{X}", .{&q.toBytes()}), "3614E119FFE55EC55B87D6B19971A9F4CBC78EFE80BEC55B96392BABCC712537");
135
136 try Curve25519.rejectNonCanonical(s);
137 s[31] |= 0x80;
138 try std.testing.expectError(error.NonCanonical, Curve25519.rejectNonCanonical(s));
139}
140
141test "non-affine edwards25519 to curve25519 projection" {
142 const skh = "90e7595fc89e52fdfddce9c6a43d74dbf6047025ee0462d2d172e8b6a2841d6e";
143 var sk: [32]u8 = undefined;
144 _ = std.fmt.hexToBytes(&sk, skh) catch unreachable;
145 const edp = try crypto.ecc.Edwards25519.basePoint.mul(sk);
146 const xp = try Curve25519.fromEdwards25519(edp);
147 const expected_hex = "cc4f2cdb695dd766f34118eb67b98652fed1d8bc49c330b119bbfa8a64989378";
148 var expected: [32]u8 = undefined;
149 _ = std.fmt.hexToBytes(&expected, expected_hex) catch unreachable;
150 try std.testing.expectEqualSlices(u8, &xp.toBytes(), &expected);
151}
152
153test "elligator2" {
154 const Fe = Curve25519.Fe;
155
156 // RFC 9380 Appendix J.4.2 test vector (curve25519_XMD:SHA-512_ELL2_NU_)
157 // u = 0x608d892b641f0328523802a6603427c26e55e6f27e71a91a478148d45b5093cd
158 // Q.x = 0x51125222da5e763d97f3c10fcc92ea6860b9ccbbd2eb1285728f566721c1e65b
159 const u = Fe.fromBytes(.{
160 0xcd, 0x93, 0x50, 0x5b, 0xd4, 0x48, 0x81, 0x47, 0x1a, 0xa9, 0x71, 0x7e, 0xf2, 0xe6, 0x55, 0x6e,
161 0xc2, 0x27, 0x34, 0x60, 0xa6, 0x02, 0x38, 0x52, 0x28, 0x03, 0x1f, 0x64, 0x2b, 0x89, 0x8d, 0x60,
162 });
163 const p = Curve25519.elligator2(u);
164 try std.testing.expectEqual([32]u8{
165 0x5b, 0xe6, 0xc1, 0x21, 0x67, 0x56, 0x8f, 0x72, 0x85, 0x12, 0xeb, 0xd2, 0xbb, 0xcc, 0xb9, 0x60,
166 0x68, 0xea, 0x92, 0xcc, 0x0f, 0xc1, 0xf3, 0x97, 0x3d, 0x76, 0x5e, 0xda, 0x22, 0x52, 0x12, 0x51,
167 }, p.toBytes());
168}
169
170test "small order check" {
171 var s: [32]u8 = [_]u8{1} ++ @as([31]u8, @splat(0));
172 const small_order_ss: [7][32]u8 = .{
173 .{
174 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)
175 },
176 .{
177 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)
178 },
179 .{
180 0xe0, 0xeb, 0x7a, 0x7c, 0x3b, 0x41, 0xb8, 0xae, 0x16, 0x56, 0xe3, 0xfa, 0xf1, 0x9f, 0xc4, 0x6a, 0xda, 0x09, 0x8d, 0xeb, 0x9c, 0x32, 0xb1, 0xfd, 0x86, 0x62, 0x05, 0x16, 0x5f, 0x49, 0xb8, 0x00, // 325606250916557431795983626356110631294008115727848805560023387167927233504 (order 8) */
181 },
182 .{
183 0x5f, 0x9c, 0x95, 0xbc, 0xa3, 0x50, 0x8c, 0x24, 0xb1, 0xd0, 0xb1, 0x55, 0x9c, 0x83, 0xef, 0x5b, 0x04, 0x44, 0x5c, 0xc4, 0x58, 0x1c, 0x8e, 0x86, 0xd8, 0x22, 0x4e, 0xdd, 0xd0, 0x9f, 0x11, 0x57, // 39382357235489614581723060781553021112529911719440698176882885853963445705823 (order 8)
184 },
185 .{
186 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)
187 },
188 .{
189 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)
190 },
191 .{
192 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)
193 },
194 };
195 for (small_order_ss) |small_order_s| {
196 try std.testing.expectError(error.WeakPublicKey, Curve25519.fromBytes(small_order_s).clearCofactor());
197 try std.testing.expectError(error.WeakPublicKey, Curve25519.fromBytes(small_order_s).mul(s));
198 var extra = small_order_s;
199 extra[31] ^= 0x80;
200 try std.testing.expectError(error.WeakPublicKey, Curve25519.fromBytes(extra).mul(s));
201 var valid = small_order_s;
202 valid[31] = 0x40;
203 s[0] = 0;
204 try std.testing.expectError(error.IdentityElement, Curve25519.fromBytes(valid).mul(s));
205 }
206}