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