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