// 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 ( ) // 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 ( *PublicKey) ( crypto.PublicKey) bool { , := .(*PublicKey) if ! { return false } return .X.Cmp(.X) == 0 && .Y.Cmp(.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. .Curve == .Curve } // PrivateKey represents an ECDSA private key. type PrivateKey struct { PublicKey D *big.Int } // Public returns the public key corresponding to priv. func ( *PrivateKey) () crypto.PublicKey { return &.PublicKey } // Equal reports whether priv and x have the same value. // // See PublicKey.Equal for details on how Curve is compared. func ( *PrivateKey) ( crypto.PrivateKey) bool { , := .(*PrivateKey) if ! { return false } return .PublicKey.Equal(&.PublicKey) && .D.Cmp(.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 ( *PrivateKey) ( io.Reader, []byte, crypto.SignerOpts) ([]byte, error) { , , := Sign(, , ) if != nil { return nil, } var cryptobyte.Builder .AddASN1(asn1.SEQUENCE, func( *cryptobyte.Builder) { .AddASN1BigInt() .AddASN1BigInt() }) return .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( elliptic.Curve, io.Reader) ( *big.Int, error) { := .Params() := make([]byte, .BitSize/8+8) _, = io.ReadFull(, ) if != nil { return } = new(big.Int).SetBytes() := new(big.Int).Sub(.N, one) .Mod(, ) .Add(, one) return } // GenerateKey generates a public and private key pair. func ( elliptic.Curve, io.Reader) (*PrivateKey, error) { , := randFieldElement(, ) if != nil { return nil, } := new(PrivateKey) .PublicKey.Curve = .D = .PublicKey.X, .PublicKey.Y = .ScalarBaseMult(.Bytes()) 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. func hashToInt( []byte, elliptic.Curve) *big.Int { := .Params().N.BitLen() := ( + 7) / 8 if len() > { = [:] } := new(big.Int).SetBytes() := len()*8 - if > 0 { .Rsh(, uint()) } return } // 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(, *big.Int) *big.Int { := big.NewInt(2) := new(big.Int).Sub(, ) return new(big.Int).Exp(, , ) } 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 ( io.Reader, *PrivateKey, []byte) (, *big.Int, error) { randutil.MaybeReadByte() // Get min(log2(q) / 2, 256) bits of entropy from rand. := (.Curve.Params().BitSize + 7) / 16 if > 32 { = 32 } := make([]byte, ) _, = io.ReadFull(, ) if != nil { return } // Initialize an SHA-512 hash context; digest ... := sha512.New() .Write(.D.Bytes()) // the private key, .Write() // the entropy, .Write() // and the input hash; := .Sum(nil)[:32] // and compute ChopMD-256(SHA-512), // which is an indifferentiable MAC. // Create an AES-CTR instance to use as a CSPRNG. , := aes.NewCipher() if != nil { return nil, nil, } // Create a CSPRNG that xors a stream of zeros with // the output of the AES-CTR instance. := cipher.StreamReader{ R: zeroReader, S: cipher.NewCTR(, []byte(aesIV)), } // See [NSA] 3.4.1 := .PublicKey.Curve return sign(, &, , ) } func signGeneric( *PrivateKey, *cipher.StreamReader, elliptic.Curve, []byte) (, *big.Int, error) { := .Params().N if .Sign() == 0 { return nil, nil, errZeroParam } var , *big.Int for { for { , = randFieldElement(, *) if != nil { = nil return } if , := .Curve.(invertible); { = .Inverse() } else { = fermatInverse(, ) // N != 0 } , _ = .Curve.ScalarBaseMult(.Bytes()) .Mod(, ) if .Sign() != 0 { break } } := hashToInt(, ) = new(big.Int).Mul(.D, ) .Add(, ) .Mul(, ) .Mod(, ) // N != 0 if .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 ( io.Reader, *PrivateKey, []byte) ([]byte, error) { return .Sign(, , 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 ( *PublicKey, []byte, , *big.Int) bool { // See [NSA] 3.4.2 := .Curve := .Params().N if .Sign() <= 0 || .Sign() <= 0 { return false } if .Cmp() >= 0 || .Cmp() >= 0 { return false } return verify(, , , , ) } func verifyGeneric( *PublicKey, elliptic.Curve, []byte, , *big.Int) bool { := hashToInt(, ) var *big.Int := .Params().N if , := .(invertible); { = .Inverse() } else { = new(big.Int).ModInverse(, ) } := .Mul(, ) .Mod(, ) := .Mul(, ) .Mod(, ) // Check if implements S1*g + S2*p var , *big.Int if , := .(combinedMult); { , = .CombinedMult(.X, .Y, .Bytes(), .Bytes()) } else { , := .ScalarBaseMult(.Bytes()) , := .ScalarMult(.X, .Y, .Bytes()) , = .Add(, , , ) } if .Sign() == 0 && .Sign() == 0 { return false } .Mod(, ) return .Cmp() == 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 ( *PublicKey, , []byte) bool { var ( , = &big.Int{}, &big.Int{} cryptobyte.String ) := cryptobyte.String() if !.ReadASN1(&, asn1.SEQUENCE) || !.Empty() || !.ReadASN1Integer() || !.ReadASN1Integer() || !.Empty() { return false } return Verify(, , , ) } type zr struct { io.Reader } // Read replaces the contents of dst with zeros. func ( *zr) ( []byte) ( int, error) { for := range { [] = 0 } return len(), nil } var zeroReader = &zr{}