1 // Copyright (c) 2013-2017 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 "bytes"
9 "crypto/ecdsa"
10 "crypto/elliptic"
11 "crypto/hmac"
12 "crypto/sha256"
13 "errors"
14 "fmt"
15 "hash"
16 "math/big"
17 )
18 19 // Errors returned by canonicalPadding.
20 var (
21 errNegativeValue = errors.New("value may be interpreted as negative")
22 errExcessivelyPaddedValue = errors.New("value is excessively padded")
23 )
24 25 // Signature is a type representing an ecdsa signature.
26 type Signature struct {
27 R *big.Int
28 S *big.Int
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 // Serialize returns the ECDSA signature in the more strict DER format. Note
41 // that the serialized bytes returned do not include the appended hash type
42 // used in Bitcoin signature scripts.
43 //
44 // encoding/asn1 is broken so we hand roll this output:
45 //
46 // 0x30 <length> 0x02 <length r> r 0x02 <length s> s
47 func (sig *Signature) Serialize() []byte {
48 // low 'S' malleability breaker
49 sigS := sig.S
50 if sigS.Cmp(S256().halfOrder) == 1 {
51 sigS = new(big.Int).Sub(S256().N, sigS)
52 }
53 // Ensure the encoded bytes for the r and s values are canonical and
54 // thus suitable for DER encoding.
55 rb := canonicalizeInt(sig.R)
56 sb := canonicalizeInt(sigS)
57 58 // total length of returned signature is 1 byte for each magic and
59 // length (6 total), plus lengths of r and s
60 length := 6 + len(rb) + len(sb)
61 b := make([]byte, length)
62 63 b[0] = 0x30
64 b[1] = byte(length - 2)
65 b[2] = 0x02
66 b[3] = byte(len(rb))
67 offset := copy(b[4:], rb) + 4
68 b[offset] = 0x02
69 b[offset+1] = byte(len(sb))
70 copy(b[offset+2:], sb)
71 return b
72 }
73 74 // Verify calls ecdsa.Verify to verify the signature of hash using the public
75 // key. It returns true if the signature is valid, false otherwise.
76 func (sig *Signature) Verify(hash []byte, pubKey *PublicKey) bool {
77 return ecdsa.Verify(pubKey.ToECDSA(), hash, sig.R, sig.S)
78 }
79 80 // IsEqual compares this Signature instance to the one passed, returning true
81 // if both Signatures are equivalent. A signature is equivalent to another, if
82 // they both have the same scalar value for R and S.
83 func (sig *Signature) IsEqual(otherSig *Signature) bool {
84 return sig.R.Cmp(otherSig.R) == 0 &&
85 sig.S.Cmp(otherSig.S) == 0
86 }
87 88 // MinSigLen is the minimum length of a DER encoded signature and is when both R
89 // and S are 1 byte each.
90 // 0x30 + <1-byte> + 0x02 + 0x01 + <byte> + 0x2 + 0x01 + <byte>
91 const MinSigLen = 8
92 93 func parseSig(sigStr []byte, curve elliptic.Curve, der bool) (*Signature, error) {
94 // Originally this code used encoding/asn1 in order to parse the
95 // signature, but a number of problems were found with this approach.
96 // Despite the fact that signatures are stored as DER, the difference
97 // between go's idea of a bignum (and that they have sign) doesn't agree
98 // with the openssl one (where they do not). The above is true as of
99 // Go 1.1. In the end it was simpler to rewrite the code to explicitly
100 // understand the format which is this:
101 // 0x30 <length of whole message> <0x02> <length of R> <R> 0x2
102 // <length of S> <S>.
103 104 signature := &Signature{}
105 106 if len(sigStr) < MinSigLen {
107 return nil, errors.New("malformed signature: too short")
108 }
109 // 0x30
110 index := 0
111 if sigStr[index] != 0x30 {
112 return nil, errors.New("malformed signature: no header magic")
113 }
114 index++
115 // length of remaining message
116 siglen := sigStr[index]
117 index++
118 119 // siglen should be less than the entire message and greater than
120 // the minimal message size.
121 if int(siglen+2) > len(sigStr) || int(siglen+2) < MinSigLen {
122 return nil, errors.New("malformed signature: bad length")
123 }
124 // trim the slice we're working on so we only look at what matters.
125 sigStr = sigStr[:siglen+2]
126 127 // 0x02
128 if sigStr[index] != 0x02 {
129 return nil,
130 errors.New("malformed signature: no 1st int marker")
131 }
132 index++
133 134 // Length of signature R.
135 rLen := int(sigStr[index])
136 // must be positive, must be able to fit in another 0x2, <len> <s>
137 // hence the -3. We assume that the length must be at least one byte.
138 index++
139 if rLen <= 0 || rLen > len(sigStr)-index-3 {
140 return nil, errors.New("malformed signature: bogus R length")
141 }
142 143 // Then R itself.
144 rBytes := sigStr[index : index+rLen]
145 if der {
146 switch err := canonicalPadding(rBytes); err {
147 case errNegativeValue:
148 return nil, errors.New("signature R is negative")
149 case errExcessivelyPaddedValue:
150 return nil, errors.New("signature R is excessively padded")
151 }
152 }
153 signature.R = new(big.Int).SetBytes(rBytes)
154 index += rLen
155 // 0x02. length already checked in previous if.
156 if sigStr[index] != 0x02 {
157 return nil, errors.New("malformed signature: no 2nd int marker")
158 }
159 index++
160 161 // Length of signature S.
162 sLen := int(sigStr[index])
163 index++
164 // S should be the rest of the string.
165 if sLen <= 0 || sLen > len(sigStr)-index {
166 return nil, errors.New("malformed signature: bogus S length")
167 }
168 169 // Then S itself.
170 sBytes := sigStr[index : index+sLen]
171 if der {
172 switch err := canonicalPadding(sBytes); err {
173 case errNegativeValue:
174 return nil, errors.New("signature S is negative")
175 case errExcessivelyPaddedValue:
176 return nil, errors.New("signature S is excessively padded")
177 }
178 }
179 signature.S = new(big.Int).SetBytes(sBytes)
180 index += sLen
181 182 // sanity check length parsing
183 if index != len(sigStr) {
184 return nil, fmt.Errorf("malformed signature: bad final length %v != %v",
185 index, len(sigStr))
186 }
187 188 // Verify also checks this, but we can be more sure that we parsed
189 // correctly if we verify here too.
190 // FWIW the ecdsa spec states that R and S must be | 1, N - 1 |
191 // but crypto/ecdsa only checks for Sign != 0. Mirror that.
192 if signature.R.Sign() != 1 {
193 return nil, errors.New("signature R isn't 1 or more")
194 }
195 if signature.S.Sign() != 1 {
196 return nil, errors.New("signature S isn't 1 or more")
197 }
198 if signature.R.Cmp(curve.Params().N) >= 0 {
199 return nil, errors.New("signature R is >= curve.N")
200 }
201 if signature.S.Cmp(curve.Params().N) >= 0 {
202 return nil, errors.New("signature S is >= curve.N")
203 }
204 205 return signature, nil
206 }
207 208 // ParseSignature parses a signature in BER format for the curve type `curve'
209 // into a Signature type, perfoming some basic sanity checks. If parsing
210 // according to the more strict DER format is needed, use ParseDERSignature.
211 func ParseSignature(sigStr []byte, curve elliptic.Curve) (*Signature, error) {
212 return parseSig(sigStr, curve, false)
213 }
214 215 // ParseDERSignature parses a signature in DER format for the curve type
216 // `curve` into a Signature type. If parsing according to the less strict
217 // BER format is needed, use ParseSignature.
218 func ParseDERSignature(sigStr []byte, curve elliptic.Curve) (*Signature, error) {
219 return parseSig(sigStr, curve, true)
220 }
221 222 // canonicalizeInt returns the bytes for the passed big integer adjusted as
223 // necessary to ensure that a big-endian encoded integer can't possibly be
224 // misinterpreted as a negative number. This can happen when the most
225 // significant bit is set, so it is padded by a leading zero byte in this case.
226 // Also, the returned bytes will have at least a single byte when the passed
227 // value is 0. This is required for DER encoding.
228 func canonicalizeInt(val *big.Int) []byte {
229 b := val.Bytes()
230 if len(b) == 0 {
231 b = []byte{0x00}
232 }
233 if b[0]&0x80 != 0 {
234 paddedBytes := make([]byte, len(b)+1)
235 copy(paddedBytes[1:], b)
236 b = paddedBytes
237 }
238 return b
239 }
240 241 // canonicalPadding checks whether a big-endian encoded integer could
242 // possibly be misinterpreted as a negative number (even though OpenSSL
243 // treats all numbers as unsigned), or if there is any unnecessary
244 // leading zero padding.
245 func canonicalPadding(b []byte) error {
246 switch {
247 case b[0]&0x80 == 0x80:
248 return errNegativeValue
249 case len(b) > 1 && b[0] == 0x00 && b[1]&0x80 != 0x80:
250 return errExcessivelyPaddedValue
251 default:
252 return nil
253 }
254 }
255 256 // hashToInt converts a hash value to an integer. There is some disagreement
257 // about how this is done. [NSA] suggests that this is done in the obvious
258 // manner, but [SECG] truncates the hash to the bit-length of the curve order
259 // first. We follow [SECG] because that's what OpenSSL does. Additionally,
260 // OpenSSL right shifts excess bits from the number if the hash is too large
261 // and we mirror that too.
262 // This is borrowed from crypto/ecdsa.
263 func hashToInt(hash []byte, c elliptic.Curve) *big.Int {
264 orderBits := c.Params().N.BitLen()
265 orderBytes := (orderBits + 7) / 8
266 if len(hash) > orderBytes {
267 hash = hash[:orderBytes]
268 }
269 270 ret := new(big.Int).SetBytes(hash)
271 excess := len(hash)*8 - orderBits
272 if excess > 0 {
273 ret.Rsh(ret, uint(excess))
274 }
275 return ret
276 }
277 278 // recoverKeyFromSignature recovers a public key from the signature "sig" on the
279 // given message hash "msg". Based on the algorithm found in section 4.1.6 of
280 // SEC 1 Ver 2.0, page 47-48 (53 and 54 in the pdf). This performs the details
281 // in the inner loop in Step 1. The counter provided is actually the j parameter
282 // of the loop * 2 - on the first iteration of j we do the R case, else the -R
283 // case in step 1.6. This counter is used in the bitcoin compressed signature
284 // format and thus we match bitcoind's behaviour here.
285 func recoverKeyFromSignature(curve *KoblitzCurve, sig *Signature, msg []byte,
286 iter int, doChecks bool) (*PublicKey, error) {
287 // Parse and validate the R and S signature components.
288 //
289 // Fail if r and s are not in [1, N-1].
290 if sig.R.Cmp(curve.Params().N) != -1 {
291 return nil, errors.New("signature R is >= curve order")
292 }
293 294 if sig.R.Sign() == 0 {
295 return nil, errors.New("signature R is 0")
296 }
297 298 if sig.S.Cmp(curve.Params().N) != -1 {
299 return nil, errors.New("signature S is >= curve order")
300 }
301 302 if sig.S.Sign() == 0 {
303 return nil, errors.New("signature S is 0")
304 }
305 306 // 1.1 x = (n * i) + r
307 Rx := new(big.Int).Mul(curve.Params().N,
308 new(big.Int).SetInt64(int64(iter/2)))
309 Rx.Add(Rx, sig.R)
310 if Rx.Cmp(curve.Params().P) != -1 {
311 return nil, errors.New("calculated Rx is larger than curve P")
312 }
313 314 // convert 02<Rx> to point R. (step 1.2 and 1.3). If we are on an odd
315 // iteration then 1.6 will be done with -R, so we calculate the other
316 // term when uncompressing the point.
317 Ry, err := decompressPoint(curve, Rx, iter%2 == 1)
318 if err != nil {
319 return nil, err
320 }
321 322 // 1.4 Check n*R is point at infinity
323 if doChecks {
324 nRx, nRy := curve.ScalarMult(Rx, Ry, curve.Params().N.Bytes())
325 if nRx.Sign() != 0 || nRy.Sign() != 0 {
326 return nil, errors.New("n*R does not equal the point at infinity")
327 }
328 }
329 330 // 1.5 calculate e from message using the same algorithm as ecdsa
331 // signature calculation.
332 e := hashToInt(msg, curve)
333 334 // Step 1.6.1:
335 // We calculate the two terms sR and eG separately multiplied by the
336 // inverse of r (from the signature). We then add them to calculate
337 // Q = r^-1(sR-eG)
338 invr := new(big.Int).ModInverse(sig.R, curve.Params().N)
339 340 // first term.
341 invrS := new(big.Int).Mul(invr, sig.S)
342 invrS.Mod(invrS, curve.Params().N)
343 sRx, sRy := curve.ScalarMult(Rx, Ry, invrS.Bytes())
344 345 // second term.
346 e.Neg(e)
347 e.Mod(e, curve.Params().N)
348 e.Mul(e, invr)
349 e.Mod(e, curve.Params().N)
350 minuseGx, minuseGy := curve.ScalarBaseMult(e.Bytes())
351 352 // TODO: this would be faster if we did a mult and add in one
353 // step to prevent the jacobian conversion back and forth.
354 Qx, Qy := curve.Add(sRx, sRy, minuseGx, minuseGy)
355 356 return &PublicKey{
357 Curve: curve,
358 X: Qx,
359 Y: Qy,
360 }, nil
361 }
362 363 // SignCompact produces a compact signature of the data in hash with the given
364 // private key on the given koblitz curve. The isCompressed parameter should
365 // be used to detail if the given signature should reference a compressed
366 // public key or not. If successful the bytes of the compact signature will be
367 // returned in the format:
368 // <(byte of 27+public key solution)+4 if compressed >< padded bytes for signature R><padded bytes for signature S>
369 // where the R and S parameters are padde up to the bitlengh of the curve.
370 func SignCompact(curve *KoblitzCurve, key *PrivateKey,
371 hash []byte, isCompressedKey bool) ([]byte, error) {
372 sig, err := key.Sign(hash)
373 if err != nil {
374 return nil, err
375 }
376 377 // bitcoind checks the bit length of R and S here. The ecdsa signature
378 // algorithm returns R and S mod N therefore they will be the bitsize of
379 // the curve, and thus correctly sized.
380 for i := 0; i < (curve.H+1)*2; i++ {
381 pk, err := recoverKeyFromSignature(curve, sig, hash, i, true)
382 if err == nil && pk.X.Cmp(key.X) == 0 && pk.Y.Cmp(key.Y) == 0 {
383 result := make([]byte, 1, 2*curve.byteSize+1)
384 result[0] = 27 + byte(i)
385 if isCompressedKey {
386 result[0] += 4
387 }
388 // Not sure this needs rounding but safer to do so.
389 curvelen := (curve.BitSize + 7) / 8
390 391 // Pad R and S to curvelen if needed.
392 bytelen := (sig.R.BitLen() + 7) / 8
393 if bytelen < curvelen {
394 result = append(result,
395 make([]byte, curvelen-bytelen)...)
396 }
397 result = append(result, sig.R.Bytes()...)
398 399 bytelen = (sig.S.BitLen() + 7) / 8
400 if bytelen < curvelen {
401 result = append(result,
402 make([]byte, curvelen-bytelen)...)
403 }
404 result = append(result, sig.S.Bytes()...)
405 406 return result, nil
407 }
408 }
409 410 return nil, errors.New("no valid solution for pubkey found")
411 }
412 413 // RecoverCompact verifies the compact signature "signature" of "hash" for the
414 // Koblitz curve in "curve". If the signature matches then the recovered public
415 // key will be returned as well as a boolean if the original key was compressed
416 // or not, else an error will be returned.
417 func RecoverCompact(curve *KoblitzCurve, signature,
418 hash []byte) (*PublicKey, bool, error) {
419 bitlen := (curve.BitSize + 7) / 8
420 if len(signature) != 1+bitlen*2 {
421 return nil, false, errors.New("invalid compact signature size")
422 }
423 424 iteration := int((signature[0] - 27) & ^byte(4))
425 426 // format is <header byte><bitlen R><bitlen S>
427 sig := &Signature{
428 R: new(big.Int).SetBytes(signature[1 : bitlen+1]),
429 S: new(big.Int).SetBytes(signature[bitlen+1:]),
430 }
431 // The iteration used here was encoded
432 key, err := recoverKeyFromSignature(curve, sig, hash, iteration, false)
433 if err != nil {
434 return nil, false, err
435 }
436 437 return key, ((signature[0] - 27) & 4) == 4, nil
438 }
439 440 // signRFC6979 generates a deterministic ECDSA signature according to RFC 6979 and BIP 62.
441 func signRFC6979(privateKey *PrivateKey, hash []byte) (*Signature, error) {
442 443 privkey := privateKey.ToECDSA()
444 N := S256().N
445 halfOrder := S256().halfOrder
446 k := nonceRFC6979(privkey.D, hash)
447 inv := new(big.Int).ModInverse(k, N)
448 r, _ := privkey.Curve.ScalarBaseMult(k.Bytes())
449 r.Mod(r, N)
450 451 if r.Sign() == 0 {
452 return nil, errors.New("calculated R is zero")
453 }
454 455 e := hashToInt(hash, privkey.Curve)
456 s := new(big.Int).Mul(privkey.D, r)
457 s.Add(s, e)
458 s.Mul(s, inv)
459 s.Mod(s, N)
460 461 if s.Cmp(halfOrder) == 1 {
462 s.Sub(N, s)
463 }
464 if s.Sign() == 0 {
465 return nil, errors.New("calculated S is zero")
466 }
467 return &Signature{R: r, S: s}, nil
468 }
469 470 // nonceRFC6979 generates an ECDSA nonce (`k`) deterministically according to RFC 6979.
471 // It takes a 32-byte hash as an input and returns 32-byte nonce to be used in ECDSA algorithm.
472 func nonceRFC6979(privkey *big.Int, hash []byte) *big.Int {
473 474 curve := S256()
475 q := curve.Params().N
476 x := privkey
477 alg := sha256.New
478 479 qlen := q.BitLen()
480 holen := alg().Size()
481 rolen := (qlen + 7) >> 3
482 bx := append(int2octets(x, rolen), bits2octets(hash, curve, rolen)...)
483 484 // Step B
485 v := bytes.Repeat(oneInitializer, holen)
486 487 // Step C (Go zeroes the all allocated memory)
488 k := make([]byte, holen)
489 490 // Step D
491 k = mac(alg, k, append(append(v, 0x00), bx...))
492 493 // Step E
494 v = mac(alg, k, v)
495 496 // Step F
497 k = mac(alg, k, append(append(v, 0x01), bx...))
498 499 // Step G
500 v = mac(alg, k, v)
501 502 // Step H
503 for {
504 // Step H1
505 var t []byte
506 507 // Step H2
508 for len(t)*8 < qlen {
509 v = mac(alg, k, v)
510 t = append(t, v...)
511 }
512 513 // Step H3
514 secret := hashToInt(t, curve)
515 if secret.Cmp(one) >= 0 && secret.Cmp(q) < 0 {
516 return secret
517 }
518 k = mac(alg, k, append(v, 0x00))
519 v = mac(alg, k, v)
520 }
521 }
522 523 // mac returns an HMAC of the given key and message.
524 func mac(alg func() hash.Hash, k, m []byte) []byte {
525 h := hmac.New(alg, k)
526 h.Write(m)
527 return h.Sum(nil)
528 }
529 530 // https://tools.ietf.org/html/rfc6979#section-2.3.3
531 func int2octets(v *big.Int, rolen int) []byte {
532 out := v.Bytes()
533 534 // left pad with zeros if it's too short
535 if len(out) < rolen {
536 out2 := make([]byte, rolen)
537 copy(out2[rolen-len(out):], out)
538 return out2
539 }
540 541 // drop most significant bytes if it's too long
542 if len(out) > rolen {
543 out2 := make([]byte, rolen)
544 copy(out2, out[len(out)-rolen:])
545 return out2
546 }
547 548 return out
549 }
550 551 // https://tools.ietf.org/html/rfc6979#section-2.3.4
552 func bits2octets(in []byte, curve elliptic.Curve, rolen int) []byte {
553 z1 := hashToInt(in, curve)
554 z2 := new(big.Int).Sub(z1, curve.Params().N)
555 if z2.Sign() < 0 {
556 return int2octets(z1, rolen)
557 }
558 return int2octets(z2, rolen)
559 }
560