ecdsa.go

     1  // Copyright 2024 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
     6  
     7  import (
     8  	"bytes"
     9  	"crypto/internal/fips140"
    10  	"crypto/internal/fips140/bigmod"
    11  	"crypto/internal/fips140/drbg"
    12  	"crypto/internal/fips140/nistec"
    13  	"errors"
    14  	"hash"
    15  	"io"
    16  	"sync"
    17  )
    18  
    19  // PrivateKey and PublicKey are not generic to make it possible to use them
    20  // in other types without instantiating them with a specific point type.
    21  // They are tied to one of the Curve types below through the curveID field.
    22  
    23  type PrivateKey struct {
    24  	pub PublicKey
    25  	d   []byte // bigmod.(*Nat).Bytes output (same length as the curve order)
    26  }
    27  
    28  func (priv *PrivateKey) Bytes() []byte {
    29  	return priv.d
    30  }
    31  
    32  func (priv *PrivateKey) PublicKey() *PublicKey {
    33  	return &priv.pub
    34  }
    35  
    36  type PublicKey struct {
    37  	curve curveID
    38  	q     []byte // uncompressed nistec Point.Bytes output
    39  }
    40  
    41  func (pub *PublicKey) Bytes() []byte {
    42  	return pub.q
    43  }
    44  
    45  type curveID string
    46  
    47  const (
    48  	p224 curveID = "P-224"
    49  	p256 curveID = "P-256"
    50  	p384 curveID = "P-384"
    51  	p521 curveID = "P-521"
    52  )
    53  
    54  type Curve[P Point[P]] struct {
    55  	curve      curveID
    56  	newPoint   func() P
    57  	ordInverse func([]byte) ([]byte, error)
    58  	N          *bigmod.Modulus
    59  	nMinus2    []byte
    60  }
    61  
    62  // Point is a generic constraint for the [nistec] Point types.
    63  type Point[P any] interface {
    64  	*nistec.P224Point | *nistec.P256Point | *nistec.P384Point | *nistec.P521Point
    65  	Bytes() []byte
    66  	BytesX() ([]byte, error)
    67  	SetBytes([]byte) (P, error)
    68  	ScalarMult(P, []byte) (P, error)
    69  	ScalarBaseMult([]byte) (P, error)
    70  	Add(p1, p2 P) P
    71  }
    72  
    73  func precomputeParams[P Point[P]](c *Curve[P], order []byte) {
    74  	var err error
    75  	c.N, err = bigmod.NewModulus(order)
    76  	if err != nil {
    77  		panic(err)
    78  	}
    79  	two, _ := bigmod.NewNat().SetBytes([]byte{2}, c.N)
    80  	c.nMinus2 = bigmod.NewNat().ExpandFor(c.N).Sub(two, c.N).Bytes(c.N)
    81  }
    82  
    83  func P224() *Curve[*nistec.P224Point] { return _P224() }
    84  
    85  var _P224 = sync.OnceValue(func() *Curve[*nistec.P224Point] {
    86  	c := &Curve[*nistec.P224Point]{
    87  		curve:    p224,
    88  		newPoint: nistec.NewP224Point,
    89  	}
    90  	precomputeParams(c, p224Order)
    91  	return c
    92  })
    93  
    94  var p224Order = []byte{
    95  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    96  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x16, 0xa2,
    97  	0xe0, 0xb8, 0xf0, 0x3e, 0x13, 0xdd, 0x29, 0x45,
    98  	0x5c, 0x5c, 0x2a, 0x3d,
    99  }
   100  
   101  func P256() *Curve[*nistec.P256Point] { return _P256() }
   102  
   103  var _P256 = sync.OnceValue(func() *Curve[*nistec.P256Point] {
   104  	c := &Curve[*nistec.P256Point]{
   105  		curve:      p256,
   106  		newPoint:   nistec.NewP256Point,
   107  		ordInverse: nistec.P256OrdInverse,
   108  	}
   109  	precomputeParams(c, p256Order)
   110  	return c
   111  })
   112  
   113  var p256Order = []byte{
   114  	0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
   115  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
   116  	0xbc, 0xe6, 0xfa, 0xad, 0xa7, 0x17, 0x9e, 0x84,
   117  	0xf3, 0xb9, 0xca, 0xc2, 0xfc, 0x63, 0x25, 0x51}
   118  
   119  func P384() *Curve[*nistec.P384Point] { return _P384() }
   120  
   121  var _P384 = sync.OnceValue(func() *Curve[*nistec.P384Point] {
   122  	c := &Curve[*nistec.P384Point]{
   123  		curve:    p384,
   124  		newPoint: nistec.NewP384Point,
   125  	}
   126  	precomputeParams(c, p384Order)
   127  	return c
   128  })
   129  
   130  var p384Order = []byte{
   131  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
   132  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
   133  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
   134  	0xc7, 0x63, 0x4d, 0x81, 0xf4, 0x37, 0x2d, 0xdf,
   135  	0x58, 0x1a, 0x0d, 0xb2, 0x48, 0xb0, 0xa7, 0x7a,
   136  	0xec, 0xec, 0x19, 0x6a, 0xcc, 0xc5, 0x29, 0x73}
   137  
   138  func P521() *Curve[*nistec.P521Point] { return _P521() }
   139  
   140  var _P521 = sync.OnceValue(func() *Curve[*nistec.P521Point] {
   141  	c := &Curve[*nistec.P521Point]{
   142  		curve:    p521,
   143  		newPoint: nistec.NewP521Point,
   144  	}
   145  	precomputeParams(c, p521Order)
   146  	return c
   147  })
   148  
   149  var p521Order = []byte{0x01, 0xff,
   150  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
   151  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
   152  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
   153  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfa,
   154  	0x51, 0x86, 0x87, 0x83, 0xbf, 0x2f, 0x96, 0x6b,
   155  	0x7f, 0xcc, 0x01, 0x48, 0xf7, 0x09, 0xa5, 0xd0,
   156  	0x3b, 0xb5, 0xc9, 0xb8, 0x89, 0x9c, 0x47, 0xae,
   157  	0xbb, 0x6f, 0xb7, 0x1e, 0x91, 0x38, 0x64, 0x09}
   158  
   159  func NewPrivateKey[P Point[P]](c *Curve[P], D, Q []byte) (*PrivateKey, error) {
   160  	fips140.RecordApproved()
   161  	pub, err := NewPublicKey(c, Q)
   162  	if err != nil {
   163  		return nil, err
   164  	}
   165  	d, err := bigmod.NewNat().SetBytes(D, c.N)
   166  	if err != nil {
   167  		return nil, err
   168  	}
   169  	priv := &PrivateKey{pub: *pub, d: d.Bytes(c.N)}
   170  	if err := fipsPCT(c, priv); err != nil {
   171  		// This can happen if the application went out of its way to make an
   172  		// ecdsa.PrivateKey with a mismatching PublicKey.
   173  		return nil, err
   174  	}
   175  	return priv, nil
   176  }
   177  
   178  func NewPublicKey[P Point[P]](c *Curve[P], Q []byte) (*PublicKey, error) {
   179  	// SetBytes checks that Q is a valid point on the curve, and that its
   180  	// coordinates are reduced modulo p, fulfilling the requirements of SP
   181  	// 800-89, Section 5.3.2.
   182  	_, err := c.newPoint().SetBytes(Q)
   183  	if err != nil {
   184  		return nil, err
   185  	}
   186  	return &PublicKey{curve: c.curve, q: Q}, nil
   187  }
   188  
   189  // GenerateKey generates a new ECDSA private key pair for the specified curve.
   190  func GenerateKey[P Point[P]](c *Curve[P], rand io.Reader) (*PrivateKey, error) {
   191  	fips140.RecordApproved()
   192  
   193  	k, Q, err := randomPoint(c, func(b []byte) error {
   194  		return drbg.ReadWithReader(rand, b)
   195  	})
   196  	if err != nil {
   197  		return nil, err
   198  	}
   199  
   200  	priv := &PrivateKey{
   201  		pub: PublicKey{
   202  			curve: c.curve,
   203  			q:     Q.Bytes(),
   204  		},
   205  		d: k.Bytes(c.N),
   206  	}
   207  	if err := fipsPCT(c, priv); err != nil {
   208  		// This clearly can't happen, but FIPS 140-3 mandates that we check it.
   209  		panic(err)
   210  	}
   211  	return priv, nil
   212  }
   213  
   214  // randomPoint returns a random scalar and the corresponding point using a
   215  // procedure equivalent to FIPS 186-5, Appendix A.2.2 (ECDSA Key Pair Generation
   216  // by Rejection Sampling) and to Appendix A.3.2 (Per-Message Secret Number
   217  // Generation of Private Keys by Rejection Sampling) or Appendix A.3.3
   218  // (Per-Message Secret Number Generation for Deterministic ECDSA) followed by
   219  // Step 5 of Section 6.4.1.
   220  func randomPoint[P Point[P]](c *Curve[P], generate func([]byte) error) (k *bigmod.Nat, p P, err error) {
   221  	for {
   222  		b := make([]byte, c.N.Size())
   223  		if err := generate(b); err != nil {
   224  			return nil, nil, err
   225  		}
   226  
   227  		// Take only the leftmost bits of the generated random value. This is
   228  		// both necessary to increase the chance of the random value being in
   229  		// the correct range and to match the specification. It's unfortunate
   230  		// that we need to do a shift instead of a mask, but see the comment on
   231  		// rightShift.
   232  		//
   233  		// These are the most dangerous lines in the package and maybe in the
   234  		// library: a single bit of bias in the selection of nonces would likely
   235  		// lead to key recovery, but no tests would fail. Look but DO NOT TOUCH.
   236  		if excess := len(b)*8 - c.N.BitLen(); excess > 0 {
   237  			// Just to be safe, assert that this only happens for the one curve that
   238  			// doesn't have a round number of bits.
   239  			if c.curve != p521 {
   240  				panic("ecdsa: internal error: unexpectedly masking off bits")
   241  			}
   242  			b = rightShift(b, excess)
   243  		}
   244  
   245  		// FIPS 186-5, Appendix A.4.2 makes us check x <= N - 2 and then return
   246  		// x + 1. Note that it follows that 0 < x + 1 < N. Instead, SetBytes
   247  		// checks that k < N, and we explicitly check 0 != k. Since k can't be
   248  		// negative, this is strictly equivalent. None of this matters anyway
   249  		// because the chance of selecting zero is cryptographically negligible.
   250  		if k, err := bigmod.NewNat().SetBytes(b, c.N); err == nil && k.IsZero() == 0 {
   251  			p, err := c.newPoint().ScalarBaseMult(k.Bytes(c.N))
   252  			return k, p, err
   253  		}
   254  
   255  		if testingOnlyRejectionSamplingLooped != nil {
   256  			testingOnlyRejectionSamplingLooped()
   257  		}
   258  	}
   259  }
   260  
   261  // testingOnlyRejectionSamplingLooped is called when rejection sampling in
   262  // randomPoint rejects a candidate for being higher than the modulus.
   263  var testingOnlyRejectionSamplingLooped func()
   264  
   265  // Signature is an ECDSA signature, where r and s are represented as big-endian
   266  // byte slices of the same length as the curve order.
   267  type Signature struct {
   268  	R, S []byte
   269  }
   270  
   271  // Sign signs a hash (which shall be the result of hashing a larger message with
   272  // the hash function H) using the private key, priv. If the hash is longer than
   273  // the bit-length of the private key's curve order, the hash will be truncated
   274  // to that length.
   275  func Sign[P Point[P], H hash.Hash](c *Curve[P], h func() H, priv *PrivateKey, rand io.Reader, hash []byte) (*Signature, error) {
   276  	if priv.pub.curve != c.curve {
   277  		return nil, errors.New("ecdsa: private key does not match curve")
   278  	}
   279  	fips140.RecordApproved()
   280  	fipsSelfTest()
   281  
   282  	// Random ECDSA is dangerous, because a failure of the RNG would immediately
   283  	// leak the private key. Instead, we use a "hedged" approach, as specified
   284  	// in draft-irtf-cfrg-det-sigs-with-noise-04, Section 4. This has also the
   285  	// advantage of closely resembling Deterministic ECDSA.
   286  
   287  	Z := make([]byte, len(priv.d))
   288  	if err := drbg.ReadWithReader(rand, Z); err != nil {
   289  		return nil, err
   290  	}
   291  
   292  	// See https://github.com/cfrg/draft-irtf-cfrg-det-sigs-with-noise/issues/6
   293  	// for the FIPS compliance of this method. In short Z is entropy from the
   294  	// main DRBG, of length 3/2 of security_strength, so the nonce is optional
   295  	// per SP 800-90Ar1, Section 8.6.7, and the rest is a personalization
   296  	// string, which per SP 800-90Ar1, Section 8.7.1 may contain secret
   297  	// information.
   298  	drbg := newDRBG(h, Z, nil, blockAlignedPersonalizationString{priv.d, bits2octets(c, hash)})
   299  
   300  	return sign(c, priv, drbg, hash)
   301  }
   302  
   303  // SignDeterministic signs a hash (which shall be the result of hashing a
   304  // larger message with the hash function H) using the private key, priv. If the
   305  // hash is longer than the bit-length of the private key's curve order, the hash
   306  // will be truncated to that length. This applies Deterministic ECDSA as
   307  // specified in FIPS 186-5 and RFC 6979.
   308  func SignDeterministic[P Point[P], H hash.Hash](c *Curve[P], h func() H, priv *PrivateKey, hash []byte) (*Signature, error) {
   309  	if priv.pub.curve != c.curve {
   310  		return nil, errors.New("ecdsa: private key does not match curve")
   311  	}
   312  	fips140.RecordApproved()
   313  	fipsSelfTestDeterministic()
   314  	drbg := newDRBG(h, priv.d, bits2octets(c, hash), nil) // RFC 6979, Section 3.3
   315  	return sign(c, priv, drbg, hash)
   316  }
   317  
   318  // bits2octets as specified in FIPS 186-5, Appendix B.2.4 or RFC 6979,
   319  // Section 2.3.4. See RFC 6979, Section 3.5 for the rationale.
   320  func bits2octets[P Point[P]](c *Curve[P], hash []byte) []byte {
   321  	e := bigmod.NewNat()
   322  	hashToNat(c, e, hash)
   323  	return e.Bytes(c.N)
   324  }
   325  
   326  func signGeneric[P Point[P]](c *Curve[P], priv *PrivateKey, drbg *hmacDRBG, hash []byte) (*Signature, error) {
   327  	// FIPS 186-5, Section 6.4.1
   328  
   329  	k, R, err := randomPoint(c, func(b []byte) error {
   330  		drbg.Generate(b)
   331  		return nil
   332  	})
   333  	if err != nil {
   334  		return nil, err
   335  	}
   336  
   337  	// kInv = k⁻¹
   338  	kInv := bigmod.NewNat()
   339  	inverse(c, kInv, k)
   340  
   341  	Rx, err := R.BytesX()
   342  	if err != nil {
   343  		return nil, err
   344  	}
   345  	r, err := bigmod.NewNat().SetOverflowingBytes(Rx, c.N)
   346  	if err != nil {
   347  		return nil, err
   348  	}
   349  
   350  	// The spec wants us to retry here, but the chance of hitting this condition
   351  	// on a large prime-order group like the NIST curves we support is
   352  	// cryptographically negligible. If we hit it, something is awfully wrong.
   353  	if r.IsZero() == 1 {
   354  		return nil, errors.New("ecdsa: internal error: r is zero")
   355  	}
   356  
   357  	e := bigmod.NewNat()
   358  	hashToNat(c, e, hash)
   359  
   360  	s, err := bigmod.NewNat().SetBytes(priv.d, c.N)
   361  	if err != nil {
   362  		return nil, err
   363  	}
   364  	s.Mul(r, c.N)
   365  	s.Add(e, c.N)
   366  	s.Mul(kInv, c.N)
   367  
   368  	// Again, the chance of this happening is cryptographically negligible.
   369  	if s.IsZero() == 1 {
   370  		return nil, errors.New("ecdsa: internal error: s is zero")
   371  	}
   372  
   373  	return &Signature{r.Bytes(c.N), s.Bytes(c.N)}, nil
   374  }
   375  
   376  // inverse sets kInv to the inverse of k modulo the order of the curve.
   377  func inverse[P Point[P]](c *Curve[P], kInv, k *bigmod.Nat) {
   378  	if c.ordInverse != nil {
   379  		kBytes, err := c.ordInverse(k.Bytes(c.N))
   380  		// Some platforms don't implement ordInverse, and always return an error.
   381  		if err == nil {
   382  			_, err := kInv.SetBytes(kBytes, c.N)
   383  			if err != nil {
   384  				panic("ecdsa: internal error: ordInverse produced an invalid value")
   385  			}
   386  			return
   387  		}
   388  	}
   389  
   390  	// Calculate the inverse of s in GF(N) using Fermat's method
   391  	// (exponentiation modulo P - 2, per Euler's theorem)
   392  	kInv.Exp(k, c.nMinus2, c.N)
   393  }
   394  
   395  // hashToNat sets e to the left-most bits of hash, according to
   396  // FIPS 186-5, Section 6.4.1, point 2 and Section 6.4.2, point 3.
   397  func hashToNat[P Point[P]](c *Curve[P], e *bigmod.Nat, hash []byte) {
   398  	// ECDSA asks us to take the left-most log2(N) bits of hash, and use them as
   399  	// an integer modulo N. This is the absolute worst of all worlds: we still
   400  	// have to reduce, because the result might still overflow N, but to take
   401  	// the left-most bits for P-521 we have to do a right shift.
   402  	if size := c.N.Size(); len(hash) >= size {
   403  		hash = hash[:size]
   404  		if excess := len(hash)*8 - c.N.BitLen(); excess > 0 {
   405  			hash = rightShift(hash, excess)
   406  		}
   407  	}
   408  	_, err := e.SetOverflowingBytes(hash, c.N)
   409  	if err != nil {
   410  		panic("ecdsa: internal error: truncated hash is too long")
   411  	}
   412  }
   413  
   414  // rightShift implements the right shift necessary for bits2int, which takes the
   415  // leftmost bits of either the hash or HMAC_DRBG output.
   416  //
   417  // Note how taking the rightmost bits would have been as easy as masking the
   418  // first byte, but we can't have nice things.
   419  func rightShift(b []byte, shift int) []byte {
   420  	if shift <= 0 || shift >= 8 {
   421  		panic("ecdsa: internal error: shift can only be by 1 to 7 bits")
   422  	}
   423  	b = bytes.Clone(b)
   424  	for i := len(b) - 1; i >= 0; i-- {
   425  		b[i] >>= shift
   426  		if i > 0 {
   427  			b[i] |= b[i-1] << (8 - shift)
   428  		}
   429  	}
   430  	return b
   431  }
   432  
   433  // Verify verifies the signature, sig, of hash (which should be the result of
   434  // hashing a larger message) using the public key, pub. If the hash is longer
   435  // than the bit-length of the private key's curve order, the hash will be
   436  // truncated to that length.
   437  //
   438  // The inputs are not considered confidential, and may leak through timing side
   439  // channels, or if an attacker has control of part of the inputs.
   440  func Verify[P Point[P]](c *Curve[P], pub *PublicKey, hash []byte, sig *Signature) error {
   441  	if pub.curve != c.curve {
   442  		return errors.New("ecdsa: public key does not match curve")
   443  	}
   444  	fips140.RecordApproved()
   445  	fipsSelfTest()
   446  	return verify(c, pub, hash, sig)
   447  }
   448  
   449  func verifyGeneric[P Point[P]](c *Curve[P], pub *PublicKey, hash []byte, sig *Signature) error {
   450  	// FIPS 186-5, Section 6.4.2
   451  
   452  	Q, err := c.newPoint().SetBytes(pub.q)
   453  	if err != nil {
   454  		return err
   455  	}
   456  
   457  	r, err := bigmod.NewNat().SetBytes(sig.R, c.N)
   458  	if err != nil {
   459  		return err
   460  	}
   461  	if r.IsZero() == 1 {
   462  		return errors.New("ecdsa: invalid signature: r is zero")
   463  	}
   464  	s, err := bigmod.NewNat().SetBytes(sig.S, c.N)
   465  	if err != nil {
   466  		return err
   467  	}
   468  	if s.IsZero() == 1 {
   469  		return errors.New("ecdsa: invalid signature: s is zero")
   470  	}
   471  
   472  	e := bigmod.NewNat()
   473  	hashToNat(c, e, hash)
   474  
   475  	// w = s⁻¹
   476  	w := bigmod.NewNat()
   477  	inverse(c, w, s)
   478  
   479  	// p₁ = [e * s⁻¹]G
   480  	p1, err := c.newPoint().ScalarBaseMult(e.Mul(w, c.N).Bytes(c.N))
   481  	if err != nil {
   482  		return err
   483  	}
   484  	// p₂ = [r * s⁻¹]Q
   485  	p2, err := Q.ScalarMult(Q, w.Mul(r, c.N).Bytes(c.N))
   486  	if err != nil {
   487  		return err
   488  	}
   489  	// BytesX returns an error for the point at infinity.
   490  	Rx, err := p1.Add(p1, p2).BytesX()
   491  	if err != nil {
   492  		return err
   493  	}
   494  
   495  	v, err := bigmod.NewNat().SetOverflowingBytes(Rx, c.N)
   496  	if err != nil {
   497  		return err
   498  	}
   499  
   500  	if v.Equal(r) != 1 {
   501  		return errors.New("ecdsa: signature did not verify")
   502  	}
   503  	return nil
   504  }
   505
View as plain text