// Copyright 2011 The Go Authors. All rights reserved. // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. // Package ecdsa implements the Elliptic Curve Digital Signature Algorithm, as // defined in FIPS 186-3. // // This implementation derives the nonce from an AES-CTR CSPRNG keyed by: // // SHA2-512(priv.D || entropy || hash)[:32] // // The CSPRNG key is indifferentiable from a random oracle as shown in // [Coron], the AES-CTR stream is indifferentiable from a random oracle // under standard cryptographic assumptions (see [Larsson] for examples). // // References: // [Coron] // https://cs.nyu.edu/~dodis/ps/merkle.pdf // [Larsson] // https://web.archive.org/web/20040719170906/https://www.nada.kth.se/kurser/kth/2D1441/semteo03/lecturenotes/assump.pdf package ecdsa // Further references: // [NSA]: Suite B implementer's guide to FIPS 186-3 // https://apps.nsa.gov/iaarchive/library/ia-guidance/ia-solutions-for-classified/algorithm-guidance/suite-b-implementers-guide-to-fips-186-3-ecdsa.cfm // [SECG]: SECG, SEC1 // http://www.secg.org/sec1-v2.pdf import ( "crypto" "crypto/aes" "crypto/cipher" "crypto/elliptic" "crypto/internal/randutil" "crypto/sha512" "errors" "io" "math/big" "golang.org/x/crypto/cryptobyte" "golang.org/x/crypto/cryptobyte/asn1" ) // A invertible implements fast inverse mod Curve.Params().N type invertible interface { // Inverse returns the inverse of k in GF(P) Inverse(k *big.Int) *big.Int } // combinedMult implements fast multiplication S1*g + S2*p (g - generator, p - arbitrary point) type combinedMult interface { CombinedMult(bigX, bigY *big.Int, baseScalar, scalar []byte) (x, y *big.Int) } const ( aesIV = "IV for ECDSA CTR" ) // PublicKey represents an ECDSA public key. type PublicKey struct { elliptic.Curve X, Y *big.Int } // Any methods implemented on PublicKey might need to also be implemented on // PrivateKey, as the latter embeds the former and will expose its methods. // Equal reports whether pub and x have the same value. // // Two keys are only considered to have the same value if they have the same Curve value. // Note that for example elliptic.P256() and elliptic.P256().Params() are different // values, as the latter is a generic not constant time implementation. func (pub *PublicKey) Equal(x crypto.PublicKey) bool { xx, ok := x.(*PublicKey) if !ok { return false } return pub.X.Cmp(xx.X) == 0 && pub.Y.Cmp(xx.Y) == 0 && // Standard library Curve implementations are singletons, so this check // will work for those. Other Curves might be equivalent even if not // singletons, but there is no definitive way to check for that, and // better to err on the side of safety. pub.Curve == xx.Curve } // PrivateKey represents an ECDSA private key. type PrivateKey struct { PublicKey D *big.Int } // Public returns the public key corresponding to priv. func (priv *PrivateKey) Public() crypto.PublicKey { return &priv.PublicKey } // Equal reports whether priv and x have the same value. // // See PublicKey.Equal for details on how Curve is compared. func (priv *PrivateKey) Equal(x crypto.PrivateKey) bool { xx, ok := x.(*PrivateKey) if !ok { return false } return priv.PublicKey.Equal(&xx.PublicKey) && priv.D.Cmp(xx.D) == 0 } // Sign signs digest with priv, reading randomness from rand. The opts argument // is not currently used but, in keeping with the crypto.Signer interface, // should be the hash function used to digest the message. // // This method implements crypto.Signer, which is an interface to support keys // where the private part is kept in, for example, a hardware module. Common // uses should use the Sign function in this package directly. func (priv *PrivateKey) Sign(rand io.Reader, digest []byte, opts crypto.SignerOpts) ([]byte, error) { r, s, err := Sign(rand, priv, digest) if err != nil { return nil, err } var b cryptobyte.Builder b.AddASN1(asn1.SEQUENCE, func(b *cryptobyte.Builder) { b.AddASN1BigInt(r) b.AddASN1BigInt(s) }) return b.Bytes() } var one = new(big.Int).SetInt64(1) // randFieldElement returns a random element of the field underlying the given // curve using the procedure given in [NSA] A.2.1. func randFieldElement(c elliptic.Curve, rand io.Reader) (k *big.Int, err error) { params := c.Params() b := make([]byte, params.BitSize/8+8) _, err = io.ReadFull(rand, b) if err != nil { return } k = new(big.Int).SetBytes(b) n := new(big.Int).Sub(params.N, one) k.Mod(k, n) k.Add(k, one) return } // GenerateKey generates a public and private key pair. func GenerateKey(c elliptic.Curve, rand io.Reader) (*PrivateKey, error) { k, err := randFieldElement(c, rand) if err != nil { return nil, err } priv := new(PrivateKey) priv.PublicKey.Curve = c priv.D = k priv.PublicKey.X, priv.PublicKey.Y = c.ScalarBaseMult(k.Bytes()) return priv, 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. 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 } // fermatInverse calculates the inverse of k in GF(P) using Fermat's method. // This has better constant-time properties than Euclid's method (implemented // in math/big.Int.ModInverse) although math/big itself isn't strictly // constant-time so it's not perfect. func fermatInverse(k, N *big.Int) *big.Int { two := big.NewInt(2) nMinus2 := new(big.Int).Sub(N, two) return new(big.Int).Exp(k, nMinus2, N) } var errZeroParam = errors.New("zero parameter") // Sign signs a hash (which should be the result of hashing a larger message) // using the private key, priv. If the hash is longer than the bit-length of the // private key's curve order, the hash will be truncated to that length. It // returns the signature as a pair of integers. The security of the private key // depends on the entropy of rand. func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) { randutil.MaybeReadByte(rand) // Get min(log2(q) / 2, 256) bits of entropy from rand. entropylen := (priv.Curve.Params().BitSize + 7) / 16 if entropylen > 32 { entropylen = 32 } entropy := make([]byte, entropylen) _, err = io.ReadFull(rand, entropy) if err != nil { return } // Initialize an SHA-512 hash context; digest ... md := sha512.New() md.Write(priv.D.Bytes()) // the private key, md.Write(entropy) // the entropy, md.Write(hash) // and the input hash; key := md.Sum(nil)[:32] // and compute ChopMD-256(SHA-512), // which is an indifferentiable MAC. // Create an AES-CTR instance to use as a CSPRNG. block, err := aes.NewCipher(key) if err != nil { return nil, nil, err } // Create a CSPRNG that xors a stream of zeros with // the output of the AES-CTR instance. csprng := cipher.StreamReader{ R: zeroReader, S: cipher.NewCTR(block, []byte(aesIV)), } // See [NSA] 3.4.1 c := priv.PublicKey.Curve return sign(priv, &csprng, c, hash) } func signGeneric(priv *PrivateKey, csprng *cipher.StreamReader, c elliptic.Curve, hash []byte) (r, s *big.Int, err error) { N := c.Params().N if N.Sign() == 0 { return nil, nil, errZeroParam } var k, kInv *big.Int for { for { k, err = randFieldElement(c, *csprng) if err != nil { r = nil return } if in, ok := priv.Curve.(invertible); ok { kInv = in.Inverse(k) } else { kInv = fermatInverse(k, N) // N != 0 } r, _ = priv.Curve.ScalarBaseMult(k.Bytes()) r.Mod(r, N) if r.Sign() != 0 { break } } e := hashToInt(hash, c) s = new(big.Int).Mul(priv.D, r) s.Add(s, e) s.Mul(s, kInv) s.Mod(s, N) // N != 0 if s.Sign() != 0 { break } } return } // SignASN1 signs a hash (which should be the result of hashing a larger message) // using the private key, priv. If the hash is longer than the bit-length of the // private key's curve order, the hash will be truncated to that length. It // returns the ASN.1 encoded signature. The security of the private key // depends on the entropy of rand. func SignASN1(rand io.Reader, priv *PrivateKey, hash []byte) ([]byte, error) { return priv.Sign(rand, hash, nil) } // Verify verifies the signature in r, s of hash using the public key, pub. Its // return value records whether the signature is valid. func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool { // See [NSA] 3.4.2 c := pub.Curve N := c.Params().N if r.Sign() <= 0 || s.Sign() <= 0 { return false } if r.Cmp(N) >= 0 || s.Cmp(N) >= 0 { return false } return verify(pub, c, hash, r, s) } func verifyGeneric(pub *PublicKey, c elliptic.Curve, hash []byte, r, s *big.Int) bool { e := hashToInt(hash, c) var w *big.Int N := c.Params().N if in, ok := c.(invertible); ok { w = in.Inverse(s) } else { w = new(big.Int).ModInverse(s, N) } u1 := e.Mul(e, w) u1.Mod(u1, N) u2 := w.Mul(r, w) u2.Mod(u2, N) // Check if implements S1*g + S2*p var x, y *big.Int if opt, ok := c.(combinedMult); ok { x, y = opt.CombinedMult(pub.X, pub.Y, u1.Bytes(), u2.Bytes()) } else { x1, y1 := c.ScalarBaseMult(u1.Bytes()) x2, y2 := c.ScalarMult(pub.X, pub.Y, u2.Bytes()) x, y = c.Add(x1, y1, x2, y2) } if x.Sign() == 0 && y.Sign() == 0 { return false } x.Mod(x, N) return x.Cmp(r) == 0 } // VerifyASN1 verifies the ASN.1 encoded signature, sig, of hash using the // public key, pub. Its return value records whether the signature is valid. func VerifyASN1(pub *PublicKey, hash, sig []byte) bool { var ( r, s = &big.Int{}, &big.Int{} inner cryptobyte.String ) input := cryptobyte.String(sig) if !input.ReadASN1(&inner, asn1.SEQUENCE) || !input.Empty() || !inner.ReadASN1Integer(r) || !inner.ReadASN1Integer(s) || !inner.Empty() { return false } return Verify(pub, hash, r, s) } type zr struct { io.Reader } // Read replaces the contents of dst with zeros. func (z *zr) Read(dst []byte) (n int, err error) { for i := range dst { dst[i] = 0 } return len(dst), nil } var zeroReader = &zr{}