1 files changed, 539 insertions, 0 deletions
diff --git a/vendor/github.com/btcsuite/btcd/btcec/signature.go b/vendor/github.com/btcsuite/btcd/btcec/signature.go
new file mode 100644
index 000000000..9b2765207
--- /dev/null
+++ b/vendor/github.com/btcsuite/btcd/btcec/signature.go
@@ -0,0 +1,539 @@
+// Copyright (c) 2013-2017 The btcsuite developers
+// Use of this source code is governed by an ISC
+// license that can be found in the LICENSE file.
+
+package btcec
+
+import (
+	"bytes"
+	"crypto/ecdsa"
+	"crypto/elliptic"
+	"crypto/hmac"
+	"crypto/sha256"
+	"errors"
+	"fmt"
+	"hash"
+	"math/big"
+)
+
+// Errors returned by canonicalPadding.
+var (
+	errNegativeValue          = errors.New("value may be interpreted as negative")
+	errExcessivelyPaddedValue = errors.New("value is excessively padded")
+)
+
+// Signature is a type representing an ecdsa signature.
+type Signature struct {
+	R *big.Int
+	S *big.Int
+}
+
+var (
+	// Curve order and halforder, used to tame ECDSA malleability (see BIP-0062)
+	order     = new(big.Int).Set(S256().N)
+	halforder = new(big.Int).Rsh(order, 1)
+
+	// Used in RFC6979 implementation when testing the nonce for correctness
+	one = big.NewInt(1)
+
+	// oneInitializer is used to fill a byte slice with byte 0x01.  It is provided
+	// here to avoid the need to create it multiple times.
+	oneInitializer = []byte{0x01}
+)
+
+// Serialize returns the ECDSA signature in the more strict DER format.  Note
+// that the serialized bytes returned do not include the appended hash type
+// used in Bitcoin signature scripts.
+//
+// encoding/asn1 is broken so we hand roll this output:
+//
+// 0x30 <length> 0x02 <length r> r 0x02 <length s> s
+func (sig *Signature) Serialize() []byte {
+	// low 'S' malleability breaker
+	sigS := sig.S
+	if sigS.Cmp(halforder) == 1 {
+		sigS = new(big.Int).Sub(order, sigS)
+	}
+	// Ensure the encoded bytes for the r and s values are canonical and
+	// thus suitable for DER encoding.
+	rb := canonicalizeInt(sig.R)
+	sb := canonicalizeInt(sigS)
+
+	// total length of returned signature is 1 byte for each magic and
+	// length (6 total), plus lengths of r and s
+	length := 6 + len(rb) + len(sb)
+	b := make([]byte, length, length)
+
+	b[0] = 0x30
+	b[1] = byte(length - 2)
+	b[2] = 0x02
+	b[3] = byte(len(rb))
+	offset := copy(b[4:], rb) + 4
+	b[offset] = 0x02
+	b[offset+1] = byte(len(sb))
+	copy(b[offset+2:], sb)
+	return b
+}
+
+// Verify calls ecdsa.Verify to verify the signature of hash using the public
+// key.  It returns true if the signature is valid, false otherwise.
+func (sig *Signature) Verify(hash []byte, pubKey *PublicKey) bool {
+	return ecdsa.Verify(pubKey.ToECDSA(), hash, sig.R, sig.S)
+}
+
+// IsEqual compares this Signature instance to the one passed, returning true
+// if both Signatures are equivalent. A signature is equivalent to another, if
+// they both have the same scalar value for R and S.
+func (sig *Signature) IsEqual(otherSig *Signature) bool {
+	return sig.R.Cmp(otherSig.R) == 0 &&
+		sig.S.Cmp(otherSig.S) == 0
+}
+
+func parseSig(sigStr []byte, curve elliptic.Curve, der bool) (*Signature, error) {
+	// Originally this code used encoding/asn1 in order to parse the
+	// signature, but a number of problems were found with this approach.
+	// Despite the fact that signatures are stored as DER, the difference
+	// between go's idea of a bignum (and that they have sign) doesn't agree
+	// with the openssl one (where they do not). The above is true as of
+	// Go 1.1. In the end it was simpler to rewrite the code to explicitly
+	// understand the format which is this:
+	// 0x30 <length of whole message> <0x02> <length of R> <R> 0x2
+	// <length of S> <S>.
+
+	signature := &Signature{}
+
+	// minimal message is when both numbers are 1 bytes. adding up to:
+	// 0x30 + len + 0x02 + 0x01 + <byte> + 0x2 + 0x01 + <byte>
+	if len(sigStr) < 8 {
+		return nil, errors.New("malformed signature: too short")
+	}
+	// 0x30
+	index := 0
+	if sigStr[index] != 0x30 {
+		return nil, errors.New("malformed signature: no header magic")
+	}
+	index++
+	// length of remaining message
+	siglen := sigStr[index]
+	index++
+	if int(siglen+2) > len(sigStr) {
+		return nil, errors.New("malformed signature: bad length")
+	}
+	// trim the slice we're working on so we only look at what matters.
+	sigStr = sigStr[:siglen+2]
+
+	// 0x02
+	if sigStr[index] != 0x02 {
+		return nil,
+			errors.New("malformed signature: no 1st int marker")
+	}
+	index++
+
+	// Length of signature R.
+	rLen := int(sigStr[index])
+	// must be positive, must be able to fit in another 0x2, <len> <s>
+	// hence the -3. We assume that the length must be at least one byte.
+	index++
+	if rLen <= 0 || rLen > len(sigStr)-index-3 {
+		return nil, errors.New("malformed signature: bogus R length")
+	}
+
+	// Then R itself.
+	rBytes := sigStr[index : index+rLen]
+	if der {
+		switch err := canonicalPadding(rBytes); err {
+		case errNegativeValue:
+			return nil, errors.New("signature R is negative")
+		case errExcessivelyPaddedValue:
+			return nil, errors.New("signature R is excessively padded")
+		}
+	}
+	signature.R = new(big.Int).SetBytes(rBytes)
+	index += rLen
+	// 0x02. length already checked in previous if.
+	if sigStr[index] != 0x02 {
+		return nil, errors.New("malformed signature: no 2nd int marker")
+	}
+	index++
+
+	// Length of signature S.
+	sLen := int(sigStr[index])
+	index++
+	// S should be the rest of the string.
+	if sLen <= 0 || sLen > len(sigStr)-index {
+		return nil, errors.New("malformed signature: bogus S length")
+	}
+
+	// Then S itself.
+	sBytes := sigStr[index : index+sLen]
+	if der {
+		switch err := canonicalPadding(sBytes); err {
+		case errNegativeValue:
+			return nil, errors.New("signature S is negative")
+		case errExcessivelyPaddedValue:
+			return nil, errors.New("signature S is excessively padded")
+		}
+	}
+	signature.S = new(big.Int).SetBytes(sBytes)
+	index += sLen
+
+	// sanity check length parsing
+	if index != len(sigStr) {
+		return nil, fmt.Errorf("malformed signature: bad final length %v != %v",
+			index, len(sigStr))
+	}
+
+	// Verify also checks this, but we can be more sure that we parsed
+	// correctly if we verify here too.
+	// FWIW the ecdsa spec states that R and S must be | 1, N - 1 |
+	// but crypto/ecdsa only checks for Sign != 0. Mirror that.
+	if signature.R.Sign() != 1 {
+		return nil, errors.New("signature R isn't 1 or more")
+	}
+	if signature.S.Sign() != 1 {
+		return nil, errors.New("signature S isn't 1 or more")
+	}
+	if signature.R.Cmp(curve.Params().N) >= 0 {
+		return nil, errors.New("signature R is >= curve.N")
+	}
+	if signature.S.Cmp(curve.Params().N) >= 0 {
+		return nil, errors.New("signature S is >= curve.N")
+	}
+
+	return signature, nil
+}
+
+// ParseSignature parses a signature in BER format for the curve type `curve'
+// into a Signature type, perfoming some basic sanity checks.  If parsing
+// according to the more strict DER format is needed, use ParseDERSignature.
+func ParseSignature(sigStr []byte, curve elliptic.Curve) (*Signature, error) {
+	return parseSig(sigStr, curve, false)
+}
+
+// ParseDERSignature parses a signature in DER format for the curve type
+// `curve` into a Signature type.  If parsing according to the less strict
+// BER format is needed, use ParseSignature.
+func ParseDERSignature(sigStr []byte, curve elliptic.Curve) (*Signature, error) {
+	return parseSig(sigStr, curve, true)
+}
+
+// canonicalizeInt returns the bytes for the passed big integer adjusted as
+// necessary to ensure that a big-endian encoded integer can't possibly be
+// misinterpreted as a negative number.  This can happen when the most
+// significant bit is set, so it is padded by a leading zero byte in this case.
+// Also, the returned bytes will have at least a single byte when the passed
+// value is 0.  This is required for DER encoding.
+func canonicalizeInt(val *big.Int) []byte {
+	b := val.Bytes()
+	if len(b) == 0 {
+		b = []byte{0x00}
+	}
+	if b[0]&0x80 != 0 {
+		paddedBytes := make([]byte, len(b)+1)
+		copy(paddedBytes[1:], b)
+		b = paddedBytes
+	}
+	return b
+}
+
+// canonicalPadding checks whether a big-endian encoded integer could
+// possibly be misinterpreted as a negative number (even though OpenSSL
+// treats all numbers as unsigned), or if there is any unnecessary
+// leading zero padding.
+func canonicalPadding(b []byte) error {
+	switch {
+	case b[0]&0x80 == 0x80:
+		return errNegativeValue
+	case len(b) > 1 && b[0] == 0x00 && b[1]&0x80 != 0x80:
+		return errExcessivelyPaddedValue
+	default:
+		return nil
+	}
+}
+
+// hashToInt converts a hash value to an integer. There is some disagreement
+// about how this is done. [NSA] suggests that this is done in the obvious
+// manner, but [SECG] truncates the hash to the bit-length of the curve order
+// first. We follow [SECG] because that's what OpenSSL does. Additionally,
+// OpenSSL right shifts excess bits from the number if the hash is too large
+// and we mirror that too.
+// This is borrowed from crypto/ecdsa.
+func hashToInt(hash []byte, c elliptic.Curve) *big.Int {
+	orderBits := c.Params().N.BitLen()
+	orderBytes := (orderBits + 7) / 8
+	if len(hash) > orderBytes {
+		hash = hash[:orderBytes]
+	}
+
+	ret := new(big.Int).SetBytes(hash)
+	excess := len(hash)*8 - orderBits
+	if excess > 0 {
+		ret.Rsh(ret, uint(excess))
+	}
+	return ret
+}
+
+// recoverKeyFromSignature recoves a public key from the signature "sig" on the
+// given message hash "msg". Based on the algorithm found in section 5.1.5 of
+// SEC 1 Ver 2.0, page 47-48 (53 and 54 in the pdf). This performs the details
+// in the inner loop in Step 1. The counter provided is actually the j parameter
+// of the loop * 2 - on the first iteration of j we do the R case, else the -R
+// case in step 1.6. This counter is used in the bitcoin compressed signature
+// format and thus we match bitcoind's behaviour here.
+func recoverKeyFromSignature(curve *KoblitzCurve, sig *Signature, msg []byte,
+	iter int, doChecks bool) (*PublicKey, error) {
+	// 1.1 x = (n * i) + r
+	Rx := new(big.Int).Mul(curve.Params().N,
+		new(big.Int).SetInt64(int64(iter/2)))
+	Rx.Add(Rx, sig.R)
+	if Rx.Cmp(curve.Params().P) != -1 {
+		return nil, errors.New("calculated Rx is larger than curve P")
+	}
+
+	// convert 02<Rx> to point R. (step 1.2 and 1.3). If we are on an odd
+	// iteration then 1.6 will be done with -R, so we calculate the other
+	// term when uncompressing the point.
+	Ry, err := decompressPoint(curve, Rx, iter%2 == 1)
+	if err != nil {
+		return nil, err
+	}
+
+	// 1.4 Check n*R is point at infinity
+	if doChecks {
+		nRx, nRy := curve.ScalarMult(Rx, Ry, curve.Params().N.Bytes())
+		if nRx.Sign() != 0 || nRy.Sign() != 0 {
+			return nil, errors.New("n*R does not equal the point at infinity")
+		}
+	}
+
+	// 1.5 calculate e from message using the same algorithm as ecdsa
+	// signature calculation.
+	e := hashToInt(msg, curve)
+
+	// Step 1.6.1:
+	// We calculate the two terms sR and eG separately multiplied by the
+	// inverse of r (from the signature). We then add them to calculate
+	// Q = r^-1(sR-eG)
+	invr := new(big.Int).ModInverse(sig.R, curve.Params().N)
+
+	// first term.
+	invrS := new(big.Int).Mul(invr, sig.S)
+	invrS.Mod(invrS, curve.Params().N)
+	sRx, sRy := curve.ScalarMult(Rx, Ry, invrS.Bytes())
+
+	// second term.
+	e.Neg(e)
+	e.Mod(e, curve.Params().N)
+	e.Mul(e, invr)
+	e.Mod(e, curve.Params().N)
+	minuseGx, minuseGy := curve.ScalarBaseMult(e.Bytes())
+
+	// TODO: this would be faster if we did a mult and add in one
+	// step to prevent the jacobian conversion back and forth.
+	Qx, Qy := curve.Add(sRx, sRy, minuseGx, minuseGy)
+
+	return &PublicKey{
+		Curve: curve,
+		X:     Qx,
+		Y:     Qy,
+	}, nil
+}
+
+// SignCompact produces a compact signature of the data in hash with the given
+// private key on the given koblitz curve. The isCompressed  parameter should
+// be used to detail if the given signature should reference a compressed
+// public key or not. If successful the bytes of the compact signature will be
+// returned in the format:
+// <(byte of 27+public key solution)+4 if compressed >< padded bytes for signature R><padded bytes for signature S>
+// where the R and S parameters are padde up to the bitlengh of the curve.
+func SignCompact(curve *KoblitzCurve, key *PrivateKey,
+	hash []byte, isCompressedKey bool) ([]byte, error) {
+	sig, err := key.Sign(hash)
+	if err != nil {
+		return nil, err
+	}
+
+	// bitcoind checks the bit length of R and S here. The ecdsa signature
+	// algorithm returns R and S mod N therefore they will be the bitsize of
+	// the curve, and thus correctly sized.
+	for i := 0; i < (curve.H+1)*2; i++ {
+		pk, err := recoverKeyFromSignature(curve, sig, hash, i, true)
+		if err == nil && pk.X.Cmp(key.X) == 0 && pk.Y.Cmp(key.Y) == 0 {
+			result := make([]byte, 1, 2*curve.byteSize+1)
+			result[0] = 27 + byte(i)
+			if isCompressedKey {
+				result[0] += 4
+			}
+			// Not sure this needs rounding but safer to do so.
+			curvelen := (curve.BitSize + 7) / 8
+
+			// Pad R and S to curvelen if needed.
+			bytelen := (sig.R.BitLen() + 7) / 8
+			if bytelen < curvelen {
+				result = append(result,
+					make([]byte, curvelen-bytelen)...)
+			}
+			result = append(result, sig.R.Bytes()...)
+
+			bytelen = (sig.S.BitLen() + 7) / 8
+			if bytelen < curvelen {
+				result = append(result,
+					make([]byte, curvelen-bytelen)...)
+			}
+			result = append(result, sig.S.Bytes()...)
+
+			return result, nil
+		}
+	}
+
+	return nil, errors.New("no valid solution for pubkey found")
+}
+
+// RecoverCompact verifies the compact signature "signature" of "hash" for the
+// Koblitz curve in "curve". If the signature matches then the recovered public
+// key will be returned as well as a boolen if the original key was compressed
+// or not, else an error will be returned.
+func RecoverCompact(curve *KoblitzCurve, signature,
+	hash []byte) (*PublicKey, bool, error) {
+	bitlen := (curve.BitSize + 7) / 8
+	if len(signature) != 1+bitlen*2 {
+		return nil, false, errors.New("invalid compact signature size")
+	}
+
+	iteration := int((signature[0] - 27) & ^byte(4))
+
+	// format is <header byte><bitlen R><bitlen S>
+	sig := &Signature{
+		R: new(big.Int).SetBytes(signature[1 : bitlen+1]),
+		S: new(big.Int).SetBytes(signature[bitlen+1:]),
+	}
+	// The iteration used here was encoded
+	key, err := recoverKeyFromSignature(curve, sig, hash, iteration, false)
+	if err != nil {
+		return nil, false, err
+	}
+
+	return key, ((signature[0] - 27) & 4) == 4, nil
+}
+
+// signRFC6979 generates a deterministic ECDSA signature according to RFC 6979 and BIP 62.
+func signRFC6979(privateKey *PrivateKey, hash []byte) (*Signature, error) {
+
+	privkey := privateKey.ToECDSA()
+	N := order
+	k := nonceRFC6979(privkey.D, hash)
+	inv := new(big.Int).ModInverse(k, N)
+	r, _ := privkey.Curve.ScalarBaseMult(k.Bytes())
+	if r.Cmp(N) == 1 {
+		r.Sub(r, N)
+	}
+
+	if r.Sign() == 0 {
+		return nil, errors.New("calculated R is zero")
+	}
+
+	e := hashToInt(hash, privkey.Curve)
+	s := new(big.Int).Mul(privkey.D, r)
+	s.Add(s, e)
+	s.Mul(s, inv)
+	s.Mod(s, N)
+
+	if s.Cmp(halforder) == 1 {
+		s.Sub(N, s)
+	}
+	if s.Sign() == 0 {
+		return nil, errors.New("calculated S is zero")
+	}
+	return &Signature{R: r, S: s}, nil
+}
+
+// nonceRFC6979 generates an ECDSA nonce (`k`) deterministically according to RFC 6979.
+// It takes a 32-byte hash as an input and returns 32-byte nonce to be used in ECDSA algorithm.
+func nonceRFC6979(privkey *big.Int, hash []byte) *big.Int {
+
+	curve := S256()
+	q := curve.Params().N
+	x := privkey
+	alg := sha256.New
+
+	qlen := q.BitLen()
+	holen := alg().Size()
+	rolen := (qlen + 7) >> 3
+	bx := append(int2octets(x, rolen), bits2octets(hash, curve, rolen)...)
+
+	// Step B
+	v := bytes.Repeat(oneInitializer, holen)
+
+	// Step C (Go zeroes the all allocated memory)
+	k := make([]byte, holen)
+
+	// Step D
+	k = mac(alg, k, append(append(v, 0x00), bx...))
+
+	// Step E
+	v = mac(alg, k, v)
+
+	// Step F
+	k = mac(alg, k, append(append(v, 0x01), bx...))
+
+	// Step G
+	v = mac(alg, k, v)
+
+	// Step H
+	for {
+		// Step H1
+		var t []byte
+
+		// Step H2
+		for len(t)*8 < qlen {
+			v = mac(alg, k, v)
+			t = append(t, v...)
+		}
+
+		// Step H3
+		secret := hashToInt(t, curve)
+		if secret.Cmp(one) >= 0 && secret.Cmp(q) < 0 {
+			return secret
+		}
+		k = mac(alg, k, append(v, 0x00))
+		v = mac(alg, k, v)
+	}
+}
+
+// mac returns an HMAC of the given key and message.
+func mac(alg func() hash.Hash, k, m []byte) []byte {
+	h := hmac.New(alg, k)
+	h.Write(m)
+	return h.Sum(nil)
+}
+
+// https://tools.ietf.org/html/rfc6979#section-2.3.3
+func int2octets(v *big.Int, rolen int) []byte {
+	out := v.Bytes()
+
+	// left pad with zeros if it's too short
+	if len(out) < rolen {
+		out2 := make([]byte, rolen)
+		copy(out2[rolen-len(out):], out)
+		return out2
+	}
+
+	// drop most significant bytes if it's too long
+	if len(out) > rolen {
+		out2 := make([]byte, rolen)
+		copy(out2, out[len(out)-rolen:])
+		return out2
+	}
+
+	return out
+}
+
+// https://tools.ietf.org/html/rfc6979#section-2.3.4
+func bits2octets(in []byte, curve elliptic.Curve, rolen int) []byte {
+	z1 := hashToInt(in, curve)
+	z2 := new(big.Int).Sub(z1, curve.Params().N)
+	if z2.Sign() < 0 {
+		return int2octets(z1, rolen)
+	}
+	return int2octets(z2, rolen)
+}