crypto/ecdsa,crypto/elliptic: update docs and spec references

crypto/ecdsa was long overdue a cleanup. Bump the FIPS 186 version, and
make sure we consistently reference that and SEC 1, not the paywalled
ANSI standard.

Change-Id: Idd90bd6c14b334941fdcd829d89b796a60a8b174
Reviewed-on: https://go-review.googlesource.com/c/go/+/352529
Run-TryBot: Filippo Valsorda <filippo@golang.org>
Trust: Filippo Valsorda <filippo@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Roland Shoemaker <roland@golang.org>

1 files changed, 50 insertions, 45 deletions

diff --git a/src/crypto/ecdsa/ecdsa.go b/src/crypto/ecdsa/ecdsa.go
index 282596d2d2..9f9a09a884 100644
--- a/src/crypto/ecdsa/ecdsa.go
+++ b/src/crypto/ecdsa/ecdsa.go
@@ -3,28 +3,21 @@
 // license that can be found in the LICENSE file.
 
 // Package ecdsa implements the Elliptic Curve Digital Signature Algorithm, as
-// defined in FIPS 186-3.
+// defined in FIPS 186-4 and SEC 1, Version 2.0.
 //
-// This implementation derives the nonce from an AES-CTR CSPRNG keyed by:
-//
-// SHA2-512(priv.D || entropy || hash)[:32]
-//
-// The CSPRNG key is indifferentiable from a random oracle as shown in
-// [Coron], the AES-CTR stream is indifferentiable from a random oracle
-// under standard cryptographic assumptions (see [Larsson] for examples).
-//
-// References:
-//   [Coron]
-//     https://cs.nyu.edu/~dodis/ps/merkle.pdf
-//   [Larsson]
-//     https://web.archive.org/web/20040719170906/https://www.nada.kth.se/kurser/kth/2D1441/semteo03/lecturenotes/assump.pdf
+// Signatures generated by this package are not deterministic, but entropy is
+// mixed with the private key and the message, achieving the same level of
+// security in case of randomness source failure.
 package ecdsa
 
