ecdsa.go

Documentation: crypto/ecdsa

     1  // Copyright 2011 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 implements the Elliptic Curve Digital Signature Algorithm, as
     6  // defined in FIPS 186-4 and SEC 1, Version 2.0.
     7  //
     8  // Signatures generated by this package are not deterministic, but entropy is
     9  // mixed with the private key and the message, achieving the same level of
    10  // security in case of randomness source failure.
    11  package ecdsa
    12  
    13  // [FIPS 186-4] references ANSI X9.62-2005 for the bulk of the ECDSA algorithm.
    14  // That standard is not freely available, which is a problem in an open source
    15  // implementation, because not only the implementer, but also any maintainer,
    16  // contributor, reviewer, auditor, and learner needs access to it. Instead, this
    17  // package references and follows the equivalent [SEC 1, Version 2.0].
    18  //
    19  // [FIPS 186-4]: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf
    20  // [SEC 1, Version 2.0]: https://www.secg.org/sec1-v2.pdf
    21  
    22  import (
    23  	"crypto"
    24  	"crypto/aes"
    25  	"crypto/cipher"
    26  	"crypto/elliptic"
    27  	"crypto/internal/boring"
    28  	"crypto/internal/boring/bbig"
    29  	"crypto/internal/randutil"
    30  	"crypto/sha512"
    31  	"errors"
    32  	"io"
    33  	"math/big"
    34  
    35  	"golang.org/x/crypto/cryptobyte"
    36  	"golang.org/x/crypto/cryptobyte/asn1"
    37  )
    38  
    39  // A invertible implements fast inverse in GF(N).
    40  type invertible interface {
    41  	// Inverse returns the inverse of k mod Params().N.
    42  	Inverse(k *big.Int) *big.Int
    43  }
    44  
    45  // A combinedMult implements fast combined multiplication for verification.
    46  type combinedMult interface {
    47  	// CombinedMult returns [s1]G + [s2]P where G is the generator.
    48  	CombinedMult(Px, Py *big.Int, s1, s2 []byte) (x, y *big.Int)
    49  }
    50  
    51  const (
    52  	aesIV = "IV for ECDSA CTR"
    53  )
    54  
    55  // PublicKey represents an ECDSA public key.
    56  type PublicKey struct {
    57  	elliptic.Curve
    58  	X, Y *big.Int
    59  }
    60  
    61  // Any methods implemented on PublicKey might need to also be implemented on
    62  // PrivateKey, as the latter embeds the former and will expose its methods.
    63  
    64  // Equal reports whether pub and x have the same value.
    65  //
    66  // Two keys are only considered to have the same value if they have the same Curve value.
    67  // Note that for example elliptic.P256() and elliptic.P256().Params() are different
    68  // values, as the latter is a generic not constant time implementation.
    69  func (pub *PublicKey) Equal(x crypto.PublicKey) bool {
    70  	xx, ok := x.(*PublicKey)
    71  	if !ok {
    72  		return false
    73  	}
    74  	return pub.X.Cmp(xx.X) == 0 && pub.Y.Cmp(xx.Y) == 0 &&
    75  		// Standard library Curve implementations are singletons, so this check
    76  		// will work for those. Other Curves might be equivalent even if not
    77  		// singletons, but there is no definitive way to check for that, and
    78  		// better to err on the side of safety.
    79  		pub.Curve == xx.Curve
    80  }
    81  
    82  // PrivateKey represents an ECDSA private key.
    83  type PrivateKey struct {
    84  	PublicKey
    85  	D *big.Int
    86  }
    87  
    88  // Public returns the public key corresponding to priv.
    89  func (priv *PrivateKey) Public() crypto.PublicKey {
    90  	return &priv.PublicKey
    91  }
    92  
    93  // Equal reports whether priv and x have the same value.
    94  //
    95  // See PublicKey.Equal for details on how Curve is compared.
    96  func (priv *PrivateKey) Equal(x crypto.PrivateKey) bool {
    97  	xx, ok := x.(*PrivateKey)
    98  	if !ok {
    99  		return false
   100  	}
   101  	return priv.PublicKey.Equal(&xx.PublicKey) && priv.D.Cmp(xx.D) == 0
   102  }
   103  
   104  // Sign signs digest with priv, reading randomness from rand. The opts argument
   105  // is not currently used but, in keeping with the crypto.Signer interface,
   106  // should be the hash function used to digest the message.
   107  //
   108  // This method implements crypto.Signer, which is an interface to support keys
   109  // where the private part is kept in, for example, a hardware module. Common
   110  // uses can use the SignASN1 function in this package directly.
   111  func (priv *PrivateKey) Sign(rand io.Reader, digest []byte, opts crypto.SignerOpts) ([]byte, error) {
   112  	if boring.Enabled && rand == boring.RandReader {
   113  		b, err := boringPrivateKey(priv)
   114  		if err != nil {
   115  			return nil, err
   116  		}
   117  		return boring.SignMarshalECDSA(b, digest)
   118  	}
   119  	boring.UnreachableExceptTests()
   120  
   121  	r, s, err := Sign(rand, priv, digest)
   122  	if err != nil {
   123  		return nil, err
   124  	}
   125  
   126  	var b cryptobyte.Builder
   127  	b.AddASN1(asn1.SEQUENCE, func(b *cryptobyte.Builder) {
   128  		b.AddASN1BigInt(r)
   129  		b.AddASN1BigInt(s)
   130  	})
   131  	return b.Bytes()
   132  }
   133  
   134  var one = new(big.Int).SetInt64(1)
   135  
   136  // randFieldElement returns a random element of the order of the given
   137  // curve using the procedure given in FIPS 186-4, Appendix B.5.1.
   138  func randFieldElement(c elliptic.Curve, rand io.Reader) (k *big.Int, err error) {
   139  	params := c.Params()
   140  	// Note that for P-521 this will actually be 63 bits more than the order, as
   141  	// division rounds down, but the extra bit is inconsequential.
   142  	b := make([]byte, params.N.BitLen()/8+8)
   143  	_, err = io.ReadFull(rand, b)
   144  	if err != nil {
   145  		return
   146  	}
   147  
   148  	k = new(big.Int).SetBytes(b)
   149  	n := new(big.Int).Sub(params.N, one)
   150  	k.Mod(k, n)
   151  	k.Add(k, one)
   152  	return
   153  }
   154  
   155  // GenerateKey generates a public and private key pair.
   156  func GenerateKey(c elliptic.Curve, rand io.Reader) (*PrivateKey, error) {
   157  	if boring.Enabled && rand == boring.RandReader {
   158  		x, y, d, err := boring.GenerateKeyECDSA(c.Params().Name)
   159  		if err != nil {
   160  			return nil, err
   161  		}
   162  		return &PrivateKey{PublicKey: PublicKey{Curve: c, X: bbig.Dec(x), Y: bbig.Dec(y)}, D: bbig.Dec(d)}, nil
   163  	}
   164  	boring.UnreachableExceptTests()
   165  
   166  	k, err := randFieldElement(c, rand)
   167  	if err != nil {
   168  		return nil, err
   169  	}
   170  
   171  	priv := new(PrivateKey)
   172  	priv.PublicKey.Curve = c
   173  	priv.D = k
   174  	priv.PublicKey.X, priv.PublicKey.Y = c.ScalarBaseMult(k.Bytes())
   175  	return priv, nil
   176  }
   177  
   178  // hashToInt converts a hash value to an integer. Per FIPS 186-4, Section 6.4,
   179  // we use the left-most bits of the hash to match the bit-length of the order of
   180  // the curve. This also performs Step 5 of SEC 1, Version 2.0, Section 4.1.3.
   181  func hashToInt(hash []byte, c elliptic.Curve) *big.Int {
   182  	orderBits := c.Params().N.BitLen()
   183  	orderBytes := (orderBits + 7) / 8
   184  	if len(hash) > orderBytes {
   185  		hash = hash[:orderBytes]
   186  	}
   187  
   188  	ret := new(big.Int).SetBytes(hash)
   189  	excess := len(hash)*8 - orderBits
   190  	if excess > 0 {
   191  		ret.Rsh(ret, uint(excess))
   192  	}
   193  	return ret
   194  }
   195  
   196  // fermatInverse calculates the inverse of k in GF(P) using Fermat's method
   197  // (exponentiation modulo P - 2, per Euler's theorem). This has better
   198  // constant-time properties than Euclid's method (implemented in
   199  // math/big.Int.ModInverse and FIPS 186-4, Appendix C.1) although math/big
   200  // itself isn't strictly constant-time so it's not perfect.
   201  func fermatInverse(k, N *big.Int) *big.Int {
   202  	two := big.NewInt(2)
   203  	nMinus2 := new(big.Int).Sub(N, two)
   204  	return new(big.Int).Exp(k, nMinus2, N)
   205  }
   206  
   207  var errZeroParam = errors.New("zero parameter")
   208  
   209  // Sign signs a hash (which should be the result of hashing a larger message)
   210  // using the private key, priv. If the hash is longer than the bit-length of the
   211  // private key's curve order, the hash will be truncated to that length. It
   212  // returns the signature as a pair of integers. Most applications should use
   213  // SignASN1 instead of dealing directly with r, s.
   214  func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) {
   215  	randutil.MaybeReadByte(rand)
   216  
   217  	if boring.Enabled && rand == boring.RandReader {
   218  		b, err := boringPrivateKey(priv)
   219  		if err != nil {
   220  			return nil, nil, err
   221  		}
   222  		sig, err := boring.SignMarshalECDSA(b, hash)
   223  		if err != nil {
   224  			return nil, nil, err
   225  		}
   226  		var r, s big.Int
   227  		var inner cryptobyte.String
   228  		input := cryptobyte.String(sig)
   229  		if !input.ReadASN1(&inner, asn1.SEQUENCE) ||
   230  			!input.Empty() ||
   231  			!inner.ReadASN1Integer(&r) ||
   232  			!inner.ReadASN1Integer(&s) ||
   233  			!inner.Empty() {
   234  			return nil, nil, errors.New("invalid ASN.1 from boringcrypto")
   235  		}
   236  		return &r, &s, nil
   237  	}
   238  	boring.UnreachableExceptTests()
   239  
   240  	// This implementation derives the nonce from an AES-CTR CSPRNG keyed by:
   241  	//
   242  	//    SHA2-512(priv.D || entropy || hash)[:32]
   243  	//
   244  	// The CSPRNG key is indifferentiable from a random oracle as shown in
   245  	// [Coron], the AES-CTR stream is indifferentiable from a random oracle
   246  	// under standard cryptographic assumptions (see [Larsson] for examples).
   247  	//
   248  	// [Coron]: https://cs.nyu.edu/~dodis/ps/merkle.pdf
   249  	// [Larsson]: https://web.archive.org/web/20040719170906/https://www.nada.kth.se/kurser/kth/2D1441/semteo03/lecturenotes/assump.pdf
   250  
   251  	// Get 256 bits of entropy from rand.
   252  	entropy := make([]byte, 32)
   253  	_, err = io.ReadFull(rand, entropy)
   254  	if err != nil {
   255  		return
   256  	}
   257  
   258  	// Initialize an SHA-512 hash context; digest...
   259  	md := sha512.New()
   260  	md.Write(priv.D.Bytes()) // the private key,
   261  	md.Write(entropy)        // the entropy,
   262  	md.Write(hash)           // and the input hash;
   263  	key := md.Sum(nil)[:32]  // and compute ChopMD-256(SHA-512),
   264  	// which is an indifferentiable MAC.
   265  
   266  	// Create an AES-CTR instance to use as a CSPRNG.
   267  	block, err := aes.NewCipher(key)
   268  	if err != nil {
   269  		return nil, nil, err
   270  	}
   271  
   272  	// Create a CSPRNG that xors a stream of zeros with
   273  	// the output of the AES-CTR instance.
   274  	csprng := &cipher.StreamReader{
   275  		R: zeroReader,
   276  		S: cipher.NewCTR(block, []byte(aesIV)),
   277  	}
   278  
   279  	c := priv.PublicKey.Curve
   280  	return sign(priv, csprng, c, hash)
   281  }
   282  
   283  func signGeneric(priv *PrivateKey, csprng *cipher.StreamReader, c elliptic.Curve, hash []byte) (r, s *big.Int, err error) {
   284  	// SEC 1, Version 2.0, Section 4.1.3
   285  	N := c.Params().N
   286  	if N.Sign() == 0 {
   287  		return nil, nil, errZeroParam
   288  	}
   289  	var k, kInv *big.Int
   290  	for {
   291  		for {
   292  			k, err = randFieldElement(c, *csprng)
   293  			if err != nil {
   294  				r = nil
   295  				return
   296  			}
   297  
   298  			if in, ok := priv.Curve.(invertible); ok {
   299  				kInv = in.Inverse(k)
   300  			} else {
   301  				kInv = fermatInverse(k, N) // N != 0
   302  			}
   303  
   304  			r, _ = priv.Curve.ScalarBaseMult(k.Bytes())
   305  			r.Mod(r, N)
   306  			if r.Sign() != 0 {
   307  				break
   308  			}
   309  		}
   310  
   311  		e := hashToInt(hash, c)
   312  		s = new(big.Int).Mul(priv.D, r)
   313  		s.Add(s, e)
   314  		s.Mul(s, kInv)
   315  		s.Mod(s, N) // N != 0
   316  		if s.Sign() != 0 {
   317  			break
   318  		}
   319  	}
   320  
   321  	return
   322  }
   323  
   324  // SignASN1 signs a hash (which should be the result of hashing a larger message)
   325  // using the private key, priv. If the hash is longer than the bit-length of the
   326  // private key's curve order, the hash will be truncated to that length. It
   327  // returns the ASN.1 encoded signature.
   328  func SignASN1(rand io.Reader, priv *PrivateKey, hash []byte) ([]byte, error) {
   329  	return priv.Sign(rand, hash, nil)
   330  }
   331  
   332  // Verify verifies the signature in r, s of hash using the public key, pub. Its
   333  // return value records whether the signature is valid. Most applications should
   334  // use VerifyASN1 instead of dealing directly with r, s.
   335  func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
   336  	if boring.Enabled {
   337  		key, err := boringPublicKey(pub)
   338  		if err != nil {
   339  			return false
   340  		}
   341  		var b cryptobyte.Builder
   342  		b.AddASN1(asn1.SEQUENCE, func(b *cryptobyte.Builder) {
   343  			b.AddASN1BigInt(r)
   344  			b.AddASN1BigInt(s)
   345  		})
   346  		sig, err := b.Bytes()
   347  		if err != nil {
   348  			return false
   349  		}
   350  		return boring.VerifyECDSA(key, hash, sig)
   351  	}
   352  	boring.UnreachableExceptTests()
   353  
   354  	c := pub.Curve
   355  	N := c.Params().N
   356  
   357  	if r.Sign() <= 0 || s.Sign() <= 0 {
   358  		return false
   359  	}
   360  	if r.Cmp(N) >= 0 || s.Cmp(N) >= 0 {
   361  		return false
   362  	}
   363  	return verify(pub, c, hash, r, s)
   364  }
   365  
   366  func verifyGeneric(pub *PublicKey, c elliptic.Curve, hash []byte, r, s *big.Int) bool {
   367  	// SEC 1, Version 2.0, Section 4.1.4
   368  	e := hashToInt(hash, c)
   369  	var w *big.Int
   370  	N := c.Params().N
   371  	if in, ok := c.(invertible); ok {
   372  		w = in.Inverse(s)
   373  	} else {
   374  		w = new(big.Int).ModInverse(s, N)
   375  	}
   376  
   377  	u1 := e.Mul(e, w)
   378  	u1.Mod(u1, N)
   379  	u2 := w.Mul(r, w)
   380  	u2.Mod(u2, N)
   381  
   382  	// Check if implements S1*g + S2*p
   383  	var x, y *big.Int
   384  	if opt, ok := c.(combinedMult); ok {
   385  		x, y = opt.CombinedMult(pub.X, pub.Y, u1.Bytes(), u2.Bytes())
   386  	} else {
   387  		x1, y1 := c.ScalarBaseMult(u1.Bytes())
   388  		x2, y2 := c.ScalarMult(pub.X, pub.Y, u2.Bytes())
   389  		x, y = c.Add(x1, y1, x2, y2)
   390  	}
   391  
   392  	if x.Sign() == 0 && y.Sign() == 0 {
   393  		return false
   394  	}
   395  	x.Mod(x, N)
   396  	return x.Cmp(r) == 0
   397  }
   398  
   399  // VerifyASN1 verifies the ASN.1 encoded signature, sig, of hash using the
   400  // public key, pub. Its return value records whether the signature is valid.
   401  func VerifyASN1(pub *PublicKey, hash, sig []byte) bool {
   402  	var (
   403  		r, s  = &big.Int{}, &big.Int{}
   404  		inner cryptobyte.String
   405  	)
   406  	input := cryptobyte.String(sig)
   407  	if !input.ReadASN1(&inner, asn1.SEQUENCE) ||
   408  		!input.Empty() ||
   409  		!inner.ReadASN1Integer(r) ||
   410  		!inner.ReadASN1Integer(s) ||
   411  		!inner.Empty() {
   412  		return false
   413  	}
   414  	return Verify(pub, hash, r, s)
   415  }
   416  
   417  type zr struct{}
   418  
   419  // Read replaces the contents of dst with zeros. It is safe for concurrent use.
   420  func (zr) Read(dst []byte) (n int, err error) {
   421  	for i := range dst {
   422  		dst[i] = 0
   423  	}
   424  	return len(dst), nil
   425  }
   426  
   427  var zeroReader = zr{}
   428
View as plain text