vendor/github.com/btcsuite/btcd/btcec/signature.go

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