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