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