diff options
Diffstat (limited to 'cli/vendor/github.com/decred/dcrd/dcrec/secp256k1/v4/ecdsa/signature.go')
| -rw-r--r-- | cli/vendor/github.com/decred/dcrd/dcrec/secp256k1/v4/ecdsa/signature.go | 925 |
1 files changed, 925 insertions, 0 deletions
diff --git a/cli/vendor/github.com/decred/dcrd/dcrec/secp256k1/v4/ecdsa/signature.go b/cli/vendor/github.com/decred/dcrd/dcrec/secp256k1/v4/ecdsa/signature.go new file mode 100644 index 0000000..50f1721 --- /dev/null +++ b/cli/vendor/github.com/decred/dcrd/dcrec/secp256k1/v4/ecdsa/signature.go @@ -0,0 +1,925 @@ +// Copyright (c) 2013-2014 The btcsuite developers +// Copyright (c) 2015-2020 The Decred developers +// Use of this source code is governed by an ISC +// license that can be found in the LICENSE file. + +package ecdsa + +import ( + "errors" + "fmt" + + "github.com/decred/dcrd/dcrec/secp256k1/v4" +) + +// References: +// [GECC]: Guide to Elliptic Curve Cryptography (Hankerson, Menezes, Vanstone) +// +// [ISO/IEC 8825-1]: Information technology — ASN.1 encoding rules: +// Specification of Basic Encoding Rules (BER), Canonical Encoding Rules +// (CER) and Distinguished Encoding Rules (DER) +// +// [SEC1]: Elliptic Curve Cryptography (May 31, 2009, Version 2.0) +// https://www.secg.org/sec1-v2.pdf + +var ( + // zero32 is an array of 32 bytes used for the purposes of zeroing and is + // defined here to avoid extra allocations. + zero32 = [32]byte{} + + // orderAsFieldVal is the order of the secp256k1 curve group stored as a + // field value. It is provided here to avoid the need to create it multiple + // times. + orderAsFieldVal = func() *secp256k1.FieldVal { + var f secp256k1.FieldVal + f.SetByteSlice(secp256k1.Params().N.Bytes()) + return &f + }() +) + +const ( + // asn1SequenceID is the ASN.1 identifier for a sequence and is used when + // parsing and serializing signatures encoded with the Distinguished + // Encoding Rules (DER) format per section 10 of [ISO/IEC 8825-1]. + asn1SequenceID = 0x30 + + // asn1IntegerID is the ASN.1 identifier for an integer and is used when + // parsing and serializing signatures encoded with the Distinguished + // Encoding Rules (DER) format per section 10 of [ISO/IEC 8825-1]. + asn1IntegerID = 0x02 +) + +// Signature is a type representing an ECDSA signature. +type Signature struct { + r secp256k1.ModNScalar + s secp256k1.ModNScalar +} + +// NewSignature instantiates a new signature given some r and s values. +func NewSignature(r, s *secp256k1.ModNScalar) *Signature { + return &Signature{*r, *s} +} + +// Serialize returns the ECDSA signature in the Distinguished Encoding Rules +// (DER) format per section 10 of [ISO/IEC 8825-1] and such that the S component +// of the signature is less than or equal to the half order of the group. +// +// Note that the serialized bytes returned do not include the appended hash type +// used in Decred signature scripts. +func (sig *Signature) Serialize() []byte { + // The format of a DER encoded signature is as follows: + // + // 0x30 <total length> 0x02 <length of R> <R> 0x02 <length of S> <S> + // - 0x30 is the ASN.1 identifier for a sequence. + // - Total length is 1 byte and specifies length of all remaining data. + // - 0x02 is the ASN.1 identifier that specifies an integer follows. + // - Length of R is 1 byte and specifies how many bytes R occupies. + // - R is the arbitrary length big-endian encoded number which + // represents the R value of the signature. DER encoding dictates + // that the value must be encoded using the minimum possible number + // of bytes. This implies the first byte can only be null if the + // highest bit of the next byte is set in order to prevent it from + // being interpreted as a negative number. + // - 0x02 is once again the ASN.1 integer identifier. + // - Length of S is 1 byte and specifies how many bytes S occupies. + // - S is the arbitrary length big-endian encoded number which + // represents the S value of the signature. The encoding rules are + // identical as those for R. + + // Ensure the S component of the signature is less than or equal to the half + // order of the group because both S and its negation are valid signatures + // modulo the order, so this forces a consistent choice to reduce signature + // malleability. + sigS := new(secp256k1.ModNScalar).Set(&sig.s) + if sigS.IsOverHalfOrder() { + sigS.Negate() + } + + // Serialize the R and S components of the signature into their fixed + // 32-byte big-endian encoding. Note that the extra leading zero byte is + // used to ensure it is canonical per DER and will be stripped if needed + // below. + var rBuf, sBuf [33]byte + sig.r.PutBytesUnchecked(rBuf[1:33]) + sigS.PutBytesUnchecked(sBuf[1:33]) + + // Ensure the encoded bytes for the R and S components are canonical per DER + // by trimming all leading zero bytes so long as the next byte does not have + // the high bit set and it's not the final byte. + canonR, canonS := rBuf[:], sBuf[:] + for len(canonR) > 1 && canonR[0] == 0x00 && canonR[1]&0x80 == 0 { + canonR = canonR[1:] + } + for len(canonS) > 1 && canonS[0] == 0x00 && canonS[1]&0x80 == 0 { + canonS = canonS[1:] + } + + // Total length of returned signature is 1 byte for each magic and length + // (6 total), plus lengths of R and S. + totalLen := 6 + len(canonR) + len(canonS) + b := make([]byte, 0, totalLen) + b = append(b, asn1SequenceID) + b = append(b, byte(totalLen-2)) + b = append(b, asn1IntegerID) + b = append(b, byte(len(canonR))) + b = append(b, canonR...) + b = append(b, asn1IntegerID) + b = append(b, byte(len(canonS))) + b = append(b, canonS...) + return b +} + +// zeroArray32 zeroes the provided 32-byte buffer. +func zeroArray32(b *[32]byte) { + copy(b[:], zero32[:]) +} + +// fieldToModNScalar converts a field value to scalar modulo the group order and +// returns the scalar along with either 1 if it was reduced (aka it overflowed) +// or 0 otherwise. +// +// Note that a bool is not used here because it is not possible in Go to convert +// from a bool to numeric value in constant time and many constant-time +// operations require a numeric value. +func fieldToModNScalar(v *secp256k1.FieldVal) (secp256k1.ModNScalar, uint32) { + var buf [32]byte + v.PutBytes(&buf) + var s secp256k1.ModNScalar + overflow := s.SetBytes(&buf) + zeroArray32(&buf) + return s, overflow +} + +// modNScalarToField converts a scalar modulo the group order to a field value. +func modNScalarToField(v *secp256k1.ModNScalar) secp256k1.FieldVal { + var buf [32]byte + v.PutBytes(&buf) + var fv secp256k1.FieldVal + fv.SetBytes(&buf) + return fv +} + +// Verify returns whether or not the signature is valid for the provided hash +// and secp256k1 public key. +func (sig *Signature) Verify(hash []byte, pubKey *secp256k1.PublicKey) bool { + // The algorithm for verifying an ECDSA signature is given as algorithm 4.30 + // in [GECC]. + // + // The following is a paraphrased version for reference: + // + // G = curve generator + // N = curve order + // Q = public key + // m = message + // R, S = signature + // + // 1. Fail if R and S are not in [1, N-1] + // 2. e = H(m) + // 3. w = S^-1 mod N + // 4. u1 = e * w mod N + // u2 = R * w mod N + // 5. X = u1G + u2Q + // 6. Fail if X is the point at infinity + // 7. x = X.x mod N (X.x is the x coordinate of X) + // 8. Verified if x == R + // + // However, since all group operations are done internally in Jacobian + // projective space, the algorithm is modified slightly here in order to + // avoid an expensive inversion back into affine coordinates at step 7. + // Credits to Greg Maxwell for originally suggesting this optimization. + // + // Ordinarily, step 7 involves converting the x coordinate to affine by + // calculating x = x / z^2 (mod P) and then calculating the remainder as + // x = x (mod N). Then step 8 compares it to R. + // + // Note that since R is the x coordinate mod N from a random point that was + // originally mod P, and the cofactor of the secp256k1 curve is 1, there are + // only two possible x coordinates that the original random point could have + // been to produce R: x, where x < N, and x+N, where x+N < P. + // + // This implies that the signature is valid if either: + // a) R == X.x / X.z^2 (mod P) + // => R * X.z^2 == X.x (mod P) + // --or-- + // b) R + N < P && R + N == X.x / X.z^2 (mod P) + // => R + N < P && (R + N) * X.z^2 == X.x (mod P) + // + // Therefore the following modified algorithm is used: + // + // 1. Fail if R and S are not in [1, N-1] + // 2. e = H(m) + // 3. w = S^-1 mod N + // 4. u1 = e * w mod N + // u2 = R * w mod N + // 5. X = u1G + u2Q + // 6. Fail if X is the point at infinity + // 7. z = (X.z)^2 mod P (X.z is the z coordinate of X) + // 8. Verified if R * z == X.x (mod P) + // 9. Fail if R + N >= P + // 10. Verified if (R + N) * z == X.x (mod P) + + // Step 1. + // + // Fail if R and S are not in [1, N-1]. + if sig.r.IsZero() || sig.s.IsZero() { + return false + } + + // Step 2. + // + // e = H(m) + var e secp256k1.ModNScalar + e.SetByteSlice(hash) + + // Step 3. + // + // w = S^-1 mod N + w := new(secp256k1.ModNScalar).InverseValNonConst(&sig.s) + + // Step 4. + // + // u1 = e * w mod N + // u2 = R * w mod N + u1 := new(secp256k1.ModNScalar).Mul2(&e, w) + u2 := new(secp256k1.ModNScalar).Mul2(&sig.r, w) + + // Step 5. + // + // X = u1G + u2Q + var X, Q, u1G, u2Q secp256k1.JacobianPoint + pubKey.AsJacobian(&Q) + secp256k1.ScalarBaseMultNonConst(u1, &u1G) + secp256k1.ScalarMultNonConst(u2, &Q, &u2Q) + secp256k1.AddNonConst(&u1G, &u2Q, &X) + + // Step 6. + // + // Fail if X is the point at infinity + if (X.X.IsZero() && X.Y.IsZero()) || X.Z.IsZero() { + return false + } + + // Step 7. + // + // z = (X.z)^2 mod P (X.z is the z coordinate of X) + z := new(secp256k1.FieldVal).SquareVal(&X.Z) + + // Step 8. + // + // Verified if R * z == X.x (mod P) + sigRModP := modNScalarToField(&sig.r) + result := new(secp256k1.FieldVal).Mul2(&sigRModP, z).Normalize() + if result.Equals(&X.X) { + return true + } + + // Step 9. + // + // Fail if R + N >= P + if sigRModP.IsGtOrEqPrimeMinusOrder() { + return false + } + + // Step 10. + // + // Verified if (R + N) * z == X.x (mod P) + sigRModP.Add(orderAsFieldVal) + result.Mul2(&sigRModP, z).Normalize() + return result.Equals(&X.X) +} + +// 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.Equals(&otherSig.r) && sig.s.Equals(&otherSig.s) +} + +// ParseDERSignature parses a signature in the Distinguished Encoding Rules +// (DER) format per section 10 of [ISO/IEC 8825-1] and enforces the following +// additional restrictions specific to secp256k1: +// +// - The R and S values must be in the valid range for secp256k1 scalars: +// - Negative values are rejected +// - Zero is rejected +// - Values greater than or equal to the secp256k1 group order are rejected +func ParseDERSignature(sig []byte) (*Signature, error) { + // The format of a DER encoded signature for secp256k1 is as follows: + // + // 0x30 <total length> 0x02 <length of R> <R> 0x02 <length of S> <S> + // - 0x30 is the ASN.1 identifier for a sequence + // - Total length is 1 byte and specifies length of all remaining data + // - 0x02 is the ASN.1 identifier that specifies an integer follows + // - Length of R is 1 byte and specifies how many bytes R occupies + // - R is the arbitrary length big-endian encoded number which + // represents the R value of the signature. DER encoding dictates + // that the value must be encoded using the minimum possible number + // of bytes. This implies the first byte can only be null if the + // highest bit of the next byte is set in order to prevent it from + // being interpreted as a negative number. + // - 0x02 is once again the ASN.1 integer identifier + // - Length of S is 1 byte and specifies how many bytes S occupies + // - S is the arbitrary length big-endian encoded number which + // represents the S value of the signature. The encoding rules are + // identical as those for R. + // + // NOTE: The DER specification supports specifying lengths that can occupy + // more than 1 byte, however, since this is specific to secp256k1 + // signatures, all lengths will be a single byte. + const ( + // minSigLen is the minimum length of a DER encoded signature and is + // when both R and S are 1 byte each. + // + // 0x30 + <1-byte> + 0x02 + 0x01 + <byte> + 0x2 + 0x01 + <byte> + minSigLen = 8 + + // maxSigLen is the maximum length of a DER encoded signature and is + // when both R and S are 33 bytes each. It is 33 bytes because a + // 256-bit integer requires 32 bytes and an additional leading null byte + // might be required if the high bit is set in the value. + // + // 0x30 + <1-byte> + 0x02 + 0x21 + <33 bytes> + 0x2 + 0x21 + <33 bytes> + maxSigLen = 72 + + // sequenceOffset is the byte offset within the signature of the + // expected ASN.1 sequence identifier. + sequenceOffset = 0 + + // dataLenOffset is the byte offset within the signature of the expected + // total length of all remaining data in the signature. + dataLenOffset = 1 + + // rTypeOffset is the byte offset within the signature of the ASN.1 + // identifier for R and is expected to indicate an ASN.1 integer. + rTypeOffset = 2 + + // rLenOffset is the byte offset within the signature of the length of + // R. + rLenOffset = 3 + + // rOffset is the byte offset within the signature of R. + rOffset = 4 + ) + + // The signature must adhere to the minimum and maximum allowed length. + sigLen := len(sig) + if sigLen < minSigLen { + str := fmt.Sprintf("malformed signature: too short: %d < %d", sigLen, + minSigLen) + return nil, signatureError(ErrSigTooShort, str) + } + if sigLen > maxSigLen { + str := fmt.Sprintf("malformed signature: too long: %d > %d", sigLen, + maxSigLen) + return nil, signatureError(ErrSigTooLong, str) + } + + // The signature must start with the ASN.1 sequence identifier. + if sig[sequenceOffset] != asn1SequenceID { + str := fmt.Sprintf("malformed signature: format has wrong type: %#x", + sig[sequenceOffset]) + return nil, signatureError(ErrSigInvalidSeqID, str) + } + + // The signature must indicate the correct amount of data for all elements + // related to R and S. + if int(sig[dataLenOffset]) != sigLen-2 { + str := fmt.Sprintf("malformed signature: bad length: %d != %d", + sig[dataLenOffset], sigLen-2) + return nil, signatureError(ErrSigInvalidDataLen, str) + } + + // Calculate the offsets of the elements related to S and ensure S is inside + // the signature. + // + // rLen specifies the length of the big-endian encoded number which + // represents the R value of the signature. + // + // sTypeOffset is the offset of the ASN.1 identifier for S and, like its R + // counterpart, is expected to indicate an ASN.1 integer. + // + // sLenOffset and sOffset are the byte offsets within the signature of the + // length of S and S itself, respectively. + rLen := int(sig[rLenOffset]) + sTypeOffset := rOffset + rLen + sLenOffset := sTypeOffset + 1 + if sTypeOffset >= sigLen { + str := "malformed signature: S type indicator missing" + return nil, signatureError(ErrSigMissingSTypeID, str) + } + if sLenOffset >= sigLen { + str := "malformed signature: S length missing" + return nil, signatureError(ErrSigMissingSLen, str) + } + + // The lengths of R and S must match the overall length of the signature. + // + // sLen specifies the length of the big-endian encoded number which + // represents the S value of the signature. + sOffset := sLenOffset + 1 + sLen := int(sig[sLenOffset]) + if sOffset+sLen != sigLen { + str := "malformed signature: invalid S length" + return nil, signatureError(ErrSigInvalidSLen, str) + } + + // R elements must be ASN.1 integers. + if sig[rTypeOffset] != asn1IntegerID { + str := fmt.Sprintf("malformed signature: R integer marker: %#x != %#x", + sig[rTypeOffset], asn1IntegerID) + return nil, signatureError(ErrSigInvalidRIntID, str) + } + + // Zero-length integers are not allowed for R. + if rLen == 0 { + str := "malformed signature: R length is zero" + return nil, signatureError(ErrSigZeroRLen, str) + } + + // R must not be negative. + if sig[rOffset]&0x80 != 0 { + str := "malformed signature: R is negative" + return nil, signatureError(ErrSigNegativeR, str) + } + + // Null bytes at the start of R are not allowed, unless R would otherwise be + // interpreted as a negative number. + if rLen > 1 && sig[rOffset] == 0x00 && sig[rOffset+1]&0x80 == 0 { + str := "malformed signature: R value has too much padding" + return nil, signatureError(ErrSigTooMuchRPadding, str) + } + + // S elements must be ASN.1 integers. + if sig[sTypeOffset] != asn1IntegerID { + str := fmt.Sprintf("malformed signature: S integer marker: %#x != %#x", + sig[sTypeOffset], asn1IntegerID) + return nil, signatureError(ErrSigInvalidSIntID, str) + } + + // Zero-length integers are not allowed for S. + if sLen == 0 { + str := "malformed signature: S length is zero" + return nil, signatureError(ErrSigZeroSLen, str) + } + + // S must not be negative. + if sig[sOffset]&0x80 != 0 { + str := "malformed signature: S is negative" + return nil, signatureError(ErrSigNegativeS, str) + } + + // Null bytes at the start of S are not allowed, unless S would otherwise be + // interpreted as a negative number. + if sLen > 1 && sig[sOffset] == 0x00 && sig[sOffset+1]&0x80 == 0 { + str := "malformed signature: S value has too much padding" + return nil, signatureError(ErrSigTooMuchSPadding, str) + } + + // The signature is validly encoded per DER at this point, however, enforce + // additional restrictions to ensure R and S are in the range [1, N-1] since + // valid ECDSA signatures are required to be in that range per spec. + // + // Also note that while the overflow checks are required to make use of the + // specialized mod N scalar type, rejecting zero here is not strictly + // required because it is also checked when verifying the signature, but + // there really isn't a good reason not to fail early here on signatures + // that do not conform to the ECDSA spec. + + // Strip leading zeroes from R. + rBytes := sig[rOffset : rOffset+rLen] + for len(rBytes) > 0 && rBytes[0] == 0x00 { + rBytes = rBytes[1:] + } + + // R must be in the range [1, N-1]. Notice the check for the maximum number + // of bytes is required because SetByteSlice truncates as noted in its + // comment so it could otherwise fail to detect the overflow. + var r secp256k1.ModNScalar + if len(rBytes) > 32 { + str := "invalid signature: R is larger than 256 bits" + return nil, signatureError(ErrSigRTooBig, str) + } + if overflow := r.SetByteSlice(rBytes); overflow { + str := "invalid signature: R >= group order" + return nil, signatureError(ErrSigRTooBig, str) + } + if r.IsZero() { + str := "invalid signature: R is 0" + return nil, signatureError(ErrSigRIsZero, str) + } + + // Strip leading zeroes from S. + sBytes := sig[sOffset : sOffset+sLen] + for len(sBytes) > 0 && sBytes[0] == 0x00 { + sBytes = sBytes[1:] + } + + // S must be in the range [1, N-1]. Notice the check for the maximum number + // of bytes is required because SetByteSlice truncates as noted in its + // comment so it could otherwise fail to detect the overflow. + var s secp256k1.ModNScalar + if len(sBytes) > 32 { + str := "invalid signature: S is larger than 256 bits" + return nil, signatureError(ErrSigSTooBig, str) + } + if overflow := s.SetByteSlice(sBytes); overflow { + str := "invalid signature: S >= group order" + return nil, signatureError(ErrSigSTooBig, str) + } + if s.IsZero() { + str := "invalid signature: S is 0" + return nil, signatureError(ErrSigSIsZero, str) + } + + // Create and return the signature. + return NewSignature(&r, &s), nil +} + +// signRFC6979 generates a deterministic ECDSA signature according to RFC 6979 +// and BIP 62 and returns it along with an additional public key recovery code +// for efficiently recovering the public key from the signature. +func signRFC6979(privKey *secp256k1.PrivateKey, hash []byte) (*Signature, byte) { + // The algorithm for producing an ECDSA signature is given as algorithm 4.29 + // in [GECC]. + // + // The following is a paraphrased version for reference: + // + // G = curve generator + // N = curve order + // d = private key + // m = message + // r, s = signature + // + // 1. Select random nonce k in [1, N-1] + // 2. Compute kG + // 3. r = kG.x mod N (kG.x is the x coordinate of the point kG) + // Repeat from step 1 if r = 0 + // 4. e = H(m) + // 5. s = k^-1(e + dr) mod N + // Repeat from step 1 if s = 0 + // 6. Return (r,s) + // + // This is slightly modified here to conform to RFC6979 and BIP 62 as + // follows: + // + // A. Instead of selecting a random nonce in step 1, use RFC6979 to generate + // a deterministic nonce in [1, N-1] parameterized by the private key, + // message being signed, and an iteration count for the repeat cases + // B. Negate s calculated in step 5 if it is > N/2 + // This is done because both s and its negation are valid signatures + // modulo the curve order N, so it forces a consistent choice to reduce + // signature malleability + + privKeyScalar := &privKey.Key + var privKeyBytes [32]byte + privKeyScalar.PutBytes(&privKeyBytes) + defer zeroArray32(&privKeyBytes) + for iteration := uint32(0); ; iteration++ { + // Step 1 with modification A. + // + // Generate a deterministic nonce in [1, N-1] parameterized by the + // private key, message being signed, and iteration count. + k := secp256k1.NonceRFC6979(privKeyBytes[:], hash, nil, nil, iteration) + + // Step 2. + // + // Compute kG + // + // Note that the point must be in affine coordinates. + var kG secp256k1.JacobianPoint + secp256k1.ScalarBaseMultNonConst(k, &kG) + kG.ToAffine() + + // Step 3. + // + // r = kG.x mod N + // Repeat from step 1 if r = 0 + r, overflow := fieldToModNScalar(&kG.X) + if r.IsZero() { + k.Zero() + continue + } + + // Since the secp256k1 curve has a cofactor of 1, when recovering a + // public key from an ECDSA signature over it, there are four possible + // candidates corresponding to the following cases: + // + // 1) The X coord of the random point is < N and its Y coord even + // 2) The X coord of the random point is < N and its Y coord is odd + // 3) The X coord of the random point is >= N and its Y coord is even + // 4) The X coord of the random point is >= N and its Y coord is odd + // + // Rather than forcing the recovery procedure to check all possible + // cases, this creates a recovery code that uniquely identifies which of + // the cases apply by making use of 2 bits. Bit 0 identifies the + // oddness case and Bit 1 identifies the overflow case (aka when the X + // coord >= N). + // + // It is also worth noting that making use of Hasse's theorem shows + // there are around log_2((p-n)/p) ~= -127.65 ~= 1 in 2^127 points where + // the X coordinate is >= N. It is not possible to calculate these + // points since that would require breaking the ECDLP, but, in practice + // this strongly implies with extremely high probability that there are + // only a few actual points for which this case is true. + pubKeyRecoveryCode := byte(overflow<<1) | byte(kG.Y.IsOddBit()) + + // Step 4. + // + // e = H(m) + // + // Note that this actually sets e = H(m) mod N which is correct since + // it is only used in step 5 which itself is mod N. + var e secp256k1.ModNScalar + e.SetByteSlice(hash) + + // Step 5 with modification B. + // + // s = k^-1(e + dr) mod N + // Repeat from step 1 if s = 0 + // s = -s if s > N/2 + kInv := new(secp256k1.ModNScalar).InverseValNonConst(k) + k.Zero() + s := new(secp256k1.ModNScalar).Mul2(privKeyScalar, &r).Add(&e).Mul(kInv) + if s.IsZero() { + continue + } + if s.IsOverHalfOrder() { + s.Negate() + + // Negating s corresponds to the random point that would have been + // generated by -k (mod N), which necessarily has the opposite + // oddness since N is prime, thus flip the pubkey recovery code + // oddness bit accordingly. + pubKeyRecoveryCode ^= 0x01 + } + + // Step 6. + // + // Return (r,s) + return NewSignature(&r, s), pubKeyRecoveryCode + } +} + +// Sign generates an ECDSA signature over the secp256k1 curve for the provided +// hash (which should be the result of hashing a larger message) using the given +// private key. The produced signature is deterministic (same message and same +// key yield the same signature) and canonical in accordance with RFC6979 and +// BIP0062. +func Sign(key *secp256k1.PrivateKey, hash []byte) *Signature { + signature, _ := signRFC6979(key, hash) + return signature +} + +const ( + // compactSigSize is the size of a compact signature. It consists of a + // compact signature recovery code byte followed by the R and S components + // serialized as 32-byte big-endian values. 1+32*2 = 65. + // for the R and S components. 1+32+32=65. + compactSigSize = 65 + + // compactSigMagicOffset is a value used when creating the compact signature + // recovery code inherited from Bitcoin and has no meaning, but has been + // retained for compatibility. For historical purposes, it was originally + // picked to avoid a binary representation that would allow compact + // signatures to be mistaken for other components. + compactSigMagicOffset = 27 + + // compactSigCompPubKey is a value used when creating the compact signature + // recovery code to indicate the original public key was compressed. + compactSigCompPubKey = 4 + + // pubKeyRecoveryCodeOddnessBit specifies the bit that indicates the oddess + // of the Y coordinate of the random point calculated when creating a + // signature. + pubKeyRecoveryCodeOddnessBit = 1 << 0 + + // pubKeyRecoveryCodeOverflowBit specifies the bit that indicates the X + // coordinate of the random point calculated when creating a signature was + // >= N, where N is the order of the group. + pubKeyRecoveryCodeOverflowBit = 1 << 1 +) + +// SignCompact produces a compact ECDSA signature over the secp256k1 curve for +// the provided hash (which should be the result of hashing a larger message) +// using the given private key. The isCompressedKey parameter specifies if the +// produced signature should reference a compressed public key or not. +// +// Compact signature format: +// <1-byte compact sig recovery code><32-byte R><32-byte S> +// +// The compact sig recovery code is the value 27 + public key recovery code + 4 +// if the compact signature was created with a compressed public key. +func SignCompact(key *secp256k1.PrivateKey, hash []byte, isCompressedKey bool) []byte { + // Create the signature and associated pubkey recovery code and calculate + // the compact signature recovery code. + sig, pubKeyRecoveryCode := signRFC6979(key, hash) + compactSigRecoveryCode := compactSigMagicOffset + pubKeyRecoveryCode + if isCompressedKey { + compactSigRecoveryCode += compactSigCompPubKey + } + + // Output <compactSigRecoveryCode><32-byte R><32-byte S>. + var b [compactSigSize]byte + b[0] = compactSigRecoveryCode + sig.r.PutBytesUnchecked(b[1:33]) + sig.s.PutBytesUnchecked(b[33:65]) + return b[:] +} + +// RecoverCompact attempts to recover the secp256k1 public key from the provided +// compact signature and message hash. It first verifies the signature, and, if +// the signature matches then the recovered public key will be returned as well +// as a boolean indicating whether or not the original key was compressed. +func RecoverCompact(signature, hash []byte) (*secp256k1.PublicKey, bool, error) { + // The following is very loosely based on the information and algorithm that + // describes recovering a public key from and ECDSA signature in section + // 4.1.6 of [SEC1]. + // + // Given the following parameters: + // + // G = curve generator + // N = group order + // P = field prime + // Q = public key + // m = message + // e = hash of the message + // r, s = signature + // X = random point used when creating signature whose x coordinate is r + // + // The equation to recover a public key candidate from an ECDSA signature + // is: + // Q = r^-1(sX - eG). + // + // This can be verified by plugging it in for Q in the sig verification + // equation: + // X = s^-1(eG + rQ) (mod N) + // => s^-1(eG + r(r^-1(sX - eG))) (mod N) + // => s^-1(eG + sX - eG) (mod N) + // => s^-1(sX) (mod N) + // => X (mod N) + // + // However, note that since r is the x coordinate mod N from a random point + // that was originally mod P, and the cofactor of the secp256k1 curve is 1, + // there are four possible points that the original random point could have + // been to produce r: (r,y), (r,-y), (r+N,y), and (r+N,-y). At least 2 of + // those points will successfully verify, and all 4 will successfully verify + // when the original x coordinate was in the range [N+1, P-1], but in any + // case, only one of them corresponds to the original private key used. + // + // The method described by section 4.1.6 of [SEC1] to determine which one is + // the correct one involves calculating each possibility as a candidate + // public key and comparing the candidate to the authentic public key. It + // also hints that is is possible to generate the signature in a such a + // way that only one of the candidate public keys is viable. + // + // A more efficient approach that is specific to the secp256k1 curve is used + // here instead which is to produce a "pubkey recovery code" when signing + // that uniquely identifies which of the 4 possibilities is correct for the + // original random point and using that to recover the pubkey directly as + // follows: + // + // 1. Fail if r and s are not in [1, N-1] + // 2. Convert r to integer mod P + // 3. If pubkey recovery code overflow bit is set: + // 3.1 Fail if r + N >= P + // 3.2 r = r + N (mod P) + // 4. y = +sqrt(r^3 + 7) (mod P) + // 4.1 Fail if y does not exist + // 4.2 y = -y if needed to match pubkey recovery code oddness bit + // 5. X = (r, y) + // 6. e = H(m) mod N + // 7. w = r^-1 mod N + // 8. u1 = -(e * w) mod N + // u2 = s * w mod N + // 9. Q = u1G + u2X + // 10. Fail if Q is the point at infinity + + // A compact signature consists of a recovery byte followed by the R and + // S components serialized as 32-byte big-endian values. + if len(signature) != compactSigSize { + return nil, false, errors.New("invalid compact signature size") + } + + // Parse and validate the compact signature recovery code. + const ( + minValidCode = compactSigMagicOffset + maxValidCode = compactSigMagicOffset + compactSigCompPubKey + 3 + ) + sigRecoveryCode := signature[0] + if sigRecoveryCode < minValidCode || sigRecoveryCode > maxValidCode { + return nil, false, errors.New("invalid compact signature recovery code") + } + sigRecoveryCode -= compactSigMagicOffset + wasCompressed := sigRecoveryCode&compactSigCompPubKey != 0 + pubKeyRecoveryCode := sigRecoveryCode & 3 + + // Step 1. + // + // Parse and validate the R and S signature components. + // + // Fail if r and s are not in [1, N-1]. + var r, s secp256k1.ModNScalar + if overflow := r.SetByteSlice(signature[1:33]); overflow { + return nil, false, errors.New("signature R is >= curve order") + } + if r.IsZero() { + return nil, false, errors.New("signature R is 0") + } + if overflow := s.SetByteSlice(signature[33:]); overflow { + return nil, false, errors.New("signature S is >= curve order") + } + if s.IsZero() { + return nil, false, errors.New("signature S is 0") + } + + // Step 2. + // + // Convert r to integer mod P. + fieldR := modNScalarToField(&r) + + // Step 3. + // + // If pubkey recovery code overflow bit is set: + if pubKeyRecoveryCode&pubKeyRecoveryCodeOverflowBit != 0 { + // Step 3.1. + // + // Fail if r + N >= P + // + // Either the signature or the recovery code must be invalid if the + // recovery code overflow bit is set and adding N to the R component + // would exceed the field prime since R originally came from the X + // coordinate of a random point on the curve. + if fieldR.IsGtOrEqPrimeMinusOrder() { + return nil, false, errors.New("signature R + N >= P") + } + + // Step 3.2. + // + // r = r + N (mod P) + fieldR.Add(orderAsFieldVal) + } + + // Step 4. + // + // y = +sqrt(r^3 + 7) (mod P) + // Fail if y does not exist. + // y = -y if needed to match pubkey recovery code oddness bit + // + // The signature must be invalid if the calculation fails because the X + // coord originally came from a random point on the curve which means there + // must be a Y coord that satisfies the equation for a valid signature. + oddY := pubKeyRecoveryCode&pubKeyRecoveryCodeOddnessBit != 0 + var y secp256k1.FieldVal + if valid := secp256k1.DecompressY(&fieldR, oddY, &y); !valid { + return nil, false, errors.New("signature is not for a valid curve point") + } + + // Step 5. + // + // X = (r, y) + var X secp256k1.JacobianPoint + X.X.Set(&fieldR) + X.Y.Set(&y) + X.Z.SetInt(1) + + // Step 6. + // + // e = H(m) mod N + var e secp256k1.ModNScalar + e.SetByteSlice(hash) + + // Step 7. + // + // w = r^-1 mod N + w := new(secp256k1.ModNScalar).InverseValNonConst(&r) + + // Step 8. + // + // u1 = -(e * w) mod N + // u2 = s * w mod N + u1 := new(secp256k1.ModNScalar).Mul2(&e, w).Negate() + u2 := new(secp256k1.ModNScalar).Mul2(&s, w) + + // Step 9. + // + // Q = u1G + u2X + var Q, u1G, u2X secp256k1.JacobianPoint + secp256k1.ScalarBaseMultNonConst(u1, &u1G) + secp256k1.ScalarMultNonConst(u2, &X, &u2X) + secp256k1.AddNonConst(&u1G, &u2X, &Q) + + // Step 10. + // + // Fail if Q is the point at infinity. + // + // Either the signature or the pubkey recovery code must be invalid if the + // recovered pubkey is the point at infinity. + if (Q.X.IsZero() && Q.Y.IsZero()) || Q.Z.IsZero() { + return nil, false, errors.New("recovered pubkey is the point at infinity") + } + + // Notice that the public key is in affine coordinates. + Q.ToAffine() + pubKey := secp256k1.NewPublicKey(&Q.X, &Q.Y) + return pubKey, wasCompressed, nil +} |