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