-// Further references:
-//   [NSA]: Suite B implementer's guide to FIPS 186-3
-//     https://apps.nsa.gov/iaarchive/library/ia-guidance/ia-solutions-for-classified/algorithm-guidance/suite-b-implementers-guide-to-fips-186-3-ecdsa.cfm
-//   [SECG]: SECG, SEC1
-//     http://www.secg.org/sec1-v2.pdf
+// [FIPS 186-4] references ANSI X9.62-2005 for the bulk of the ECDSA algorithm.
+// That standard is not freely available, which is a problem in an open source
+// implementation, because not only the implementer, but also any maintainer,
+// contributor, reviewer, auditor, and learner needs access to it. Instead, this
+// package references and follows the equivalent [SEC 1, Version 2.0].
+//
+// [FIPS 186-4]: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf
+// [SEC 1, Version 2.0]: https://www.secg.org/sec1-v2.pdf
 
 import (
 	"crypto"
@@ -41,15 +34,16 @@ import (
 	"golang.org/x/crypto/cryptobyte/asn1"
 )
 
-// A invertible implements fast inverse mod Curve.Params().N
+// A invertible implements fast inverse in GF(N).
 type invertible interface {
-	// Inverse returns the inverse of k in GF(P)
+	// Inverse returns the inverse of k mod Params().N.
 	Inverse(k *big.Int) *big.Int
 }
 
-// combinedMult implements fast multiplication S1*g + S2*p (g - generator, p - arbitrary point)
+// A combinedMult implements fast combined multiplication for verification.
 type combinedMult interface {
-	CombinedMult(bigX, bigY *big.Int, baseScalar, scalar []byte) (x, y *big.Int)
+	// CombinedMult returns [s1]G + [s2]P where G is the generator.
+	CombinedMult(Px, Py *big.Int, s1, s2 []byte) (x, y *big.Int)
 }
 
 const (
@@ -111,7 +105,7 @@ func (priv *PrivateKey) Equal(x crypto.PrivateKey) bool {
 //
 // This method implements crypto.Signer, which is an interface to support keys
 // where the private part is kept in, for example, a hardware module. Common
-// uses should use the Sign function in this package directly.
+// uses can use the SignASN1 function in this package directly.
 func (priv *PrivateKey) Sign(rand io.Reader, digest []byte, opts crypto.SignerOpts) ([]byte, error) {
 	r, s, err := Sign(rand, priv, digest)
 	if err != nil {
@@ -128,11 +122,13 @@ func (priv *PrivateKey) Sign(rand io.Reader, digest []byte, opts crypto.SignerOp
 
 var one = new(big.Int).SetInt64(1)
 
-// randFieldElement returns a random element of the field underlying the given
-// curve using the procedure given in [NSA] A.2.1.
+// randFieldElement returns a random element of the order of the given
+// curve using the procedure given in FIPS 186-4, Appendix B.5.1.
 func randFieldElement(c elliptic.Curve, rand io.Reader) (k *big.Int, err error) {
 	params := c.Params()
-	b := make([]byte, params.BitSize/8+8)
+	// Note that for P-521 this will actually be 63 bits more than the order, as
+	// division rounds down, but the extra bit is inconsequential.
+	b := make([]byte, params.BitSize/8+8) // TODO: use params.N.BitLen()
 	_, err = io.ReadFull(rand, b)
 	if err != nil {
 		return
@@ -159,12 +155,9 @@ func GenerateKey(c elliptic.Curve, rand io.Reader) (*PrivateKey, error) {
 	return priv, nil
 }
 
-// hashToInt converts a hash value to an integer. There is some disagreement
-// about how this is done. [NSA] suggests that this is done in the obvious
-// manner, but [SECG] truncates the hash to the bit-length of the curve order
-// first. We follow [SECG] because that's what OpenSSL does. Additionally,
-// OpenSSL right shifts excess bits from the number if the hash is too large
-// and we mirror that too.
+// hashToInt converts a hash value to an integer. Per FIPS 186-4, Section 6.4,
+// we use the left-most bits of the hash to match the bit-length of the order of
+// the curve. This also performs Step 5 of SEC 1, Version 2.0, Section 4.1.3.
 func hashToInt(hash []byte, c elliptic.Curve) *big.Int {
 	orderBits := c.Params().N.BitLen()
 	orderBytes := (orderBits + 7) / 8
@@ -180,10 +173,11 @@ func hashToInt(hash []byte, c elliptic.Curve) *big.Int {
 	return ret
 }
 
-// fermatInverse calculates the inverse of k in GF(P) using Fermat's method.
-// This has better constant-time properties than Euclid's method (implemented
-// in math/big.Int.ModInverse) although math/big itself isn't strictly
-// constant-time so it's not perfect.
+// fermatInverse calculates the inverse of k in GF(P) using Fermat's method
+// (exponentiation modulo P - 2, per Euler's theorem). This has better
+// constant-time properties than Euclid's method (implemented in
+// math/big.Int.ModInverse and FIPS 186-4, Appendix C.1) although math/big
+// itself isn't strictly constant-time so it's not perfect.
 func fermatInverse(k, N *big.Int) *big.Int {
 	two := big.NewInt(2)
 	nMinus2 := new(big.Int).Sub(N, two)
@@ -195,11 +189,22 @@ var errZeroParam = errors.New("zero parameter")
 // Sign signs a hash (which should be the result of hashing a larger message)
 // using the private key, priv. If the hash is longer than the bit-length of the
 // private key's curve order, the hash will be truncated to that length. It
-// returns the signature as a pair of integers. The security of the private key
-// depends on the entropy of rand.
+// returns the signature as a pair of integers. Most applications should use
+// SignASN1 instead of dealing directly with r, s.
 func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) {
 	randutil.MaybeReadByte(rand)
 
+	// This implementation derives the nonce from an AES-CTR CSPRNG keyed by:
+	//
+	//    SHA2-512(priv.D || entropy || hash)[:32]
+	//
+	// The CSPRNG key is indifferentiable from a random oracle as shown in
+	// [Coron], the AES-CTR stream is indifferentiable from a random oracle
+	// under standard cryptographic assumptions (see [Larsson] for examples).
+	//
+	// [Coron]: https://cs.nyu.edu/~dodis/ps/merkle.pdf
+	// [Larsson]: https://web.archive.org/web/20040719170906/https://www.nada.kth.se/kurser/kth/2D1441/semteo03/lecturenotes/assump.pdf
+
 	// Get 256 bits of entropy from rand.
 	entropy := make([]byte, 32)
 	_, err = io.ReadFull(rand, entropy)
@@ -207,7 +212,7 @@ func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err err
 		return
 	}
 
-	// Initialize an SHA-512 hash context; digest ...
+	// Initialize an SHA-512 hash context; digest...
 	md := sha512.New()
 	md.Write(priv.D.Bytes()) // the private key,
 	md.Write(entropy)        // the entropy,
@@ -228,12 +233,12 @@ func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err err
 		S: cipher.NewCTR(block, []byte(aesIV)),
 	}
 
-	// See [NSA] 3.4.1
 	c := priv.PublicKey.Curve
 	return sign(priv, &csprng, c, hash)
 }
 
 func signGeneric(priv *PrivateKey, csprng *cipher.StreamReader, c elliptic.Curve, hash []byte) (r, s *big.Int, err error) {
+	// SEC 1, Version 2.0, Section 4.1.3
 	N := c.Params().N
 	if N.Sign() == 0 {
 		return nil, nil, errZeroParam
@@ -276,16 +281,15 @@ func signGeneric(priv *PrivateKey, csprng *cipher.StreamReader, c elliptic.Curve
 // SignASN1 signs a hash (which should be the result of hashing a larger message)
 // using the private key, priv. If the hash is longer than the bit-length of the
 // private key's curve order, the hash will be truncated to that length. It
-// returns the ASN.1 encoded signature. The security of the private key
-// depends on the entropy of rand.
+// returns the ASN.1 encoded signature.
 func SignASN1(rand io.Reader, priv *PrivateKey, hash []byte) ([]byte, error) {
 	return priv.Sign(rand, hash, nil)
 }
 
 // Verify verifies the signature in r, s of hash using the public key, pub. Its
-// return value records whether the signature is valid.
+// return value records whether the signature is valid. Most applications should
+// use VerifyASN1 instead of dealing directly with r, s.
 func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
-	// See [NSA] 3.4.2
 	c := pub.Curve
 	N := c.Params().N
 
@@ -299,6 +303,7 @@ func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
 }
 
 func verifyGeneric(pub *PublicKey, c elliptic.Curve, hash []byte, r, s *big.Int) bool {
+	// SEC 1, Version 2.0, Section 4.1.4
 	e := hashToInt(hash, c)
 	var w *big.Int
 	N := c.Params().N