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