1 // Copyright (c) 2013-2014 The btcsuite 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 ecc
6 7 import (
8 "crypto/ecdsa"
9 "errors"
10 "fmt"
11 "math/big"
12 )
13 14 // These constants define the lengths of serialized public keys.
15 const (
16 PubKeyBytesLenCompressed = 33
17 PubKeyBytesLenUncompressed = 65
18 PubKeyBytesLenHybrid = 65
19 )
20 21 func isOdd(a *big.Int) bool {
22 return a.Bit(0) == 1
23 }
24 25 // decompressPoint decompresses a point on the secp256k1 curve given the X point and
26 // the solution to use.
27 func decompressPoint(curve *KoblitzCurve, bigX *big.Int, ybit bool) (*big.Int, error) {
28 var x fieldVal
29 x.SetByteSlice(bigX.Bytes())
30 31 // Compute x^3 + B mod p.
32 var x3 fieldVal
33 x3.SquareVal(&x).Mul(&x)
34 x3.Add(curve.fieldB).Normalize()
35 36 // Now calculate sqrt mod p of x^3 + B
37 // This code used to do a full sqrt based on tonelli/shanks,
38 // but this was replaced by the algorithms referenced in
39 // https://bitcointalk.org/index.php?topic=162805.msg1712294#msg1712294
40 var y fieldVal
41 y.SqrtVal(&x3).Normalize()
42 if ybit != y.IsOdd() {
43 y.Negate(1).Normalize()
44 }
45 46 // Check that y is a square root of x^3 + B.
47 var y2 fieldVal
48 y2.SquareVal(&y).Normalize()
49 if !y2.Equals(&x3) {
50 return nil, fmt.Errorf("invalid square root")
51 }
52 53 // Verify that y-coord has expected parity.
54 if ybit != y.IsOdd() {
55 return nil, fmt.Errorf("ybit doesn't match oddness")
56 }
57 58 return new(big.Int).SetBytes(y.Bytes()[:]), nil
59 }
60 61 const (
62 pubkeyCompressed byte = 0x2 // y_bit + x coord
63 pubkeyUncompressed byte = 0x4 // x coord + y coord
64 pubkeyHybrid byte = 0x6 // y_bit + x coord + y coord
65 )
66 67 // IsCompressedPubKey returns true the the passed serialized public key has
68 // been encoded in compressed format, and false otherwise.
69 func IsCompressedPubKey(pubKey []byte) bool {
70 // The public key is only compressed if it is the correct length and
71 // the format (first byte) is one of the compressed pubkey values.
72 return len(pubKey) == PubKeyBytesLenCompressed &&
73 (pubKey[0]&^byte(0x1) == pubkeyCompressed)
74 }
75 76 // ParsePubKey parses a public key for a koblitz curve from a bytestring into a
77 // ecdsa.Publickey, verifying that it is valid. It supports compressed,
78 // uncompressed and hybrid signature formats.
79 func ParsePubKey(pubKeyStr []byte, curve *KoblitzCurve) (key *PublicKey, err error) {
80 pubkey := PublicKey{}
81 pubkey.Curve = curve
82 83 if len(pubKeyStr) == 0 {
84 return nil, errors.New("pubkey string is empty")
85 }
86 87 format := pubKeyStr[0]
88 ybit := (format & 0x1) == 0x1
89 format &= ^byte(0x1)
90 91 switch len(pubKeyStr) {
92 case PubKeyBytesLenUncompressed:
93 if format != pubkeyUncompressed && format != pubkeyHybrid {
94 return nil, fmt.Errorf("invalid magic in pubkey str: "+
95 "%d", pubKeyStr[0])
96 }
97 98 pubkey.X = new(big.Int).SetBytes(pubKeyStr[1:33])
99 pubkey.Y = new(big.Int).SetBytes(pubKeyStr[33:])
100 // hybrid keys have extra information, make use of it.
101 if format == pubkeyHybrid && ybit != isOdd(pubkey.Y) {
102 return nil, fmt.Errorf("ybit doesn't match oddness")
103 }
104 105 if pubkey.X.Cmp(pubkey.Curve.Params().P) >= 0 {
106 return nil, fmt.Errorf("pubkey X parameter is >= to P")
107 }
108 if pubkey.Y.Cmp(pubkey.Curve.Params().P) >= 0 {
109 return nil, fmt.Errorf("pubkey Y parameter is >= to P")
110 }
111 if !pubkey.Curve.IsOnCurve(pubkey.X, pubkey.Y) {
112 return nil, fmt.Errorf("pubkey isn't on secp256k1 curve")
113 }
114 115 case PubKeyBytesLenCompressed:
116 // format is 0x2 | solution, <X coordinate>
117 // solution determines which solution of the curve we use.
118 /// y^2 = x^3 + Curve.B
119 if format != pubkeyCompressed {
120 return nil, fmt.Errorf("invalid magic in compressed "+
121 "pubkey string: %d", pubKeyStr[0])
122 }
123 pubkey.X = new(big.Int).SetBytes(pubKeyStr[1:33])
124 pubkey.Y, err = decompressPoint(curve, pubkey.X, ybit)
125 if err != nil {
126 return nil, err
127 }
128 129 default: // wrong!
130 return nil, fmt.Errorf("invalid pub key length %d",
131 len(pubKeyStr))
132 }
133 134 return &pubkey, nil
135 }
136 137 // PublicKey is an ecdsa.PublicKey with additional functions to
138 // serialize in uncompressed, compressed, and hybrid formats.
139 type PublicKey ecdsa.PublicKey
140 141 // ToECDSA returns the public key as a *ecdsa.PublicKey.
142 func (p *PublicKey) ToECDSA() *ecdsa.PublicKey {
143 return (*ecdsa.PublicKey)(p)
144 }
145 146 // SerializeUncompressed serializes a public key in a 65-byte uncompressed
147 // format.
148 func (p *PublicKey) SerializeUncompressed() []byte {
149 b := make([]byte, 0, PubKeyBytesLenUncompressed)
150 b = append(b, pubkeyUncompressed)
151 b = paddedAppend(32, b, p.X.Bytes())
152 return paddedAppend(32, b, p.Y.Bytes())
153 }
154 155 // SerializeCompressed serializes a public key in a 33-byte compressed format.
156 func (p *PublicKey) SerializeCompressed() []byte {
157 b := make([]byte, 0, PubKeyBytesLenCompressed)
158 format := pubkeyCompressed
159 if isOdd(p.Y) {
160 format |= 0x1
161 }
162 b = append(b, format)
163 return paddedAppend(32, b, p.X.Bytes())
164 }
165 166 // SerializeHybrid serializes a public key in a 65-byte hybrid format.
167 func (p *PublicKey) SerializeHybrid() []byte {
168 b := make([]byte, 0, PubKeyBytesLenHybrid)
169 format := pubkeyHybrid
170 if isOdd(p.Y) {
171 format |= 0x1
172 }
173 b = append(b, format)
174 b = paddedAppend(32, b, p.X.Bytes())
175 return paddedAppend(32, b, p.Y.Bytes())
176 }
177 178 // IsEqual compares this PublicKey instance to the one passed, returning true if
179 // both PublicKeys are equivalent. A PublicKey is equivalent to another, if they
180 // both have the same X and Y coordinate.
181 func (p *PublicKey) IsEqual(otherPubKey *PublicKey) bool {
182 return p.X.Cmp(otherPubKey.X) == 0 &&
183 p.Y.Cmp(otherPubKey.Y) == 0
184 }
185 186 // paddedAppend appends the src byte slice to dst, returning the new slice.
187 // If the length of the source is smaller than the passed size, leading zero
188 // bytes are appended to the dst slice before appending src.
189 func paddedAppend(size uint, dst, src []byte) []byte {
190 for i := 0; i < int(size)-len(src); i++ {
191 dst = append(dst, 0)
192 }
193 return append(dst, src...)
194 }
195