ecdsa.go

     1  // Copyright 2011 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Package ecdsa implements the Elliptic Curve Digital Signature Algorithm, as
     6  // defined in [FIPS 186-5].
     7  //
     8  // Signatures generated by this package are not deterministic, but entropy is
     9  // mixed with the private key and the message, achieving the same level of
    10  // security in case of randomness source failure.
    11  //
    12  // Operations involving private keys are implemented using constant-time
    13  // algorithms, as long as an [elliptic.Curve] returned by [elliptic.P224],
    14  // [elliptic.P256], [elliptic.P384], or [elliptic.P521] is used.
    15  //
    16  // [FIPS 186-5]: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf
    17  package ecdsa
    18  
    19  import (
    20  	"crypto"
    21  	"crypto/ecdh"
    22  	"crypto/elliptic"
    23  	"crypto/internal/boring"
    24  	"crypto/internal/boring/bbig"
    25  	"crypto/internal/fips140/ecdsa"
    26  	"crypto/internal/fips140hash"
    27  	"crypto/internal/fips140only"
    28  	"crypto/internal/randutil"
    29  	"crypto/sha512"
    30  	"crypto/subtle"
    31  	"errors"
    32  	"io"
    33  	"math/big"
    34  
    35  	"golang.org/x/crypto/cryptobyte"
    36  	"golang.org/x/crypto/cryptobyte/asn1"
    37  )
    38  
    39  // PublicKey represents an ECDSA public key.
    40  type PublicKey struct {
    41  	elliptic.Curve
    42  	X, Y *big.Int
    43  }
    44  
    45  // Any methods implemented on PublicKey might need to also be implemented on
    46  // PrivateKey, as the latter embeds the former and will expose its methods.
    47  
    48  // ECDH returns k as a [ecdh.PublicKey]. It returns an error if the key is
    49  // invalid according to the definition of [ecdh.Curve.NewPublicKey], or if the
    50  // Curve is not supported by crypto/ecdh.
    51  func (k *PublicKey) ECDH() (*ecdh.PublicKey, error) {
    52  	c := curveToECDH(k.Curve)
    53  	if c == nil {
    54  		return nil, errors.New("ecdsa: unsupported curve by crypto/ecdh")
    55  	}
    56  	if !k.Curve.IsOnCurve(k.X, k.Y) {
    57  		return nil, errors.New("ecdsa: invalid public key")
    58  	}
    59  	return c.NewPublicKey(elliptic.Marshal(k.Curve, k.X, k.Y))
    60  }
    61  
    62  // Equal reports whether pub and x have the same value.
    63  //
    64  // Two keys are only considered to have the same value if they have the same Curve value.
    65  // Note that for example [elliptic.P256] and elliptic.P256().Params() are different
    66  // values, as the latter is a generic not constant time implementation.
    67  func (pub *PublicKey) Equal(x crypto.PublicKey) bool {
    68  	xx, ok := x.(*PublicKey)
    69  	if !ok {
    70  		return false
    71  	}
    72  	return bigIntEqual(pub.X, xx.X) && bigIntEqual(pub.Y, xx.Y) &&
    73  		// Standard library Curve implementations are singletons, so this check
    74  		// will work for those. Other Curves might be equivalent even if not
    75  		// singletons, but there is no definitive way to check for that, and
    76  		// better to err on the side of safety.
    77  		pub.Curve == xx.Curve
    78  }
    79  
    80  // PrivateKey represents an ECDSA private key.
    81  type PrivateKey struct {
    82  	PublicKey
    83  	D *big.Int
    84  }
    85  
    86  // ECDH returns k as a [ecdh.PrivateKey]. It returns an error if the key is
    87  // invalid according to the definition of [ecdh.Curve.NewPrivateKey], or if the
    88  // Curve is not supported by [crypto/ecdh].
    89  func (k *PrivateKey) ECDH() (*ecdh.PrivateKey, error) {
    90  	c := curveToECDH(k.Curve)
    91  	if c == nil {
    92  		return nil, errors.New("ecdsa: unsupported curve by crypto/ecdh")
    93  	}
    94  	size := (k.Curve.Params().N.BitLen() + 7) / 8
    95  	if k.D.BitLen() > size*8 {
    96  		return nil, errors.New("ecdsa: invalid private key")
    97  	}
    98  	return c.NewPrivateKey(k.D.FillBytes(make([]byte, size)))
    99  }
   100  
   101  func curveToECDH(c elliptic.Curve) ecdh.Curve {
   102  	switch c {
   103  	case elliptic.P256():
   104  		return ecdh.P256()
   105  	case elliptic.P384():
   106  		return ecdh.P384()
   107  	case elliptic.P521():
   108  		return ecdh.P521()
   109  	default:
   110  		return nil
   111  	}
   112  }
   113  
   114  // Public returns the public key corresponding to priv.
   115  func (priv *PrivateKey) Public() crypto.PublicKey {
   116  	return &priv.PublicKey
   117  }
   118  
   119  // Equal reports whether priv and x have the same value.
   120  //
   121  // See [PublicKey.Equal] for details on how Curve is compared.
   122  func (priv *PrivateKey) Equal(x crypto.PrivateKey) bool {
   123  	xx, ok := x.(*PrivateKey)
   124  	if !ok {
   125  		return false
   126  	}
   127  	return priv.PublicKey.Equal(&xx.PublicKey) && bigIntEqual(priv.D, xx.D)
   128  }
   129  
   130  // bigIntEqual reports whether a and b are equal leaking only their bit length
   131  // through timing side-channels.
   132  func bigIntEqual(a, b *big.Int) bool {
   133  	return subtle.ConstantTimeCompare(a.Bytes(), b.Bytes()) == 1
   134  }
   135  
   136  // Sign signs a hash (which should be the result of hashing a larger message
   137  // with opts.HashFunc()) using the private key, priv. If the hash is longer than
   138  // the bit-length of the private key's curve order, the hash will be truncated
   139  // to that length. It returns the ASN.1 encoded signature, like [SignASN1].
   140  //
   141  // If rand is not nil, the signature is randomized. Most applications should use
   142  // [crypto/rand.Reader] as rand. Note that the returned signature does not
   143  // depend deterministically on the bytes read from rand, and may change between
   144  // calls and/or between versions.
   145  //
   146  // If rand is nil, Sign will produce a deterministic signature according to RFC
   147  // 6979. When producing a deterministic signature, opts.HashFunc() must be the
   148  // function used to produce digest and priv.Curve must be one of
   149  // [elliptic.P224], [elliptic.P256], [elliptic.P384], or [elliptic.P521].
   150  func (priv *PrivateKey) Sign(rand io.Reader, digest []byte, opts crypto.SignerOpts) ([]byte, error) {
   151  	if rand == nil {
   152  		return signRFC6979(priv, digest, opts)
   153  	}
   154  	return SignASN1(rand, priv, digest)
   155  }
   156  
   157  // GenerateKey generates a new ECDSA private key for the specified curve.
   158  //
   159  // Most applications should use [crypto/rand.Reader] as rand. Note that the
   160  // returned key does not depend deterministically on the bytes read from rand,
   161  // and may change between calls and/or between versions.
   162  func GenerateKey(c elliptic.Curve, rand io.Reader) (*PrivateKey, error) {
   163  	randutil.MaybeReadByte(rand)
   164  
   165  	if boring.Enabled && rand == boring.RandReader {
   166  		x, y, d, err := boring.GenerateKeyECDSA(c.Params().Name)
   167  		if err != nil {
   168  			return nil, err
   169  		}
   170  		return &PrivateKey{PublicKey: PublicKey{Curve: c, X: bbig.Dec(x), Y: bbig.Dec(y)}, D: bbig.Dec(d)}, nil
   171  	}
   172  	boring.UnreachableExceptTests()
   173  
   174  	switch c.Params() {
   175  	case elliptic.P224().Params():
   176  		return generateFIPS(c, ecdsa.P224(), rand)
   177  	case elliptic.P256().Params():
   178  		return generateFIPS(c, ecdsa.P256(), rand)
   179  	case elliptic.P384().Params():
   180  		return generateFIPS(c, ecdsa.P384(), rand)
   181  	case elliptic.P521().Params():
   182  		return generateFIPS(c, ecdsa.P521(), rand)
   183  	default:
   184  		return generateLegacy(c, rand)
   185  	}
   186  }
   187  
   188  func generateFIPS[P ecdsa.Point[P]](curve elliptic.Curve, c *ecdsa.Curve[P], rand io.Reader) (*PrivateKey, error) {
   189  	if fips140only.Enabled && !fips140only.ApprovedRandomReader(rand) {
   190  		return nil, errors.New("crypto/ecdsa: only crypto/rand.Reader is allowed in FIPS 140-only mode")
   191  	}
   192  	privateKey, err := ecdsa.GenerateKey(c, rand)
   193  	if err != nil {
   194  		return nil, err
   195  	}
   196  	return privateKeyFromFIPS(curve, privateKey)
   197  }
   198  
   199  // errNoAsm is returned by signAsm and verifyAsm when the assembly
   200  // implementation is not available.
   201  var errNoAsm = errors.New("no assembly implementation available")
   202  
   203  // SignASN1 signs a hash (which should be the result of hashing a larger message)
   204  // using the private key, priv. If the hash is longer than the bit-length of the
   205  // private key's curve order, the hash will be truncated to that length. It
   206  // returns the ASN.1 encoded signature.
   207  //
   208  // The signature is randomized. Most applications should use [crypto/rand.Reader]
   209  // as rand. Note that the returned signature does not depend deterministically on
   210  // the bytes read from rand, and may change between calls and/or between versions.
   211  func SignASN1(rand io.Reader, priv *PrivateKey, hash []byte) ([]byte, error) {
   212  	randutil.MaybeReadByte(rand)
   213  
   214  	if boring.Enabled && rand == boring.RandReader {
   215  		b, err := boringPrivateKey(priv)
   216  		if err != nil {
   217  			return nil, err
   218  		}
   219  		return boring.SignMarshalECDSA(b, hash)
   220  	}
   221  	boring.UnreachableExceptTests()
   222  
   223  	switch priv.Curve.Params() {
   224  	case elliptic.P224().Params():
   225  		return signFIPS(ecdsa.P224(), priv, rand, hash)
   226  	case elliptic.P256().Params():
   227  		return signFIPS(ecdsa.P256(), priv, rand, hash)
   228  	case elliptic.P384().Params():
   229  		return signFIPS(ecdsa.P384(), priv, rand, hash)
   230  	case elliptic.P521().Params():
   231  		return signFIPS(ecdsa.P521(), priv, rand, hash)
   232  	default:
   233  		return signLegacy(priv, rand, hash)
   234  	}
   235  }
   236  
   237  func signFIPS[P ecdsa.Point[P]](c *ecdsa.Curve[P], priv *PrivateKey, rand io.Reader, hash []byte) ([]byte, error) {
   238  	if fips140only.Enabled && !fips140only.ApprovedRandomReader(rand) {
   239  		return nil, errors.New("crypto/ecdsa: only crypto/rand.Reader is allowed in FIPS 140-only mode")
   240  	}
   241  	// privateKeyToFIPS is very slow in FIPS mode because it performs a
   242  	// Sign+Verify cycle per FIPS 140-3 IG 10.3.A. We should find a way to cache
   243  	// it or attach it to the PrivateKey.
   244  	k, err := privateKeyToFIPS(c, priv)
   245  	if err != nil {
   246  		return nil, err
   247  	}
   248  	// Always using SHA-512 instead of the hash that computed hash is
   249  	// technically a violation of draft-irtf-cfrg-det-sigs-with-noise-04 but in
   250  	// our API we don't get to know what it was, and this has no security impact.
   251  	sig, err := ecdsa.Sign(c, sha512.New, k, rand, hash)
   252  	if err != nil {
   253  		return nil, err
   254  	}
   255  	return encodeSignature(sig.R, sig.S)
   256  }
   257  
   258  func signRFC6979(priv *PrivateKey, hash []byte, opts crypto.SignerOpts) ([]byte, error) {
   259  	if opts == nil {
   260  		return nil, errors.New("ecdsa: Sign called with nil opts")
   261  	}
   262  	h := opts.HashFunc()
   263  	if h.Size() != len(hash) {
   264  		return nil, errors.New("ecdsa: hash length does not match hash function")
   265  	}
   266  	switch priv.Curve.Params() {
   267  	case elliptic.P224().Params():
   268  		return signFIPSDeterministic(ecdsa.P224(), h, priv, hash)
   269  	case elliptic.P256().Params():
   270  		return signFIPSDeterministic(ecdsa.P256(), h, priv, hash)
   271  	case elliptic.P384().Params():
   272  		return signFIPSDeterministic(ecdsa.P384(), h, priv, hash)
   273  	case elliptic.P521().Params():
   274  		return signFIPSDeterministic(ecdsa.P521(), h, priv, hash)
   275  	default:
   276  		return nil, errors.New("ecdsa: curve not supported by deterministic signatures")
   277  	}
   278  }
   279  
   280  func signFIPSDeterministic[P ecdsa.Point[P]](c *ecdsa.Curve[P], hashFunc crypto.Hash, priv *PrivateKey, hash []byte) ([]byte, error) {
   281  	k, err := privateKeyToFIPS(c, priv)
   282  	if err != nil {
   283  		return nil, err
   284  	}
   285  	h := fips140hash.UnwrapNew(hashFunc.New)
   286  	if fips140only.Enabled && !fips140only.ApprovedHash(h()) {
   287  		return nil, errors.New("crypto/ecdsa: use of hash functions other than SHA-2 or SHA-3 is not allowed in FIPS 140-only mode")
   288  	}
   289  	sig, err := ecdsa.SignDeterministic(c, h, k, hash)
   290  	if err != nil {
   291  		return nil, err
   292  	}
   293  	return encodeSignature(sig.R, sig.S)
   294  }
   295  
   296  func encodeSignature(r, s []byte) ([]byte, error) {
   297  	var b cryptobyte.Builder
   298  	b.AddASN1(asn1.SEQUENCE, func(b *cryptobyte.Builder) {
   299  		addASN1IntBytes(b, r)
   300  		addASN1IntBytes(b, s)
   301  	})
   302  	return b.Bytes()
   303  }
   304  
   305  // addASN1IntBytes encodes in ASN.1 a positive integer represented as
   306  // a big-endian byte slice with zero or more leading zeroes.
   307  func addASN1IntBytes(b *cryptobyte.Builder, bytes []byte) {
   308  	for len(bytes) > 0 && bytes[0] == 0 {
   309  		bytes = bytes[1:]
   310  	}
   311  	if len(bytes) == 0 {
   312  		b.SetError(errors.New("invalid integer"))
   313  		return
   314  	}
   315  	b.AddASN1(asn1.INTEGER, func(c *cryptobyte.Builder) {
   316  		if bytes[0]&0x80 != 0 {
   317  			c.AddUint8(0)
   318  		}
   319  		c.AddBytes(bytes)
   320  	})
   321  }
   322  
   323  // VerifyASN1 verifies the ASN.1 encoded signature, sig, of hash using the
   324  // public key, pub. Its return value records whether the signature is valid.
   325  //
   326  // The inputs are not considered confidential, and may leak through timing side
   327  // channels, or if an attacker has control of part of the inputs.
   328  func VerifyASN1(pub *PublicKey, hash, sig []byte) bool {
   329  	if boring.Enabled {
   330  		key, err := boringPublicKey(pub)
   331  		if err != nil {
   332  			return false
   333  		}
   334  		return boring.VerifyECDSA(key, hash, sig)
   335  	}
   336  	boring.UnreachableExceptTests()
   337  
   338  	switch pub.Curve.Params() {
   339  	case elliptic.P224().Params():
   340  		return verifyFIPS(ecdsa.P224(), pub, hash, sig)
   341  	case elliptic.P256().Params():
   342  		return verifyFIPS(ecdsa.P256(), pub, hash, sig)
   343  	case elliptic.P384().Params():
   344  		return verifyFIPS(ecdsa.P384(), pub, hash, sig)
   345  	case elliptic.P521().Params():
   346  		return verifyFIPS(ecdsa.P521(), pub, hash, sig)
   347  	default:
   348  		return verifyLegacy(pub, hash, sig)
   349  	}
   350  }
   351  
   352  func verifyFIPS[P ecdsa.Point[P]](c *ecdsa.Curve[P], pub *PublicKey, hash, sig []byte) bool {
   353  	r, s, err := parseSignature(sig)
   354  	if err != nil {
   355  		return false
   356  	}
   357  	k, err := publicKeyToFIPS(c, pub)
   358  	if err != nil {
   359  		return false
   360  	}
   361  	if err := ecdsa.Verify(c, k, hash, &ecdsa.Signature{R: r, S: s}); err != nil {
   362  		return false
   363  	}
   364  	return true
   365  }
   366  
   367  func parseSignature(sig []byte) (r, s []byte, err error) {
   368  	var inner cryptobyte.String
   369  	input := cryptobyte.String(sig)
   370  	if !input.ReadASN1(&inner, asn1.SEQUENCE) ||
   371  		!input.Empty() ||
   372  		!inner.ReadASN1Integer(&r) ||
   373  		!inner.ReadASN1Integer(&s) ||
   374  		!inner.Empty() {
   375  		return nil, nil, errors.New("invalid ASN.1")
   376  	}
   377  	return r, s, nil
   378  }
   379  
   380  func publicKeyFromFIPS(curve elliptic.Curve, pub *ecdsa.PublicKey) (*PublicKey, error) {
   381  	x, y, err := pointToAffine(curve, pub.Bytes())
   382  	if err != nil {
   383  		return nil, err
   384  	}
   385  	return &PublicKey{Curve: curve, X: x, Y: y}, nil
   386  }
   387  
   388  func privateKeyFromFIPS(curve elliptic.Curve, priv *ecdsa.PrivateKey) (*PrivateKey, error) {
   389  	pub, err := publicKeyFromFIPS(curve, priv.PublicKey())
   390  	if err != nil {
   391  		return nil, err
   392  	}
   393  	return &PrivateKey{PublicKey: *pub, D: new(big.Int).SetBytes(priv.Bytes())}, nil
   394  }
   395  
   396  func publicKeyToFIPS[P ecdsa.Point[P]](c *ecdsa.Curve[P], pub *PublicKey) (*ecdsa.PublicKey, error) {
   397  	Q, err := pointFromAffine(pub.Curve, pub.X, pub.Y)
   398  	if err != nil {
   399  		return nil, err
   400  	}
   401  	return ecdsa.NewPublicKey(c, Q)
   402  }
   403  
   404  func privateKeyToFIPS[P ecdsa.Point[P]](c *ecdsa.Curve[P], priv *PrivateKey) (*ecdsa.PrivateKey, error) {
   405  	Q, err := pointFromAffine(priv.Curve, priv.X, priv.Y)
   406  	if err != nil {
   407  		return nil, err
   408  	}
   409  	return ecdsa.NewPrivateKey(c, priv.D.Bytes(), Q)
   410  }
   411  
   412  // pointFromAffine is used to convert the PublicKey to a nistec SetBytes input.
   413  func pointFromAffine(curve elliptic.Curve, x, y *big.Int) ([]byte, error) {
   414  	bitSize := curve.Params().BitSize
   415  	// Reject values that would not get correctly encoded.
   416  	if x.Sign() < 0 || y.Sign() < 0 {
   417  		return nil, errors.New("negative coordinate")
   418  	}
   419  	if x.BitLen() > bitSize || y.BitLen() > bitSize {
   420  		return nil, errors.New("overflowing coordinate")
   421  	}
   422  	// Encode the coordinates and let SetBytes reject invalid points.
   423  	byteLen := (bitSize + 7) / 8
   424  	buf := make([]byte, 1+2*byteLen)
   425  	buf[0] = 4 // uncompressed point
   426  	x.FillBytes(buf[1 : 1+byteLen])
   427  	y.FillBytes(buf[1+byteLen : 1+2*byteLen])
   428  	return buf, nil
   429  }
   430  
   431  // pointToAffine is used to convert a nistec Bytes encoding to a PublicKey.
   432  func pointToAffine(curve elliptic.Curve, p []byte) (x, y *big.Int, err error) {
   433  	if len(p) == 1 && p[0] == 0 {
   434  		// This is the encoding of the point at infinity.
   435  		return nil, nil, errors.New("ecdsa: public key point is the infinity")
   436  	}
   437  	byteLen := (curve.Params().BitSize + 7) / 8
   438  	x = new(big.Int).SetBytes(p[1 : 1+byteLen])
   439  	y = new(big.Int).SetBytes(p[1+byteLen:])
   440  	return x, y, nil
   441  }
   442
View as plain text