// 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"
"unsafe"
)
-// 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 (
//
// 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) {
if boring.Enabled && rand == boring.RandReader {
b, err := boringPrivateKey(priv)
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
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
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)
// 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)
}
boring.UnreachableExceptTests()
+ // 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)
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,
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
// 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 {
if boring.Enabled {
b, err := boringPublicKey(pub)
}
boring.UnreachableExceptTests()
- // See [NSA] 3.4.2
c := pub.Curve
N := c.Params().N
}
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