curve.go raw
1 // Package secp256k1 implements the BIP-340 Schnorr signature scheme over the
2 // secp256k1 curve, which is what Nostr uses to sign events.
3 //
4 // The arithmetic uses math/big with Jacobian projective coordinates: no
5 // inversions are performed during scalar multiplication, only once when the
6 // final point is converted back to affine form. This keeps the code obviously
7 // correct and portable across TinyGo's supported targets. Signature
8 // verification is the hot path for a relay; the representation can be replaced
9 // with fixed-width limb arithmetic later without changing this API.
10 package secp256k1
11
12 import "math/big"
13
14 var (
15 // P is the field prime 2^256 - 2^32 - 977.
16 P = mustBig("fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f")
17 // N is the group order.
18 N = mustBig("fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141")
19
20 gx = mustBig("79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798")
21 gy = mustBig("483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8")
22 seven = big.NewInt(7)
23 // sqrtExp is (P+1)/4, the exponent that yields a square root for the
24 // p ≡ 3 (mod 4) field used by secp256k1.
25 sqrtExp = new(big.Int).Rsh(new(big.Int).Add(P, big.NewInt(1)), 2)
26 )
27
28 // G is the generator in affine coordinates.
29 var G = affine{gx, gy}
30
31 type affine struct {
32 x, y *big.Int
33 }
34
35 // point is a Jacobian projective point. Z == 0 encodes the point at infinity.
36 type point struct {
37 x, y, z *big.Int
38 }
39
40 func mustBig(s string) *big.Int {
41 v, ok := new(big.Int).SetString(s, 16)
42 if !ok {
43 panic("secp256k1: bad constant")
44 }
45 return v
46 }
47
48 func infinity() *point {
49 return &point{new(big.Int), big.NewInt(1), new(big.Int)}
50 }
51
52 func (p *point) isInfinity() bool { return p.z.Sign() == 0 }
53
54 func fromAffine(a affine) *point {
55 return &point{new(big.Int).Set(a.x), new(big.Int).Set(a.y), big.NewInt(1)}
56 }
57
58 // --- field helpers ---
59
60 func fAdd(a, b *big.Int) *big.Int {
61 z := new(big.Int).Add(a, b)
62 if z.Cmp(P) >= 0 {
63 z.Sub(z, P)
64 }
65 return z
66 }
67
68 func fSub(a, b *big.Int) *big.Int {
69 z := new(big.Int).Sub(a, b)
70 if z.Sign() < 0 {
71 z.Add(z, P)
72 }
73 return z
74 }
75
76 func fMul(a, b *big.Int) *big.Int {
77 return new(big.Int).Mod(new(big.Int).Mul(a, b), P)
78 }
79
80 func fSqr(a *big.Int) *big.Int {
81 return new(big.Int).Mod(new(big.Int).Mul(a, a), P)
82 }
83
84 func fMulSmall(a *big.Int, k int64) *big.Int {
85 z := new(big.Int).Mul(a, big.NewInt(k))
86 return z.Mod(z, P)
87 }
88
89 func fNeg(a *big.Int) *big.Int {
90 if a.Sign() == 0 {
91 return new(big.Int)
92 }
93 return new(big.Int).Sub(P, a)
94 }
95
96 // --- group operations (Jacobian, a = 0) ---
97
98 // double returns 2*a.
99 func double(a *point) *point {
100 if a.isInfinity() || a.y.Sign() == 0 {
101 return infinity()
102 }
103 A := fSqr(a.x)
104 B := fSqr(a.y)
105 C := fSqr(B)
106 xb := fAdd(a.x, B)
107 D := fSub(fSub(fSqr(xb), A), C)
108 D = fMulSmall(D, 2)
109 E := fMulSmall(A, 3)
110 F := fSqr(E)
111 x3 := fSub(F, fMulSmall(D, 2))
112 y3 := fSub(fMul(E, fSub(D, x3)), fMulSmall(C, 8))
113 z3 := fMulSmall(fMul(a.y, a.z), 2)
114 return &point{x3, y3, z3}
115 }
116
117 // add returns a+b.
118 func add(a, b *point) *point {
119 if a.isInfinity() {
120 return &point{new(big.Int).Set(b.x), new(big.Int).Set(b.y), new(big.Int).Set(b.z)}
121 }
122 if b.isInfinity() {
123 return &point{new(big.Int).Set(a.x), new(big.Int).Set(a.y), new(big.Int).Set(a.z)}
124 }
125 z1z1 := fSqr(a.z)
126 z2z2 := fSqr(b.z)
127 u1 := fMul(a.x, z2z2)
128 u2 := fMul(b.x, z1z1)
129 s1 := fMul(fMul(a.y, b.z), z2z2)
130 s2 := fMul(fMul(b.y, a.z), z1z1)
131 h := fSub(u2, u1)
132 // r carries the factor 2 that the complete addition formula requires
133 // (EFD add-2007-bl); using the raw S2-S1 makes the result order-dependent.
134 r := fMulSmall(fSub(s2, s1), 2)
135 if h.Sign() == 0 {
136 if r.Sign() == 0 {
137 return double(a)
138 }
139 return infinity()
140 }
141 i := fSqr(fMulSmall(h, 2))
142 j := fMul(h, i)
143 v := fMul(u1, i)
144 x3 := fSub(fSub(fSqr(r), j), fMulSmall(v, 2))
145 y3 := fSub(fMul(r, fSub(v, x3)), fMulSmall(fMul(s1, j), 2))
146 zsum := fAdd(a.z, b.z)
147 z3 := fMul(fSub(fSub(fSqr(zsum), z1z1), z2z2), h)
148 return &point{x3, y3, z3}
149 }
150
151 // toAffine converts a projective point. The caller must not pass infinity.
152 func toAffine(p *point) affine {
153 zinv := new(big.Int).ModInverse(p.z, P)
154 z2 := fSqr(zinv)
155 z3 := fMul(z2, zinv)
156 return affine{fMul(p.x, z2), fMul(p.y, z3)}
157 }
158
159 // scalarMult returns k*p using a 4-bit fixed window. The scalar is reduced
160 // modulo N first; a zero scalar yields infinity.
161 func scalarMult(k *big.Int, p *point) *point {
162 kk := new(big.Int).Mod(k, N)
163 if kk.Sign() == 0 || p.isInfinity() {
164 return infinity()
165 }
166 // Precompute 0*P .. 15*P.
167 var table [16]*point
168 table[0] = infinity()
169 table[1] = p
170 for i := 2; i < 16; i++ {
171 table[i] = add(table[i-1], p)
172 }
173 result := infinity()
174 // Process the scalar nibble by nibble from the most significant one.
175 byteLen := (kk.BitLen() + 7) / 8
176 buf := kk.Bytes()
177 _ = byteLen
178 for i := 0; i < len(buf); i++ {
179 hi := buf[i] >> 4
180 lo := buf[i] & 0x0f
181 result = double(double(double(double(result))))
182 if hi != 0 {
183 result = add(result, table[hi])
184 }
185 result = double(double(double(double(result))))
186 if lo != 0 {
187 result = add(result, table[lo])
188 }
189 }
190 return result
191 }
192
193 // liftX returns the affine point with the given x coordinate and even y, as
194 // BIP-340 defines public keys. It returns nil when x is not on the curve.
195 func liftX(x *big.Int) *affine {
196 if x.Sign() < 0 || x.Cmp(P) >= 0 {
197 return nil
198 }
199 c := fAdd(fMul(fSqr(x), x), seven)
200 y := new(big.Int).Exp(c, sqrtExp, P)
201 if fSqr(y).Cmp(c) != 0 {
202 return nil
203 }
204 if y.Bit(0) == 1 {
205 y = fNeg(y)
206 }
207 return &affine{new(big.Int).Set(x), y}
208 }
209