master
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} ++ [_]u8{0} ** 31;
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 /// Compute the Curve25519 equivalent to an Edwards25519 point.
105 ///
106 /// Note that the function doesn't check that the input point is
107 /// on the prime order group, e.g. that it is an Ed25519 public key
108 /// for which an Ed25519 secret key exists.
109 ///
110 /// If this is required, for example for compatibility with libsodium's strict
111 /// validation policy, the caller can call the `rejectUnexpectedSubgroup` function
112 /// on the input point before calling this function.
113 pub fn fromEdwards25519(p: crypto.ecc.Edwards25519) IdentityElementError!Curve25519 {
114 try p.clearCofactor().rejectIdentity();
115 const one = crypto.ecc.Edwards25519.Fe.one;
116 const py = p.y.mul(p.z.invert());
117 const x = one.add(py).mul(one.sub(py).invert()); // xMont=(1+yEd)/(1-yEd)
118 return Curve25519{ .x = x };
119 }
120};
121
122test "curve25519" {
123 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 };
124 const p = try Curve25519.basePoint.clampedMul(s);
125 try p.rejectIdentity();
126 var buf: [128]u8 = undefined;
127 try std.testing.expectEqualStrings(try std.fmt.bufPrint(&buf, "{X}", .{&p.toBytes()}), "E6F2A4D1C28EE5C7AD0329268255A468AD407D2672824C0C0EB30EA6EF450145");
128 const q = try p.clampedMul(s);
129 try std.testing.expectEqualStrings(try std.fmt.bufPrint(&buf, "{X}", .{&q.toBytes()}), "3614E119FFE55EC55B87D6B19971A9F4CBC78EFE80BEC55B96392BABCC712537");
130
131 try Curve25519.rejectNonCanonical(s);
132 s[31] |= 0x80;
133 try std.testing.expectError(error.NonCanonical, Curve25519.rejectNonCanonical(s));
134}
135
136test "non-affine edwards25519 to curve25519 projection" {
137 const skh = "90e7595fc89e52fdfddce9c6a43d74dbf6047025ee0462d2d172e8b6a2841d6e";
138 var sk: [32]u8 = undefined;
139 _ = std.fmt.hexToBytes(&sk, skh) catch unreachable;
140 const edp = try crypto.ecc.Edwards25519.basePoint.mul(sk);
141 const xp = try Curve25519.fromEdwards25519(edp);
142 const expected_hex = "cc4f2cdb695dd766f34118eb67b98652fed1d8bc49c330b119bbfa8a64989378";
143 var expected: [32]u8 = undefined;
144 _ = std.fmt.hexToBytes(&expected, expected_hex) catch unreachable;
145 try std.testing.expectEqualSlices(u8, &xp.toBytes(), &expected);
146}
147
148test "small order check" {
149 var s: [32]u8 = [_]u8{1} ++ [_]u8{0} ** 31;
150 const small_order_ss: [7][32]u8 = .{
151 .{
152 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)
153 },
154 .{
155 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)
156 },
157 .{
158 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) */
159 },
160 .{
161 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)
162 },
163 .{
164 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)
165 },
166 .{
167 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)
168 },
169 .{
170 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)
171 },
172 };
173 for (small_order_ss) |small_order_s| {
174 try std.testing.expectError(error.WeakPublicKey, Curve25519.fromBytes(small_order_s).clearCofactor());
175 try std.testing.expectError(error.WeakPublicKey, Curve25519.fromBytes(small_order_s).mul(s));
176 var extra = small_order_s;
177 extra[31] ^= 0x80;
178 try std.testing.expectError(error.WeakPublicKey, Curve25519.fromBytes(extra).mul(s));
179 var valid = small_order_s;
180 valid[31] = 0x40;
181 s[0] = 0;
182 try std.testing.expectError(error.IdentityElement, Curve25519.fromBytes(valid).mul(s));
183 }
184}