// 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-4 and SEC 1, Version 2.0. // // Signatures generated by this package are not deterministic, but entropy is // mixed with the private key and the message, achieving the same level of // security in case of randomness source failure.
package ecdsa // [FIPS 186-4] references ANSI X9.62-2005 for the bulk of the ECDSA algorithm. // That standard is not freely available, which is a problem in an open source // implementation, because not only the implementer, but also any maintainer, // contributor, reviewer, auditor, and learner needs access to it. Instead, this // package references and follows the equivalent [SEC 1, Version 2.0]. // // [FIPS 186-4]: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf // [SEC 1, Version 2.0]: https://www.secg.org/sec1-v2.pdf import ( ) // 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. // ECDH returns k as a [ecdh.PublicKey]. It returns an error if the key is // invalid according to the definition of [ecdh.Curve.NewPublicKey], or if the // Curve is not supported by crypto/ecdh. func ( *PublicKey) () (*ecdh.PublicKey, error) { := curveToECDH(.Curve) if == nil { return nil, errors.New("ecdsa: unsupported curve by crypto/ecdh") } if !.Curve.IsOnCurve(.X, .Y) { return nil, errors.New("ecdsa: invalid public key") } return .NewPublicKey(elliptic.Marshal(.Curve, .X, .Y)) } // 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 bigIntEqual(.X, .X) && bigIntEqual(.Y, .Y) && // 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 } // ECDH returns k as a [ecdh.PrivateKey]. It returns an error if the key is // invalid according to the definition of [ecdh.Curve.NewPrivateKey], or if the // Curve is not supported by crypto/ecdh. func ( *PrivateKey) () (*ecdh.PrivateKey, error) { := curveToECDH(.Curve) if == nil { return nil, errors.New("ecdsa: unsupported curve by crypto/ecdh") } := (.Curve.Params().N.BitLen() + 7) / 8 if .D.BitLen() > *8 { return nil, errors.New("ecdsa: invalid private key") } return .NewPrivateKey(.D.FillBytes(make([]byte, ))) } func curveToECDH( elliptic.Curve) ecdh.Curve { switch { case elliptic.P256(): return ecdh.P256() case elliptic.P384(): return ecdh.P384() case elliptic.P521(): return ecdh.P521() default: return nil } } // 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) && bigIntEqual(.D, .D) } // bigIntEqual reports whether a and b are equal leaking only their bit length // through timing side-channels. func bigIntEqual(, *big.Int) bool { return subtle.ConstantTimeCompare(.Bytes(), .Bytes()) == 1 } // 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 can use the SignASN1 function in this package directly. func ( *PrivateKey) ( io.Reader, []byte, crypto.SignerOpts) ([]byte, error) { return SignASN1(, , ) } // GenerateKey generates a public and private key pair. func ( elliptic.Curve, io.Reader) (*PrivateKey, error) { randutil.MaybeReadByte() if boring.Enabled && == boring.RandReader { , , , := boring.GenerateKeyECDSA(.Params().Name) if != nil { return nil, } return &PrivateKey{PublicKey: PublicKey{Curve: , X: bbig.Dec(), Y: bbig.Dec()}, D: bbig.Dec()}, nil } boring.UnreachableExceptTests() switch .Params() { case elliptic.P224().Params(): return generateNISTEC(p224(), ) case elliptic.P256().Params(): return generateNISTEC(p256(), ) case elliptic.P384().Params(): return generateNISTEC(p384(), ) case elliptic.P521().Params(): return generateNISTEC(p521(), ) default: return generateLegacy(, ) } } func generateNISTEC[ nistPoint[]]( *nistCurve[], io.Reader) (*PrivateKey, error) { , , := randomPoint(, ) if != nil { return nil, } := new(PrivateKey) .PublicKey.Curve = .curve .D = new(big.Int).SetBytes(.Bytes(.N)) .PublicKey.X, .PublicKey.Y, = .pointToAffine() if != nil { return nil, } return , nil } // randomPoint returns a random scalar and the corresponding point using the // procedure given in FIPS 186-4, Appendix B.5.2 (rejection sampling). func randomPoint[ nistPoint[]]( *nistCurve[], io.Reader) ( *bigmod.Nat, , error) { = bigmod.NewNat() for { := make([]byte, .N.Size()) if _, = io.ReadFull(, ); != nil { return } // Mask off any excess bits to increase the chance of hitting a value in // (0, N). These are the most dangerous lines in the package and maybe in // the library: a single bit of bias in the selection of nonces would likely // lead to key recovery, but no tests would fail. Look but DO NOT TOUCH. if := len()*8 - .N.BitLen(); > 0 { // Just to be safe, assert that this only happens for the one curve that // doesn't have a round number of bits. if != 0 && .curve.Params().Name != "P-521" { panic("ecdsa: internal error: unexpectedly masking off bits") } [0] >>= } // FIPS 186-4 makes us check k <= N - 2 and then add one. // Checking 0 < k <= N - 1 is strictly equivalent. // None of this matters anyway because the chance of selecting // zero is cryptographically negligible. if _, = .SetBytes(, .N); == nil && .IsZero() == 0 { break } if testingOnlyRejectionSamplingLooped != nil { testingOnlyRejectionSamplingLooped() } } , = .newPoint().ScalarBaseMult(.Bytes(.N)) return } // testingOnlyRejectionSamplingLooped is called when rejection sampling in // randomPoint rejects a candidate for being higher than the modulus. var testingOnlyRejectionSamplingLooped func() // errNoAsm is returned by signAsm and verifyAsm when the assembly // implementation is not available. var errNoAsm = errors.New("no assembly implementation available") // 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. func ( io.Reader, *PrivateKey, []byte) ([]byte, error) { randutil.MaybeReadByte() if boring.Enabled && == boring.RandReader { , := boringPrivateKey() if != nil { return nil, } return boring.SignMarshalECDSA(, ) } boring.UnreachableExceptTests() , := mixedCSPRNG(, , ) if != nil { return nil, } if , := signAsm(, , ); != errNoAsm { return , } switch .Curve.Params() { case elliptic.P224().Params(): return signNISTEC(p224(), , , ) case elliptic.P256().Params(): return signNISTEC(p256(), , , ) case elliptic.P384().Params(): return signNISTEC(p384(), , , ) case elliptic.P521().Params(): return signNISTEC(p521(), , , ) default: return signLegacy(, , ) } } func signNISTEC[ nistPoint[]]( *nistCurve[], *PrivateKey, io.Reader, []byte) ( []byte, error) { // SEC 1, Version 2.0, Section 4.1.3 , , := randomPoint(, ) if != nil { return nil, } // kInv = k⁻¹ := bigmod.NewNat() inverse(, , ) , := .BytesX() if != nil { return nil, } , := bigmod.NewNat().SetOverflowingBytes(, .N) if != nil { return nil, } // The spec wants us to retry here, but the chance of hitting this condition // on a large prime-order group like the NIST curves we support is // cryptographically negligible. If we hit it, something is awfully wrong. if .IsZero() == 1 { return nil, errors.New("ecdsa: internal error: r is zero") } := bigmod.NewNat() hashToNat(, , ) , := bigmod.NewNat().SetBytes(.D.Bytes(), .N) if != nil { return nil, } .Mul(, .N) .Add(, .N) .Mul(, .N) // Again, the chance of this happening is cryptographically negligible. if .IsZero() == 1 { return nil, errors.New("ecdsa: internal error: s is zero") } return encodeSignature(.Bytes(.N), .Bytes(.N)) } func encodeSignature(, []byte) ([]byte, error) { var cryptobyte.Builder .AddASN1(asn1.SEQUENCE, func( *cryptobyte.Builder) { addASN1IntBytes(, ) addASN1IntBytes(, ) }) return .Bytes() } // addASN1IntBytes encodes in ASN.1 a positive integer represented as // a big-endian byte slice with zero or more leading zeroes. func addASN1IntBytes( *cryptobyte.Builder, []byte) { for len() > 0 && [0] == 0 { = [1:] } if len() == 0 { .SetError(errors.New("invalid integer")) return } .AddASN1(asn1.INTEGER, func( *cryptobyte.Builder) { if [0]&0x80 != 0 { .AddUint8(0) } .AddBytes() }) } // inverse sets kInv to the inverse of k modulo the order of the curve. func inverse[ nistPoint[]]( *nistCurve[], , *bigmod.Nat) { if .curve.Params().Name == "P-256" { , := nistec.P256OrdInverse(.Bytes(.N)) // Some platforms don't implement P256OrdInverse, and always return an error. if == nil { , := .SetBytes(, .N) if != nil { panic("ecdsa: internal error: P256OrdInverse produced an invalid value") } return } } // Calculate the inverse of s in GF(N) using Fermat's method // (exponentiation modulo P - 2, per Euler's theorem) .Exp(, .nMinus2, .N) } // hashToNat sets e to the left-most bits of hash, according to // SEC 1, Section 4.1.3, point 5 and Section 4.1.4, point 3. func hashToNat[ nistPoint[]]( *nistCurve[], *bigmod.Nat, []byte) { // ECDSA asks us to take the left-most log2(N) bits of hash, and use them as // an integer modulo N. This is the absolute worst of all worlds: we still // have to reduce, because the result might still overflow N, but to take // the left-most bits for P-521 we have to do a right shift. if := .N.Size(); len() > { = [:] if := len()*8 - .N.BitLen(); > 0 { = bytes.Clone() for := len() - 1; >= 0; -- { [] >>= if > 0 { [] |= [-1] << (8 - ) } } } } , := .SetOverflowingBytes(, .N) if != nil { panic("ecdsa: internal error: truncated hash is too long") } } // mixedCSPRNG returns a CSPRNG that mixes entropy from rand with the message // and the private key, to protect the key in case rand fails. This is // equivalent in security to RFC 6979 deterministic nonce generation, but still // produces randomized signatures. func mixedCSPRNG( io.Reader, *PrivateKey, []byte) (io.Reader, error) { // 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). // // [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 // Get 256 bits of entropy from rand. := make([]byte, 32) if , := io.ReadFull(, ); != nil { return nil, } // 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, } // Create a CSPRNG that xors a stream of zeros with // the output of the AES-CTR instance. const = "IV for ECDSA CTR" return &cipher.StreamReader{ R: zeroReader, S: cipher.NewCTR(, []byte()), }, nil } type zr struct{} var zeroReader = zr{} // Read replaces the contents of dst with zeros. It is safe for concurrent use. func (zr) ( []byte) ( int, error) { for := range { [] = 0 } return len(), nil } // 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 { if boring.Enabled { , := boringPublicKey() if != nil { return false } return boring.VerifyECDSA(, , ) } boring.UnreachableExceptTests() if := verifyAsm(, , ); != errNoAsm { return == nil } switch .Curve.Params() { case elliptic.P224().Params(): return verifyNISTEC(p224(), , , ) case elliptic.P256().Params(): return verifyNISTEC(p256(), , , ) case elliptic.P384().Params(): return verifyNISTEC(p384(), , , ) case elliptic.P521().Params(): return verifyNISTEC(p521(), , , ) default: return verifyLegacy(, , ) } } func verifyNISTEC[ nistPoint[]]( *nistCurve[], *PublicKey, , []byte) bool { , , := parseSignature() if != nil { return false } , := .pointFromAffine(.X, .Y) if != nil { return false } // SEC 1, Version 2.0, Section 4.1.4 , := bigmod.NewNat().SetBytes(, .N) if != nil || .IsZero() == 1 { return false } , := bigmod.NewNat().SetBytes(, .N) if != nil || .IsZero() == 1 { return false } := bigmod.NewNat() hashToNat(, , ) // w = s⁻¹ := bigmod.NewNat() inverse(, , ) // p₁ = [e * s⁻¹]G , := .newPoint().ScalarBaseMult(.Mul(, .N).Bytes(.N)) if != nil { return false } // p₂ = [r * s⁻¹]Q , := .ScalarMult(, .Mul(, .N).Bytes(.N)) if != nil { return false } // BytesX returns an error for the point at infinity. , := .Add(, ).BytesX() if != nil { return false } , := bigmod.NewNat().SetOverflowingBytes(, .N) if != nil { return false } return .Equal() == 1 } func parseSignature( []byte) (, []byte, error) { var cryptobyte.String := cryptobyte.String() if !.ReadASN1(&, asn1.SEQUENCE) || !.Empty() || !.ReadASN1Integer(&) || !.ReadASN1Integer(&) || !.Empty() { return nil, nil, errors.New("invalid ASN.1") } return , , nil } type nistCurve[ nistPoint[]] struct { newPoint func() curve elliptic.Curve N *bigmod.Modulus nMinus2 []byte } // nistPoint is a generic constraint for the nistec Point types. type nistPoint[ any] interface { Bytes() []byte BytesX() ([]byte, error) SetBytes([]byte) (, error) Add(, ) ScalarMult(, []byte) (, error) ScalarBaseMult([]byte) (, error) } // pointFromAffine is used to convert the PublicKey to a nistec Point. func ( *nistCurve[]) (, *big.Int) ( , error) { := .curve.Params().BitSize // Reject values that would not get correctly encoded. if .Sign() < 0 || .Sign() < 0 { return , errors.New("negative coordinate") } if .BitLen() > || .BitLen() > { return , errors.New("overflowing coordinate") } // Encode the coordinates and let SetBytes reject invalid points. := ( + 7) / 8 := make([]byte, 1+2*) [0] = 4 // uncompressed point .FillBytes([1 : 1+]) .FillBytes([1+ : 1+2*]) return .newPoint().SetBytes() } // pointToAffine is used to convert a nistec Point to a PublicKey. func ( *nistCurve[]) ( ) (, *big.Int, error) { := .Bytes() if len() == 1 && [0] == 0 { // This is the encoding of the point at infinity. return nil, nil, errors.New("ecdsa: public key point is the infinity") } := (.curve.Params().BitSize + 7) / 8 = new(big.Int).SetBytes([1 : 1+]) = new(big.Int).SetBytes([1+:]) return , , nil } var p224Once sync.Once var _p224 *nistCurve[*nistec.P224Point] func p224() *nistCurve[*nistec.P224Point] { p224Once.Do(func() { _p224 = &nistCurve[*nistec.P224Point]{ newPoint: func() *nistec.P224Point { return nistec.NewP224Point() }, } precomputeParams(_p224, elliptic.P224()) }) return _p224 } var p256Once sync.Once var _p256 *nistCurve[*nistec.P256Point] func p256() *nistCurve[*nistec.P256Point] { p256Once.Do(func() { _p256 = &nistCurve[*nistec.P256Point]{ newPoint: func() *nistec.P256Point { return nistec.NewP256Point() }, } precomputeParams(_p256, elliptic.P256()) }) return _p256 } var p384Once sync.Once var _p384 *nistCurve[*nistec.P384Point] func p384() *nistCurve[*nistec.P384Point] { p384Once.Do(func() { _p384 = &nistCurve[*nistec.P384Point]{ newPoint: func() *nistec.P384Point { return nistec.NewP384Point() }, } precomputeParams(_p384, elliptic.P384()) }) return _p384 } var p521Once sync.Once var _p521 *nistCurve[*nistec.P521Point] func p521() *nistCurve[*nistec.P521Point] { p521Once.Do(func() { _p521 = &nistCurve[*nistec.P521Point]{ newPoint: func() *nistec.P521Point { return nistec.NewP521Point() }, } precomputeParams(_p521, elliptic.P521()) }) return _p521 } func precomputeParams[ nistPoint[]]( *nistCurve[], elliptic.Curve) { := .Params() .curve = .N = bigmod.NewModulusFromBig(.N) .nMinus2 = new(big.Int).Sub(.N, big.NewInt(2)).Bytes() }