1 // Copyright 2020-2022 The Decred developers
2 // Use of this source code is governed by an ISC
3 // license that can be found in the LICENSE file.
4 5 package secp256k1
6 7 // References:
8 // [SECG]: Recommended Elliptic Curve Domain Parameters
9 // https://www.secg.org/sec2-v2.pdf
10 //
11 // [GECC]: Guide to Elliptic Curve Cryptography (Hankerson, Menezes, Vanstone)
12 13 import (
14 "crypto/ecdsa"
15 "crypto/elliptic"
16 "math/big"
17 )
18 19 // CurveParams contains the parameters for the secp256k1 curve.
20 type CurveParams struct {
21 // P is the prime used in the secp256k1 field.
22 P *big.Int
23 // N is the order of the secp256k1 curve group generated by the base point.
24 N *big.Int
25 // Gx and Gy are the x and y coordinate of the base point, respectively.
26 Gx, Gy *big.Int
27 // BitSize is the size of the underlying secp256k1 field in bits.
28 BitSize int
29 // H is the cofactor of the secp256k1 curve.
30 H int
31 // ByteSize is simply the bit size / 8 and is provided for convenience
32 // since it is calculated repeatedly.
33 ByteSize int
34 }
35 36 // Curve parameters taken from [SECG] section 2.4.1.
37 var curveParams = CurveParams{
38 P: fromHex("fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f"),
39 N: fromHex("fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141"),
40 Gx: fromHex("79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798"),
41 Gy: fromHex("483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8"),
42 BitSize: 256,
43 H: 1,
44 ByteSize: 256 / 8,
45 }
46 47 // Params returns the secp256k1 curve parameters for convenience.
48 func Params() *CurveParams { return &curveParams }
49 50 // KoblitzCurve provides an implementation for secp256k1 that fits the ECC Curve
51 // interface from crypto/elliptic.
52 type KoblitzCurve struct {
53 *elliptic.CurveParams
54 }
55 56 // bigAffineToJacobian takes an affine point (x, y) as big integers and converts
57 // it to Jacobian point with Z=1.
58 func bigAffineToJacobian(x, y *big.Int, result *JacobianPoint) {
59 result.X.SetByteSlice(x.Bytes())
60 result.Y.SetByteSlice(y.Bytes())
61 result.Z.SetInt(1)
62 }
63 64 // jacobianToBigAffine takes a Jacobian point (x, y, z) as field values and
65 // converts it to an affine point as big integers.
66 func jacobianToBigAffine(point *JacobianPoint) (*big.Int, *big.Int) {
67 point.ToAffine()
68 // Convert the field values for the now affine point to big.Ints.
69 x3, y3 := &big.Int{}, &big.Int{}
70 x3.SetBytes(point.X.Bytes()[:])
71 y3.SetBytes(point.Y.Bytes()[:])
72 return x3, y3
73 }
74 75 // Params returns the parameters for the curve.
76 //
77 // This is part of the elliptic.Curve interface implementation.
78 func (curve *KoblitzCurve) Params() *elliptic.CurveParams {
79 return curve.CurveParams
80 }
81 82 // IsOnCurve returns whether or not the affine point (x,y) is on the curve.
83 //
84 // This is part of the elliptic.Curve interface implementation. This function
85 // differs from the crypto/elliptic algorithm since a = 0 not -3.
86 func (curve *KoblitzCurve) IsOnCurve(x, y *big.Int) bool {
87 // Convert big ints to a Jacobian point for faster arithmetic.
88 var point JacobianPoint
89 bigAffineToJacobian(x, y, &point)
90 return isOnCurve(&point.X, &point.Y)
91 }
92 93 // Add returns the sum of (x1,y1) and (x2,y2).
94 //
95 // This is part of the elliptic.Curve interface implementation.
96 func (curve *KoblitzCurve) Add(x1, y1, x2, y2 *big.Int) (*big.Int, *big.Int) {
97 // The point at infinity is the identity according to the group law for
98 // elliptic curve cryptography. Thus, ∞ + P = P and P + ∞ = P.
99 if x1.Sign() == 0 && y1.Sign() == 0 {
100 return x2, y2
101 }
102 if x2.Sign() == 0 && y2.Sign() == 0 {
103 return x1, y1
104 }
105 // Convert the affine coordinates from big integers to Jacobian points,
106 // do the point addition in Jacobian projective space, and convert the
107 // Jacobian point back to affine big.Ints.
108 var p1, p2, result JacobianPoint
109 bigAffineToJacobian(x1, y1, &p1)
110 bigAffineToJacobian(x2, y2, &p2)
111 AddNonConst(&p1, &p2, &result)
112 return jacobianToBigAffine(&result)
113 }
114 115 // Double returns 2*(x1,y1).
116 //
117 // This is part of the elliptic.Curve interface implementation.
118 func (curve *KoblitzCurve) Double(x1, y1 *big.Int) (*big.Int, *big.Int) {
119 if y1.Sign() == 0 {
120 return &big.Int{}, &big.Int{}
121 }
122 // Convert the affine coordinates from big integers to Jacobian points,
123 // do the point doubling in Jacobian projective space, and convert the
124 // Jacobian point back to affine big.Ints.
125 var point, result JacobianPoint
126 bigAffineToJacobian(x1, y1, &point)
127 DoubleNonConst(&point, &result)
128 return jacobianToBigAffine(&result)
129 }
130 131 // moduloReduce reduces k from more than 32 bytes to 32 bytes and under. This
132 // is done by doing a simple modulo curve.N. We can do this since G^N = 1 and
133 // thus any other valid point on the elliptic curve has the same order.
134 func moduloReduce(k []byte) []byte {
135 // Since the order of G is curve.N, we can use a much smaller number by
136 // doing modulo curve.N
137 if len(k) > curveParams.ByteSize {
138 tmpK := (&big.Int{}).SetBytes(k)
139 tmpK.Mod(tmpK, curveParams.N)
140 return tmpK.Bytes()
141 }
142 return k
143 }
144 145 // ScalarMult returns k*(Bx, By) where k is a big endian integer.
146 //
147 // This is part of the elliptic.Curve interface implementation.
148 func (curve *KoblitzCurve) ScalarMult(Bx, By *big.Int, k []byte) (
149 *big.Int,
150 *big.Int,
151 ) {
152 // Convert the affine coordinates from big integers to Jacobian points,
153 // do the multiplication in Jacobian projective space, and convert the
154 // Jacobian point back to affine big.Ints.
155 var kModN ModNScalar
156 kModN.SetByteSlice(moduloReduce(k))
157 var point, result JacobianPoint
158 bigAffineToJacobian(Bx, By, &point)
159 ScalarMultNonConst(&kModN, &point, &result)
160 return jacobianToBigAffine(&result)
161 }
162 163 // ScalarBaseMult returns k*G where G is the base point of the group and k is a
164 // big endian integer.
165 //
166 // This is part of the elliptic.Curve interface implementation.
167 func (curve *KoblitzCurve) ScalarBaseMult(k []byte) (*big.Int, *big.Int) {
168 // Perform the multiplication and convert the Jacobian point back to affine
169 // big.Ints.
170 var kModN ModNScalar
171 kModN.SetByteSlice(moduloReduce(k))
172 var result JacobianPoint
173 ScalarBaseMultNonConst(&kModN, &result)
174 return jacobianToBigAffine(&result)
175 }
176 177 // X returns the x coordinate of the public key.
178 func (p *PublicKey) X() *big.Int {
179 return (&big.Int{}).SetBytes(p.x.Bytes()[:])
180 }
181 182 // Y returns the y coordinate of the public key.
183 func (p *PublicKey) Y() *big.Int {
184 return (&big.Int{}).SetBytes(p.y.Bytes()[:])
185 }
186 187 // ToECDSA returns the public key as a *ecdsa.PublicKey.
188 func (p *PublicKey) ToECDSA() *ecdsa.PublicKey {
189 return &ecdsa.PublicKey{
190 Curve: S256(),
191 X: p.X(),
192 Y: p.Y(),
193 }
194 }
195 196 // ToECDSA returns the secret key as a *ecdsa.SecretKey.
197 func (p *SecretKey) ToECDSA() *ecdsa.PrivateKey {
198 var secretKeyBytes [SecKeyBytesLen]byte
199 p.Key.PutBytes(&secretKeyBytes)
200 var result JacobianPoint
201 ScalarBaseMultNonConst(&p.Key, &result)
202 x, y := jacobianToBigAffine(&result)
203 newSecKey := &ecdsa.PrivateKey{
204 PublicKey: ecdsa.PublicKey{
205 Curve: S256(),
206 X: x,
207 Y: y,
208 },
209 D: (&big.Int{}).SetBytes(secretKeyBytes[:]),
210 }
211 zeroArray32(&secretKeyBytes)
212 return newSecKey
213 }
214 215 // fromHex converts the passed hex string into a big integer pointer and will
216 // panic is there is an error. This is only provided for the hard-coded
217 // constants so errors in the source code can bet detected. It will only (and
218 // must only) be called for initialization purposes.
219 func fromHex(s string) *big.Int {
220 if s == "" {
221 return big.NewInt(0)
222 }
223 r, ok := (&big.Int{}).SetString(s, 16)
224 if !ok {
225 panic("invalid hex in source file: " + s)
226 }
227 return r
228 }
229 230 // secp256k1 is a global instance of the KoblitzCurve implementation which in
231 // turn embeds and implements elliptic.CurveParams.
232 var secp256k1 = &KoblitzCurve{
233 CurveParams: &elliptic.CurveParams{
234 P: curveParams.P,
235 N: curveParams.N,
236 B: fromHex("0000000000000000000000000000000000000000000000000000000000000007"),
237 Gx: curveParams.Gx,
238 Gy: curveParams.Gy,
239 BitSize: curveParams.BitSize,
240 Name: "secp256k1",
241 },
242 }
243 244 // S256 returns an elliptic.Curve which implements secp256k1.
245 func S256() *KoblitzCurve {
246 return secp256k1
247 }
248