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