ecdsa.go

Documentation: crypto/internal/fips140/ecdsa

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