1 // Copyright (c) 2013-2017 The btcsuite developers
2 // Copyright (c) 2015-2021 The Decred developers
3 // Use of this source code is governed by an ISC
4 // license that can be found in the LICENSE file.
5 6 package ecdsa
7 8 import (
9 "errors"
10 "fmt"
11 "math/big"
12 13 "github.com/btcsuite/btcd/btcec/v2"
14 secp_ecdsa "github.com/decred/dcrd/dcrec/secp256k1/v4/ecdsa"
15 )
16 17 // Errors returned by canonicalPadding.
18 var (
19 errNegativeValue = errors.New("value may be interpreted as negative")
20 errExcessivelyPaddedValue = errors.New("value is excessively padded")
21 )
22 23 // Signature is a type representing an ecdsa signature.
24 type Signature = secp_ecdsa.Signature
25 26 // NewSignature instantiates a new signature given some r and s values.
27 func NewSignature(r, s *btcec.ModNScalar) *Signature {
28 return secp_ecdsa.NewSignature(r, s)
29 }
30 31 var (
32 // Used in RFC6979 implementation when testing the nonce for correctness
33 one = big.NewInt(1)
34 35 // oneInitializer is used to fill a byte slice with byte 0x01. It is provided
36 // here to avoid the need to create it multiple times.
37 oneInitializer = []byte{0x01}
38 )
39 40 const (
41 // MinSigLen is the minimum length of a DER encoded signature and is when both R
42 // and S are 1 byte each.
43 // 0x30 + <1-byte> + 0x02 + 0x01 + <byte> + 0x2 + 0x01 + <byte>
44 MinSigLen = 8
45 46 // MaxSigLen is the maximum length of a DER encoded signature and is
47 // when both R and S are 33 bytes each. It is 33 bytes because a
48 // 256-bit integer requires 32 bytes and an additional leading null byte
49 // might be required if the high bit is set in the value.
50 //
51 // 0x30 + <1-byte> + 0x02 + 0x21 + <33 bytes> + 0x2 + 0x21 + <33 bytes>
52 MaxSigLen = 72
53 )
54 55 // canonicalPadding checks whether a big-endian encoded integer could
56 // possibly be misinterpreted as a negative number (even though OpenSSL
57 // treats all numbers as unsigned), or if there is any unnecessary
58 // leading zero padding.
59 func canonicalPadding(b []byte) error {
60 switch {
61 case b[0]&0x80 == 0x80:
62 return errNegativeValue
63 case len(b) > 1 && b[0] == 0x00 && b[1]&0x80 != 0x80:
64 return errExcessivelyPaddedValue
65 default:
66 return nil
67 }
68 }
69 70 func parseSig(sigStr []byte, der bool) (*Signature, error) {
71 // Originally this code used encoding/asn1 in order to parse the
72 // signature, but a number of problems were found with this approach.
73 // Despite the fact that signatures are stored as DER, the difference
74 // between go's idea of a bignum (and that they have sign) doesn't agree
75 // with the openssl one (where they do not). The above is true as of
76 // Go 1.1. In the end it was simpler to rewrite the code to explicitly
77 // understand the format which is this:
78 // 0x30 <length of whole message> <0x02> <length of R> <R> 0x2
79 // <length of S> <S>.
80 81 // The signature must adhere to the minimum and maximum allowed length.
82 totalSigLen := len(sigStr)
83 if totalSigLen < MinSigLen {
84 return nil, errors.New("malformed signature: too short")
85 }
86 if der && totalSigLen > MaxSigLen {
87 return nil, errors.New("malformed signature: too long")
88 }
89 90 // 0x30
91 index := 0
92 if sigStr[index] != 0x30 {
93 return nil, errors.New("malformed signature: no header magic")
94 }
95 index++
96 // length of remaining message
97 siglen := sigStr[index]
98 index++
99 100 // siglen should be less than the entire message and greater than
101 // the minimal message size.
102 if int(siglen+2) > len(sigStr) || int(siglen+2) < MinSigLen {
103 return nil, errors.New("malformed signature: bad length")
104 }
105 // trim the slice we're working on so we only look at what matters.
106 sigStr = sigStr[:siglen+2]
107 108 // 0x02
109 if sigStr[index] != 0x02 {
110 return nil,
111 errors.New("malformed signature: no 1st int marker")
112 }
113 index++
114 115 // Length of signature R.
116 rLen := int(sigStr[index])
117 // must be positive, must be able to fit in another 0x2, <len> <s>
118 // hence the -3. We assume that the length must be at least one byte.
119 index++
120 if rLen <= 0 || rLen > len(sigStr)-index-3 {
121 return nil, errors.New("malformed signature: bogus R length")
122 }
123 124 // Then R itself.
125 rBytes := sigStr[index : index+rLen]
126 if der {
127 switch err := canonicalPadding(rBytes); err {
128 case errNegativeValue:
129 return nil, errors.New("signature R is negative")
130 case errExcessivelyPaddedValue:
131 return nil, errors.New("signature R is excessively padded")
132 }
133 }
134 135 // Strip leading zeroes from R.
136 for len(rBytes) > 0 && rBytes[0] == 0x00 {
137 rBytes = rBytes[1:]
138 }
139 140 // R must be in the range [1, N-1]. Notice the check for the maximum number
141 // of bytes is required because SetByteSlice truncates as noted in its
142 // comment so it could otherwise fail to detect the overflow.
143 var r btcec.ModNScalar
144 if len(rBytes) > 32 {
145 str := "invalid signature: R is larger than 256 bits"
146 return nil, errors.New(str)
147 }
148 if overflow := r.SetByteSlice(rBytes); overflow {
149 str := "invalid signature: R >= group order"
150 return nil, errors.New(str)
151 }
152 if r.IsZero() {
153 str := "invalid signature: R is 0"
154 return nil, errors.New(str)
155 }
156 index += rLen
157 // 0x02. length already checked in previous if.
158 if sigStr[index] != 0x02 {
159 return nil, errors.New("malformed signature: no 2nd int marker")
160 }
161 index++
162 163 // Length of signature S.
164 sLen := int(sigStr[index])
165 index++
166 // S should be the rest of the string.
167 if sLen <= 0 || sLen > len(sigStr)-index {
168 return nil, errors.New("malformed signature: bogus S length")
169 }
170 171 // Then S itself.
172 sBytes := sigStr[index : index+sLen]
173 if der {
174 switch err := canonicalPadding(sBytes); err {
175 case errNegativeValue:
176 return nil, errors.New("signature S is negative")
177 case errExcessivelyPaddedValue:
178 return nil, errors.New("signature S is excessively padded")
179 }
180 }
181 182 // Strip leading zeroes from S.
183 for len(sBytes) > 0 && sBytes[0] == 0x00 {
184 sBytes = sBytes[1:]
185 }
186 187 // S must be in the range [1, N-1]. Notice the check for the maximum number
188 // of bytes is required because SetByteSlice truncates as noted in its
189 // comment so it could otherwise fail to detect the overflow.
190 var s btcec.ModNScalar
191 if len(sBytes) > 32 {
192 str := "invalid signature: S is larger than 256 bits"
193 return nil, errors.New(str)
194 }
195 if overflow := s.SetByteSlice(sBytes); overflow {
196 str := "invalid signature: S >= group order"
197 return nil, errors.New(str)
198 }
199 if s.IsZero() {
200 str := "invalid signature: S is 0"
201 return nil, errors.New(str)
202 }
203 index += sLen
204 205 // sanity check length parsing
206 if index != len(sigStr) {
207 return nil, fmt.Errorf("malformed signature: bad final length %v != %v",
208 index, len(sigStr))
209 }
210 211 return NewSignature(&r, &s), nil
212 }
213 214 // ParseSignature parses a signature in BER format for the curve type `curve'
215 // into a Signature type, performing some basic sanity checks. If parsing
216 // according to the more strict DER format is needed, use ParseDERSignature.
217 func ParseSignature(sigStr []byte) (*Signature, error) {
218 return parseSig(sigStr, false)
219 }
220 221 // ParseDERSignature parses a signature in DER format for the curve type
222 // `curve` into a Signature type. If parsing according to the less strict
223 // BER format is needed, use ParseSignature.
224 func ParseDERSignature(sigStr []byte) (*Signature, error) {
225 return parseSig(sigStr, true)
226 }
227 228 // SignCompact produces a compact signature of the data in hash with the given
229 // private key on the given koblitz curve. The isCompressed parameter should
230 // be used to detail if the given signature should reference a compressed
231 // public key or not. If successful the bytes of the compact signature will be
232 // returned in the format:
233 // <(byte of 27+public key solution)+4 if compressed >< padded bytes for signature R><padded bytes for signature S>
234 // where the R and S parameters are padde up to the bitlengh of the curve.
235 func SignCompact(key *btcec.PrivateKey, hash []byte,
236 isCompressedKey bool) []byte {
237 238 return secp_ecdsa.SignCompact(key, hash, isCompressedKey)
239 }
240 241 // RecoverCompact verifies the compact signature "signature" of "hash" for the
242 // Koblitz curve in "curve". If the signature matches then the recovered public
243 // key will be returned as well as a boolean if the original key was compressed
244 // or not, else an error will be returned.
245 func RecoverCompact(signature, hash []byte) (*btcec.PublicKey, bool, error) {
246 return secp_ecdsa.RecoverCompact(signature, hash)
247 }
248 249 // Sign generates an ECDSA signature over the secp256k1 curve for the provided
250 // hash (which should be the result of hashing a larger message) using the
251 // given private key. The produced signature is deterministic (same message and
252 // same key yield the same signature) and canonical in accordance with RFC6979
253 // and BIP0062.
254 func Sign(key *btcec.PrivateKey, hash []byte) *Signature {
255 return secp_ecdsa.Sign(key, hash)
256 }
257