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>

3 files changed, 75 insertions, 68 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
diff --git a/src/crypto/elliptic/elliptic.go b/src/crypto/elliptic/elliptic.go
index d06a284154..c5c5a906c4 100644
--- a/src/crypto/elliptic/elliptic.go
+++ b/src/crypto/elliptic/elliptic.go
@@ -2,17 +2,10 @@
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
-// Package elliptic implements several standard elliptic curves over prime
-// fields.
+// Package elliptic implements the standard NIST P-224, P-256, P-384, and P-521
+// elliptic curves over prime fields.
 package elliptic
 
-// This package operates, internally, on Jacobian coordinates. For a given
-// (x, y) position on the curve, the Jacobian coordinates are (x1, y1, z1)
-// where x = x1/z1² and y = y1/z1³. The greatest speedups come when the whole
-// calculation can be performed within the transform (as in ScalarMult and
-// ScalarBaseMult). But even for Add and Double, it's faster to apply and
-// reverse the transform than to operate in affine coordinates.
-
 import (
 	"io"
 	"math/big"
@@ -21,12 +14,12 @@ import (
 
 // A Curve represents a short-form Weierstrass curve with a=-3.
 //
-// The output of Add, Double, and ScalarMult when the input is not a point on
+// The behavior of Add, Double, and ScalarMult when the input is not a point on
 // the curve is undefined.
 //
 // Note that the conventional point at infinity (0, 0) is not considered on the
 // curve, although it can be returned by Add, Double, ScalarMult, or
-// ScalarBaseMult (but not Unmarshal or UnmarshalCompressed).
+// ScalarBaseMult (but not the Unmarshal or UnmarshalCompressed functions).
 type Curve interface {
 	// Params returns the parameters for the curve.
 	Params() *CurveParams
@@ -67,6 +60,13 @@ func (curve *CurveParams) Params() *CurveParams {
 	return curve
 }
 
+// CurveParams operates, internally, on Jacobian coordinates. For a given
+// (x, y) position on the curve, the Jacobian coordinates are (x1, y1, z1)
+// where x = x1/z1² and y = y1/z1³. The greatest speedups come when the whole
+// calculation can be performed within the transform (as in ScalarMult and
+// ScalarBaseMult). But even for Add and Double, it's faster to apply and
+// reverse the transform than to operate in affine coordinates.
+
 // polynomial returns x³ - 3x + b.
 func (curve *CurveParams) polynomial(x *big.Int) *big.Int {
 	x3 := new(big.Int).Mul(x, x)
@@ -353,7 +353,8 @@ func GenerateKey(curve Curve, rand io.Reader) (priv []byte, x, y *big.Int, err e
 }
 
 // Marshal converts a point on the curve into the uncompressed form specified in
-// section 4.3.6 of ANSI X9.62.
+// SEC 1, Version 2.0, Section 2.3.3. If the point is not on the curve (or is
+// the conventional point at infinity), the behavior is undefined.
 func Marshal(curve Curve, x, y *big.Int) []byte {
 	byteLen := (curve.Params().BitSize + 7) / 8
 
@@ -367,7 +368,8 @@ func Marshal(curve Curve, x, y *big.Int) []byte {
 }
 
 // MarshalCompressed converts a point on the curve into the compressed form
-// specified in section 4.3.6 of ANSI X9.62.
+// specified in SEC 1, Version 2.0, Section 2.3.3. If the point is not on the
+// curve (or is the conventional point at infinity), the behavior is undefined.
 func MarshalCompressed(curve Curve, x, y *big.Int) []byte {
 	byteLen := (curve.Params().BitSize + 7) / 8
 	compressed := make([]byte, 1+byteLen)
@@ -376,9 +378,9 @@ func MarshalCompressed(curve Curve, x, y *big.Int) []byte {
 	return compressed
 }
 
-// Unmarshal converts a point, serialized by Marshal, into an x, y pair.
-// It is an error if the point is not in uncompressed form or is not on the curve.
-// On error, x = nil.
+// Unmarshal converts a point, serialized by Marshal, into an x, y pair. It is
+// an error if the point is not in uncompressed form, is not on the curve, or is
+// the point at infinity. On error, x = nil.
 func Unmarshal(curve Curve, data []byte) (x, y *big.Int) {
 	byteLen := (curve.Params().BitSize + 7) / 8
 	if len(data) != 1+2*byteLen {
@@ -399,9 +401,9 @@ func Unmarshal(curve Curve, data []byte) (x, y *big.Int) {
 	return
 }
 
-// UnmarshalCompressed converts a point, serialized by MarshalCompressed, into an x, y pair.
-// It is an error if the point is not in compressed form or is not on the curve.
-// On error, x = nil.
+// UnmarshalCompressed converts a point, serialized by MarshalCompressed, into
+// an x, y pair. It is an error if the point is not in compressed form, is not
+// on the curve, or is the point at infinity. On error, x = nil.
 func UnmarshalCompressed(curve Curve, data []byte) (x, y *big.Int) {
 	byteLen := (curve.Params().BitSize + 7) / 8
 	if len(data) != 1+byteLen {
diff --git a/src/crypto/elliptic/p256.go b/src/crypto/elliptic/p256.go
index 7ff7e33548..e1c6ff4f87 100644
--- a/src/crypto/elliptic/p256.go
+++ b/src/crypto/elliptic/p256.go
@@ -6,11 +6,11 @@
 
 package elliptic
 
-// This file contains a constant-time, 32-bit implementation of P256.
+// P-256 is implemented by various different backends, including a generic
+// 32-bit constant-time one in this file, which is used when assembly
+// implementations are not available, or not appropriate for the hardware.
 
-import (
-	"math/big"
-)
+import "math/big"
 
 type p256Curve struct {
 	*CurveParams