master
1const std = @import("std");
2const crypto = std.crypto;
3const mem = std.mem;
4const meta = std.meta;
5
6const EncodingError = crypto.errors.EncodingError;
7const IdentityElementError = crypto.errors.IdentityElementError;
8const NonCanonicalError = crypto.errors.NonCanonicalError;
9const NotSquareError = crypto.errors.NotSquareError;
10
11/// Group operations over P384.
12pub const P384 = struct {
13 /// The underlying prime field.
14 pub const Fe = @import("p384/field.zig").Fe;
15 /// Field arithmetic mod the order of the main subgroup.
16 pub const scalar = @import("p384/scalar.zig");
17
18 x: Fe,
19 y: Fe,
20 z: Fe = Fe.one,
21
22 is_base: bool = false,
23
24 /// The P384 base point.
25 pub const basePoint = P384{
26 .x = Fe.fromInt(26247035095799689268623156744566981891852923491109213387815615900925518854738050089022388053975719786650872476732087) catch unreachable,
27 .y = Fe.fromInt(8325710961489029985546751289520108179287853048861315594709205902480503199884419224438643760392947333078086511627871) catch unreachable,
28 .z = Fe.one,
29 .is_base = true,
30 };
31
32 /// The P384 neutral element.
33 pub const identityElement = P384{ .x = Fe.zero, .y = Fe.one, .z = Fe.zero };
34
35 pub const B = Fe.fromInt(27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575) catch unreachable;
36
37 /// Reject the neutral element.
38 pub fn rejectIdentity(p: P384) IdentityElementError!void {
39 const affine_0 = @intFromBool(p.x.equivalent(AffineCoordinates.identityElement.x)) & (@intFromBool(p.y.isZero()) | @intFromBool(p.y.equivalent(AffineCoordinates.identityElement.y)));
40 const is_identity = @intFromBool(p.z.isZero()) | affine_0;
41 if (is_identity != 0) {
42 return error.IdentityElement;
43 }
44 }
45
46 /// Create a point from affine coordinates after checking that they match the curve equation.
47 pub fn fromAffineCoordinates(p: AffineCoordinates) EncodingError!P384 {
48 const x = p.x;
49 const y = p.y;
50 const x3AxB = x.sq().mul(x).sub(x).sub(x).sub(x).add(B);
51 const yy = y.sq();
52 const on_curve = @intFromBool(x3AxB.equivalent(yy));
53 const is_identity = @intFromBool(x.equivalent(AffineCoordinates.identityElement.x)) & @intFromBool(y.equivalent(AffineCoordinates.identityElement.y));
54 if ((on_curve | is_identity) == 0) {
55 return error.InvalidEncoding;
56 }
57 var ret = P384{ .x = x, .y = y, .z = Fe.one };
58 ret.z.cMov(P384.identityElement.z, is_identity);
59 return ret;
60 }
61
62 /// Create a point from serialized affine coordinates.
63 pub fn fromSerializedAffineCoordinates(xs: [48]u8, ys: [48]u8, endian: std.builtin.Endian) (NonCanonicalError || EncodingError)!P384 {
64 const x = try Fe.fromBytes(xs, endian);
65 const y = try Fe.fromBytes(ys, endian);
66 return fromAffineCoordinates(.{ .x = x, .y = y });
67 }
68
69 /// Recover the Y coordinate from the X coordinate.
70 pub fn recoverY(x: Fe, is_odd: bool) NotSquareError!Fe {
71 const x3AxB = x.sq().mul(x).sub(x).sub(x).sub(x).add(B);
72 var y = try x3AxB.sqrt();
73 const yn = y.neg();
74 y.cMov(yn, @intFromBool(is_odd) ^ @intFromBool(y.isOdd()));
75 return y;
76 }
77
78 /// Deserialize a SEC1-encoded point.
79 pub fn fromSec1(s: []const u8) (EncodingError || NotSquareError || NonCanonicalError)!P384 {
80 if (s.len < 1) return error.InvalidEncoding;
81 const encoding_type = s[0];
82 const encoded = s[1..];
83 switch (encoding_type) {
84 0 => {
85 if (encoded.len != 0) return error.InvalidEncoding;
86 return P384.identityElement;
87 },
88 2, 3 => {
89 if (encoded.len != 48) return error.InvalidEncoding;
90 const x = try Fe.fromBytes(encoded[0..48].*, .big);
91 const y_is_odd = (encoding_type == 3);
92 const y = try recoverY(x, y_is_odd);
93 return P384{ .x = x, .y = y };
94 },
95 4 => {
96 if (encoded.len != 96) return error.InvalidEncoding;
97 const x = try Fe.fromBytes(encoded[0..48].*, .big);
98 const y = try Fe.fromBytes(encoded[48..96].*, .big);
99 return P384.fromAffineCoordinates(.{ .x = x, .y = y });
100 },
101 else => return error.InvalidEncoding,
102 }
103 }
104
105 /// Serialize a point using the compressed SEC-1 format.
106 pub fn toCompressedSec1(p: P384) [49]u8 {
107 var out: [49]u8 = undefined;
108 const xy = p.affineCoordinates();
109 out[0] = if (xy.y.isOdd()) 3 else 2;
110 out[1..].* = xy.x.toBytes(.big);
111 return out;
112 }
113
114 /// Serialize a point using the uncompressed SEC-1 format.
115 pub fn toUncompressedSec1(p: P384) [97]u8 {
116 var out: [97]u8 = undefined;
117 out[0] = 4;
118 const xy = p.affineCoordinates();
119 out[1..49].* = xy.x.toBytes(.big);
120 out[49..97].* = xy.y.toBytes(.big);
121 return out;
122 }
123
124 /// Return a random point.
125 pub fn random() P384 {
126 const n = scalar.random(.little);
127 return basePoint.mul(n, .little) catch unreachable;
128 }
129
130 /// Flip the sign of the X coordinate.
131 pub fn neg(p: P384) P384 {
132 return .{ .x = p.x, .y = p.y.neg(), .z = p.z };
133 }
134
135 /// Double a P384 point.
136 // Algorithm 6 from https://eprint.iacr.org/2015/1060.pdf
137 pub fn dbl(p: P384) P384 {
138 var t0 = p.x.sq();
139 var t1 = p.y.sq();
140 var t2 = p.z.sq();
141 var t3 = p.x.mul(p.y);
142 t3 = t3.dbl();
143 var Z3 = p.x.mul(p.z);
144 Z3 = Z3.add(Z3);
145 var Y3 = B.mul(t2);
146 Y3 = Y3.sub(Z3);
147 var X3 = Y3.dbl();
148 Y3 = X3.add(Y3);
149 X3 = t1.sub(Y3);
150 Y3 = t1.add(Y3);
151 Y3 = X3.mul(Y3);
152 X3 = X3.mul(t3);
153 t3 = t2.dbl();
154 t2 = t2.add(t3);
155 Z3 = B.mul(Z3);
156 Z3 = Z3.sub(t2);
157 Z3 = Z3.sub(t0);
158 t3 = Z3.dbl();
159 Z3 = Z3.add(t3);
160 t3 = t0.dbl();
161 t0 = t3.add(t0);
162 t0 = t0.sub(t2);
163 t0 = t0.mul(Z3);
164 Y3 = Y3.add(t0);
165 t0 = p.y.mul(p.z);
166 t0 = t0.dbl();
167 Z3 = t0.mul(Z3);
168 X3 = X3.sub(Z3);
169 Z3 = t0.mul(t1);
170 Z3 = Z3.dbl().dbl();
171 return .{
172 .x = X3,
173 .y = Y3,
174 .z = Z3,
175 };
176 }
177
178 /// Add P384 points, the second being specified using affine coordinates.
179 // Algorithm 5 from https://eprint.iacr.org/2015/1060.pdf
180 pub fn addMixed(p: P384, q: AffineCoordinates) P384 {
181 var t0 = p.x.mul(q.x);
182 var t1 = p.y.mul(q.y);
183 var t3 = q.x.add(q.y);
184 var t4 = p.x.add(p.y);
185 t3 = t3.mul(t4);
186 t4 = t0.add(t1);
187 t3 = t3.sub(t4);
188 t4 = q.y.mul(p.z);
189 t4 = t4.add(p.y);
190 var Y3 = q.x.mul(p.z);
191 Y3 = Y3.add(p.x);
192 var Z3 = B.mul(p.z);
193 var X3 = Y3.sub(Z3);
194 Z3 = X3.dbl();
195 X3 = X3.add(Z3);
196 Z3 = t1.sub(X3);
197 X3 = t1.add(X3);
198 Y3 = B.mul(Y3);
199 t1 = p.z.dbl();
200 var t2 = t1.add(p.z);
201 Y3 = Y3.sub(t2);
202 Y3 = Y3.sub(t0);
203 t1 = Y3.dbl();
204 Y3 = t1.add(Y3);
205 t1 = t0.dbl();
206 t0 = t1.add(t0);
207 t0 = t0.sub(t2);
208 t1 = t4.mul(Y3);
209 t2 = t0.mul(Y3);
210 Y3 = X3.mul(Z3);
211 Y3 = Y3.add(t2);
212 X3 = t3.mul(X3);
213 X3 = X3.sub(t1);
214 Z3 = t4.mul(Z3);
215 t1 = t3.mul(t0);
216 Z3 = Z3.add(t1);
217 var ret = P384{
218 .x = X3,
219 .y = Y3,
220 .z = Z3,
221 };
222 ret.cMov(p, @intFromBool(q.x.isZero()));
223 return ret;
224 }
225
226 /// Add P384 points.
227 // Algorithm 4 from https://eprint.iacr.org/2015/1060.pdf
228 pub fn add(p: P384, q: P384) P384 {
229 var t0 = p.x.mul(q.x);
230 var t1 = p.y.mul(q.y);
231 var t2 = p.z.mul(q.z);
232 var t3 = p.x.add(p.y);
233 var t4 = q.x.add(q.y);
234 t3 = t3.mul(t4);
235 t4 = t0.add(t1);
236 t3 = t3.sub(t4);
237 t4 = p.y.add(p.z);
238 var X3 = q.y.add(q.z);
239 t4 = t4.mul(X3);
240 X3 = t1.add(t2);
241 t4 = t4.sub(X3);
242 X3 = p.x.add(p.z);
243 var Y3 = q.x.add(q.z);
244 X3 = X3.mul(Y3);
245 Y3 = t0.add(t2);
246 Y3 = X3.sub(Y3);
247 var Z3 = B.mul(t2);
248 X3 = Y3.sub(Z3);
249 Z3 = X3.dbl();
250 X3 = X3.add(Z3);
251 Z3 = t1.sub(X3);
252 X3 = t1.add(X3);
253 Y3 = B.mul(Y3);
254 t1 = t2.dbl();
255 t2 = t1.add(t2);
256 Y3 = Y3.sub(t2);
257 Y3 = Y3.sub(t0);
258 t1 = Y3.dbl();
259 Y3 = t1.add(Y3);
260 t1 = t0.dbl();
261 t0 = t1.add(t0);
262 t0 = t0.sub(t2);
263 t1 = t4.mul(Y3);
264 t2 = t0.mul(Y3);
265 Y3 = X3.mul(Z3);
266 Y3 = Y3.add(t2);
267 X3 = t3.mul(X3);
268 X3 = X3.sub(t1);
269 Z3 = t4.mul(Z3);
270 t1 = t3.mul(t0);
271 Z3 = Z3.add(t1);
272 return .{
273 .x = X3,
274 .y = Y3,
275 .z = Z3,
276 };
277 }
278
279 /// Subtract P384 points.
280 pub fn sub(p: P384, q: P384) P384 {
281 return p.add(q.neg());
282 }
283
284 /// Subtract P384 points, the second being specified using affine coordinates.
285 pub fn subMixed(p: P384, q: AffineCoordinates) P384 {
286 return p.addMixed(q.neg());
287 }
288
289 /// Return affine coordinates.
290 pub fn affineCoordinates(p: P384) AffineCoordinates {
291 const affine_0 = @intFromBool(p.x.equivalent(AffineCoordinates.identityElement.x)) & (@intFromBool(p.y.isZero()) | @intFromBool(p.y.equivalent(AffineCoordinates.identityElement.y)));
292 const is_identity = @intFromBool(p.z.isZero()) | affine_0;
293 const zinv = p.z.invert();
294 var ret = AffineCoordinates{
295 .x = p.x.mul(zinv),
296 .y = p.y.mul(zinv),
297 };
298 ret.cMov(AffineCoordinates.identityElement, is_identity);
299 return ret;
300 }
301
302 /// Return true if both coordinate sets represent the same point.
303 pub fn equivalent(a: P384, b: P384) bool {
304 if (a.sub(b).rejectIdentity()) {
305 return false;
306 } else |_| {
307 return true;
308 }
309 }
310
311 fn cMov(p: *P384, a: P384, c: u1) void {
312 p.x.cMov(a.x, c);
313 p.y.cMov(a.y, c);
314 p.z.cMov(a.z, c);
315 }
316
317 fn pcSelect(comptime n: usize, pc: *const [n]P384, b: u8) P384 {
318 var t = P384.identityElement;
319 comptime var i: u8 = 1;
320 inline while (i < pc.len) : (i += 1) {
321 t.cMov(pc[i], @as(u1, @truncate((@as(usize, b ^ i) -% 1) >> 8)));
322 }
323 return t;
324 }
325
326 fn slide(s: [48]u8) [2 * 48 + 1]i8 {
327 var e: [2 * 48 + 1]i8 = undefined;
328 for (s, 0..) |x, i| {
329 e[i * 2 + 0] = @as(i8, @as(u4, @truncate(x)));
330 e[i * 2 + 1] = @as(i8, @as(u4, @truncate(x >> 4)));
331 }
332 // Now, e[0..63] is between 0 and 15, e[63] is between 0 and 7
333 var carry: i8 = 0;
334 for (e[0..96]) |*x| {
335 x.* += carry;
336 carry = (x.* + 8) >> 4;
337 x.* -= carry * 16;
338 std.debug.assert(x.* >= -8 and x.* <= 8);
339 }
340 e[96] = carry;
341 // Now, e[*] is between -8 and 8, including e[64]
342 std.debug.assert(carry >= -8 and carry <= 8);
343 return e;
344 }
345
346 fn pcMul(pc: *const [9]P384, s: [48]u8, comptime vartime: bool) IdentityElementError!P384 {
347 std.debug.assert(vartime);
348 const e = slide(s);
349 var q = P384.identityElement;
350 var pos = e.len - 1;
351 while (true) : (pos -= 1) {
352 const slot = e[pos];
353 if (slot > 0) {
354 q = q.add(pc[@as(usize, @intCast(slot))]);
355 } else if (slot < 0) {
356 q = q.sub(pc[@as(usize, @intCast(-slot))]);
357 }
358 if (pos == 0) break;
359 q = q.dbl().dbl().dbl().dbl();
360 }
361 try q.rejectIdentity();
362 return q;
363 }
364
365 fn pcMul16(pc: *const [16]P384, s: [48]u8, comptime vartime: bool) IdentityElementError!P384 {
366 var q = P384.identityElement;
367 var pos: usize = 380;
368 while (true) : (pos -= 4) {
369 const slot = @as(u4, @truncate((s[pos >> 3] >> @as(u3, @truncate(pos)))));
370 if (vartime) {
371 if (slot != 0) {
372 q = q.add(pc[slot]);
373 }
374 } else {
375 q = q.add(pcSelect(16, pc, slot));
376 }
377 if (pos == 0) break;
378 q = q.dbl().dbl().dbl().dbl();
379 }
380 try q.rejectIdentity();
381 return q;
382 }
383
384 fn precompute(p: P384, comptime count: usize) [1 + count]P384 {
385 var pc: [1 + count]P384 = undefined;
386 pc[0] = P384.identityElement;
387 pc[1] = p;
388 var i: usize = 2;
389 while (i <= count) : (i += 1) {
390 pc[i] = if (i % 2 == 0) pc[i / 2].dbl() else pc[i - 1].add(p);
391 }
392 return pc;
393 }
394
395 const basePointPc = pc: {
396 @setEvalBranchQuota(70000);
397 break :pc precompute(P384.basePoint, 15);
398 };
399
400 /// Multiply an elliptic curve point by a scalar.
401 /// Return error.IdentityElement if the result is the identity element.
402 pub fn mul(p: P384, s_: [48]u8, endian: std.builtin.Endian) IdentityElementError!P384 {
403 const s = if (endian == .little) s_ else Fe.orderSwap(s_);
404 if (p.is_base) {
405 return pcMul16(&basePointPc, s, false);
406 }
407 try p.rejectIdentity();
408 const pc = precompute(p, 15);
409 return pcMul16(&pc, s, false);
410 }
411
412 /// Multiply an elliptic curve point by a *PUBLIC* scalar *IN VARIABLE TIME*
413 /// This can be used for signature verification.
414 pub fn mulPublic(p: P384, s_: [48]u8, endian: std.builtin.Endian) IdentityElementError!P384 {
415 const s = if (endian == .little) s_ else Fe.orderSwap(s_);
416 if (p.is_base) {
417 return pcMul16(&basePointPc, s, true);
418 }
419 try p.rejectIdentity();
420 const pc = precompute(p, 8);
421 return pcMul(&pc, s, true);
422 }
423
424 /// Double-base multiplication of public parameters - Compute (p1*s1)+(p2*s2) *IN VARIABLE TIME*
425 /// This can be used for signature verification.
426 pub fn mulDoubleBasePublic(p1: P384, s1_: [48]u8, p2: P384, s2_: [48]u8, endian: std.builtin.Endian) IdentityElementError!P384 {
427 const s1 = if (endian == .little) s1_ else Fe.orderSwap(s1_);
428 const s2 = if (endian == .little) s2_ else Fe.orderSwap(s2_);
429 try p1.rejectIdentity();
430 var pc1_array: [9]P384 = undefined;
431 const pc1 = if (p1.is_base) basePointPc[0..9] else pc: {
432 pc1_array = precompute(p1, 8);
433 break :pc &pc1_array;
434 };
435 try p2.rejectIdentity();
436 var pc2_array: [9]P384 = undefined;
437 const pc2 = if (p2.is_base) basePointPc[0..9] else pc: {
438 pc2_array = precompute(p2, 8);
439 break :pc &pc2_array;
440 };
441 const e1 = slide(s1);
442 const e2 = slide(s2);
443 var q = P384.identityElement;
444 var pos: usize = 2 * 48;
445 while (true) : (pos -= 1) {
446 const slot1 = e1[pos];
447 if (slot1 > 0) {
448 q = q.add(pc1[@as(usize, @intCast(slot1))]);
449 } else if (slot1 < 0) {
450 q = q.sub(pc1[@as(usize, @intCast(-slot1))]);
451 }
452 const slot2 = e2[pos];
453 if (slot2 > 0) {
454 q = q.add(pc2[@as(usize, @intCast(slot2))]);
455 } else if (slot2 < 0) {
456 q = q.sub(pc2[@as(usize, @intCast(-slot2))]);
457 }
458 if (pos == 0) break;
459 q = q.dbl().dbl().dbl().dbl();
460 }
461 try q.rejectIdentity();
462 return q;
463 }
464};
465
466/// A point in affine coordinates.
467pub const AffineCoordinates = struct {
468 x: P384.Fe,
469 y: P384.Fe,
470
471 /// Identity element in affine coordinates.
472 pub const identityElement = AffineCoordinates{ .x = P384.identityElement.x, .y = P384.identityElement.y };
473
474 pub fn neg(p: AffineCoordinates) AffineCoordinates {
475 return .{ .x = p.x, .y = p.y.neg() };
476 }
477
478 fn cMov(p: *AffineCoordinates, a: AffineCoordinates, c: u1) void {
479 p.x.cMov(a.x, c);
480 p.y.cMov(a.y, c);
481 }
482};
483
484test {
485 if (@import("builtin").zig_backend == .stage2_c) return error.SkipZigTest;
486
487 _ = @import("tests/p384.zig");
488}