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  	fips140.RecordApproved()
   165  	pub, err := NewPublicKey(c, Q)
   166  	if err != nil {
   167  		return nil, err
   168  	}
   169  	if len(D) != c.N.Size() {
   170  		return nil, errors.New("ecdsa: invalid private key length")
   171  	}
   172  	d, err := bigmod.NewNat().SetBytes(D, c.N)
   173  	if err != nil {
   174  		return nil, err
   175  	}
   176  	if d.IsZero() == 1 {
   177  		return nil, errors.New("ecdsa: private key is zero")
   178  	}
   179  	priv := &PrivateKey{pub: *pub, d: d.Bytes(c.N)}
   180  	return priv, nil
   181  }
   182  
   183  // NewPublicKey creates a new ECDSA public key from the given Q byte slice.
   184  // Q must be the compressed or uncompressed encoding of the public point.
   185  func NewPublicKey[P Point[P]](c *Curve[P], Q []byte) (*PublicKey, error) {
   186  	// SetBytes checks that Q is a valid point on the curve, and that its
   187  	// coordinates are reduced modulo p, fulfilling the requirements of SP
   188  	// 800-89, Section 5.3.2.
   189  	if len(Q) < 1 || Q[0] == 0 {
   190  		return nil, errors.New("ecdsa: invalid public key encoding")
   191  	}
   192  	_, err := c.newPoint().SetBytes(Q)
   193  	if err != nil {
   194  		return nil, err
   195  	}
   196  	return &PublicKey{curve: c.curve, q: Q}, nil
   197  }
   198  
   199  // GenerateKey generates a new ECDSA private key pair for the specified curve.
   200  func GenerateKey[P Point[P]](c *Curve[P], rand io.Reader) (*PrivateKey, error) {
   201  	fips140.RecordApproved()
   202  
   203  	k, Q, err := randomPoint(c, func(b []byte) error {
   204  		return drbg.ReadWithReader(rand, b)
   205  	})
   206  	if err != nil {
   207  		return nil, err
   208  	}
   209  
   210  	priv := &PrivateKey{
   211  		pub: PublicKey{
   212  			curve: c.curve,
   213  			q:     Q.Bytes(),
   214  		},
   215  		d: k.Bytes(c.N),
   216  	}
   217  	fipsPCT(c, priv)
   218  	return priv, nil
   219  }
   220  
   221  // randomPoint returns a random scalar and the corresponding point using a
   222  // procedure equivalent to FIPS 186-5, Appendix A.2.2 (ECDSA Key Pair Generation
   223  // by Rejection Sampling) and to Appendix A.3.2 (Per-Message Secret Number
   224  // Generation of Private Keys by Rejection Sampling) or Appendix A.3.3
   225  // (Per-Message Secret Number Generation for Deterministic ECDSA) followed by
   226  // Step 5 of Section 6.4.1.
   227  func randomPoint[P Point[P]](c *Curve[P], generate func([]byte) error) (k *bigmod.Nat, p P, err error) {
   228  	for {
   229  		b := make([]byte, c.N.Size())
   230  		if err := generate(b); err != nil {
   231  			return nil, nil, err
   232  		}
   233  
   234  		// Take only the leftmost bits of the generated random value. This is
   235  		// both necessary to increase the chance of the random value being in
   236  		// the correct range and to match the specification. It's unfortunate
   237  		// that we need to do a shift instead of a mask, but see the comment on
   238  		// rightShift.
   239  		//
   240  		// These are the most dangerous lines in the package and maybe in the
   241  		// library: a single bit of bias in the selection of nonces would likely
   242  		// lead to key recovery, but no tests would fail. Look but DO NOT TOUCH.
   243  		if excess := len(b)*8 - c.N.BitLen(); excess > 0 {
   244  			// Just to be safe, assert that this only happens for the one curve that
   245  			// doesn't have a round number of bits.
   246  			if c.curve != p521 {
   247  				panic("ecdsa: internal error: unexpectedly masking off bits")
   248  			}
   249  			b = rightShift(b, excess)
   250  		}
   251  
   252  		// FIPS 186-5, Appendix A.4.2 makes us check x <= N - 2 and then return
   253  		// x + 1. Note that it follows that 0 < x + 1 < N. Instead, SetBytes
   254  		// checks that k < N, and we explicitly check 0 != k. Since k can't be
   255  		// negative, this is strictly equivalent. None of this matters anyway
   256  		// because the chance of selecting zero is cryptographically negligible.
   257  		if k, err := bigmod.NewNat().SetBytes(b, c.N); err == nil && k.IsZero() == 0 {
   258  			p, err := c.newPoint().ScalarBaseMult(k.Bytes(c.N))
   259  			return k, p, err
   260  		}
   261  
   262  		if testingOnlyRejectionSamplingLooped != nil {
   263  			testingOnlyRejectionSamplingLooped()
   264  		}
   265  	}
   266  }
   267  
   268  // testingOnlyRejectionSamplingLooped is called when rejection sampling in
   269  // randomPoint rejects a candidate for being higher than the modulus.
   270  var testingOnlyRejectionSamplingLooped func()
   271  
   272  // Signature is an ECDSA signature, where r and s are represented as big-endian
   273  // byte slices of the same length as the curve order.
   274  type Signature struct {
   275  	R, S []byte
   276  }
   277  
   278  // Sign signs a hash (which should be the result of hashing a larger message with
   279  // the hash function H) using the private key, priv. If the hash is longer than
   280  // the bit-length of the private key's curve order, the hash will be truncated
   281  // to that length.
   282  func Sign[P Point[P], H hash.Hash](c *Curve[P], h func() H, priv *PrivateKey, rand io.Reader, hash []byte) (*Signature, error) {
   283  	if priv.pub.curve != c.curve {
   284  		return nil, errors.New("ecdsa: private key does not match curve")
   285  	}
   286  	if len(hash) == 0 {
   287  		return nil, errors.New("ecdsa: hash cannot be empty")
   288  	}
   289  	fips140.RecordApproved()
   290  	fipsSelfTest()
   291  
   292  	// Random ECDSA is dangerous, because a failure of the RNG would immediately
   293  	// leak the private key. Instead, we use a "hedged" approach, as specified
   294  	// in draft-irtf-cfrg-det-sigs-with-noise-04, Section 4. This has also the
   295  	// advantage of closely resembling Deterministic ECDSA.
   296  
   297  	Z := make([]byte, len(priv.d))
   298  	if err := drbg.ReadWithReader(rand, Z); err != nil {
   299  		return nil, err
   300  	}
   301  
   302  	// See https://github.com/cfrg/draft-irtf-cfrg-det-sigs-with-noise/issues/6
   303  	// for the FIPS compliance of this method. In short Z is entropy from the
   304  	// main DRBG, of length 3/2 of security_strength, so the nonce is optional
   305  	// per SP 800-90Ar1, Section 8.6.7, and the rest is a personalization
   306  	// string, which per SP 800-90Ar1, Section 8.7.1 may contain secret
   307  	// information.
   308  	drbg := newDRBG(h, Z, nil, blockAlignedPersonalizationString{priv.d, bits2octets(c, hash)})
   309  
   310  	return sign(c, priv, drbg, hash)
   311  }
   312  
   313  // SignDeterministic signs a hash (which shall be the result of hashing a
   314  // larger message with the hash function H) using the private key, priv. If the
   315  // hash is longer than the bit-length of the private key's curve order, the hash
   316  // will be truncated to that length. This applies Deterministic ECDSA as
   317  // specified in FIPS 186-5 and RFC 6979.
   318  func SignDeterministic[P Point[P], H hash.Hash](c *Curve[P], h func() H, priv *PrivateKey, hash []byte) (*Signature, error) {
   319  	if priv.pub.curve != c.curve {
   320  		return nil, errors.New("ecdsa: private key does not match curve")
   321  	}
   322  	if len(hash) == 0 {
   323  		return nil, errors.New("ecdsa: hash cannot be empty")
   324  	}
   325  	fips140.RecordApproved()
   326  	fipsSelfTestDeterministic()
   327  	drbg := newDRBG(h, priv.d, bits2octets(c, hash), nil) // RFC 6979, Section 3.3
   328  	return sign(c, priv, drbg, hash)
   329  }
   330  
   331  // bits2octets as specified in FIPS 186-5, Appendix B.2.4 or RFC 6979,
   332  // Section 2.3.4. See RFC 6979, Section 3.5 for the rationale.
   333  func bits2octets[P Point[P]](c *Curve[P], hash []byte) []byte {
   334  	e := bigmod.NewNat()
   335  	hashToNat(c, e, hash)
   336  	return e.Bytes(c.N)
   337  }
   338  
   339  func signGeneric[P Point[P]](c *Curve[P], priv *PrivateKey, drbg *hmacDRBG, hash []byte) (*Signature, error) {
   340  	// FIPS 186-5, Section 6.4.1
   341  
   342  	k, R, err := randomPoint(c, func(b []byte) error {
   343  		drbg.Generate(b)
   344  		return nil
   345  	})
   346  	if err != nil {
   347  		return nil, err
   348  	}
   349  
   350  	// kInv = k⁻¹
   351  	kInv := bigmod.NewNat()
   352  	inverse(c, kInv, k)
   353  
   354  	Rx, err := R.BytesX()
   355  	if err != nil {
   356  		return nil, err
   357  	}
   358  	r, err := bigmod.NewNat().SetOverflowingBytes(Rx, c.N)
   359  	if err != nil {
   360  		return nil, err
   361  	}
   362  
   363  	// The spec wants us to retry here, but the chance of hitting this condition
   364  	// on a large prime-order group like the NIST curves we support is
   365  	// cryptographically negligible. If we hit it, something is awfully wrong.
   366  	if r.IsZero() == 1 {
   367  		return nil, errors.New("ecdsa: internal error: r is zero")
   368  	}
   369  
   370  	e := bigmod.NewNat()
   371  	hashToNat(c, e, hash)
   372  
   373  	s, err := bigmod.NewNat().SetBytes(priv.d, c.N)
   374  	if err != nil {
   375  		return nil, err
   376  	}
   377  	s.Mul(r, c.N)
   378  	s.Add(e, c.N)
   379  	s.Mul(kInv, c.N)
   380  
   381  	// Again, the chance of this happening is cryptographically negligible.
   382  	if s.IsZero() == 1 {
   383  		return nil, errors.New("ecdsa: internal error: s is zero")
   384  	}
   385  
   386  	return &Signature{r.Bytes(c.N), s.Bytes(c.N)}, nil
   387  }
   388  
   389  // inverse sets kInv to the inverse of k modulo the order of the curve.
   390  func inverse[P Point[P]](c *Curve[P], kInv, k *bigmod.Nat) {
   391  	if c.ordInverse != nil && bits.UintSize == 64 {
   392  		if kb := k.Bits(); len(kb) == 4 {
   393  			k64 := [4]uint64{uint64(kb[0]), uint64(kb[1]), uint64(kb[2]), uint64(kb[3])}
   394  			c.ordInverse(&k64)
   395  			kInv.SetBits([]uint{uint(k64[0]), uint(k64[1]), uint(k64[2]), uint(k64[3])})
   396  			return
   397  		}
   398  	}
   399  
   400  	// Calculate the inverse of s in GF(N) using Fermat's method
   401  	// (exponentiation modulo P - 2, per Euler's theorem)
   402  	kInv.Exp(k, c.nMinus2, c.N)
   403  }
   404  
   405  // hashToNat sets e to the left-most bits of hash, according to
   406  // FIPS 186-5, Section 6.4.1, point 2 and Section 6.4.2, point 3.
   407  func hashToNat[P Point[P]](c *Curve[P], e *bigmod.Nat, hash []byte) {
   408  	// ECDSA asks us to take the left-most log2(N) bits of hash, and use them as
   409  	// an integer modulo N. This is the absolute worst of all worlds: we still
   410  	// have to reduce, because the result might still overflow N, but to take
   411  	// the left-most bits for P-521 we have to do a right shift.
   412  	if size := c.N.Size(); len(hash) >= size {
   413  		hash = hash[:size]
   414  		if excess := len(hash)*8 - c.N.BitLen(); excess > 0 {
   415  			hash = rightShift(hash, excess)
   416  		}
   417  	}
   418  	_, err := e.SetOverflowingBytes(hash, c.N)
   419  	if err != nil {
   420  		panic("ecdsa: internal error: truncated hash is too long")
   421  	}
   422  }
   423  
   424  // rightShift implements the right shift necessary for bits2int, which takes the
   425  // leftmost bits of either the hash or HMAC_DRBG output.
   426  //
   427  // Note how taking the rightmost bits would have been as easy as masking the
   428  // first byte, but we can't have nice things.
   429  func rightShift(b []byte, shift int) []byte {
   430  	if shift <= 0 || shift >= 8 {
   431  		panic("ecdsa: internal error: shift can only be by 1 to 7 bits")
   432  	}
   433  	b = bytes.Clone(b)
   434  	for i := len(b) - 1; i >= 0; i-- {
   435  		b[i] >>= shift
   436  		if i > 0 {
   437  			b[i] |= b[i-1] << (8 - shift)
   438  		}
   439  	}
   440  	return b
   441  }
   442  
   443  // Verify verifies the signature, sig, of hash (which should be the result of
   444  // hashing a larger message) using the public key, pub. If the hash is longer
   445  // than the bit-length of the private key's curve order, the hash will be
   446  // truncated to that length.
   447  //
   448  // The inputs are not considered confidential, and may leak through timing side
   449  // channels, or if an attacker has control of part of the inputs.
   450  func Verify[P Point[P]](c *Curve[P], pub *PublicKey, hash []byte, sig *Signature) error {
   451  	if pub.curve != c.curve {
   452  		return errors.New("ecdsa: public key does not match curve")
   453  	}
   454  	if len(hash) == 0 {
   455  		return errors.New("ecdsa: hash cannot be empty")
   456  	}
   457  	fips140.RecordApproved()
   458  	fipsSelfTest()
   459  	return verify(c, pub, hash, sig)
   460  }
   461  
   462  func verifyGeneric[P Point[P]](c *Curve[P], pub *PublicKey, hash []byte, sig *Signature) error {
   463  	// FIPS 186-5, Section 6.4.2
   464  
   465  	Q, err := c.newPoint().SetBytes(pub.q)
   466  	if err != nil {
   467  		return err
   468  	}
   469  
   470  	r, err := bigmod.NewNat().SetBytes(sig.R, c.N)
   471  	if err != nil {
   472  		return err
   473  	}
   474  	if r.IsZero() == 1 {
   475  		return errors.New("ecdsa: invalid signature: r is zero")
   476  	}
   477  	s, err := bigmod.NewNat().SetBytes(sig.S, c.N)
   478  	if err != nil {
   479  		return err
   480  	}
   481  	if s.IsZero() == 1 {
   482  		return errors.New("ecdsa: invalid signature: s is zero")
   483  	}
   484  
   485  	e := bigmod.NewNat()
   486  	hashToNat(c, e, hash)
   487  
   488  	// w = s⁻¹
   489  	w := bigmod.NewNat()
   490  	inverse(c, w, s)
   491  
   492  	// p₁ = [e * s⁻¹]G
   493  	p1, err := c.newPoint().ScalarBaseMult(e.Mul(w, c.N).Bytes(c.N))
   494  	if err != nil {
   495  		return err
   496  	}
   497  	// p₂ = [r * s⁻¹]Q
   498  	p2, err := Q.ScalarMult(Q, w.Mul(r, c.N).Bytes(c.N))
   499  	if err != nil {
   500  		return err
   501  	}
   502  	// BytesX returns an error for the point at infinity.
   503  	Rx, err := p1.Add(p1, p2).BytesX()
   504  	if err != nil {
   505  		return err
   506  	}
   507  
   508  	v, err := bigmod.NewNat().SetOverflowingBytes(Rx, c.N)
   509  	if err != nil {
   510  		return err
   511  	}
   512  
   513  	if v.Equal(r) != 1 {
   514  		return errors.New("ecdsa: signature did not verify")
   515  	}
   516  	return nil
   517  }
   518
View as plain text