Source: ecdsa.go in package crypto/ecdsa

Package ecdsa implements the Elliptic Curve Digital Signature Algorithm, as defined in FIPS 186-3. 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://www.nada.kth.se/kurser/kth/2D1441/semteo03/lecturenotes/assump.pdf

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


import (
	"crypto"
	"crypto/aes"
	"crypto/cipher"
	"crypto/elliptic"
	"crypto/internal/randutil"
	"crypto/sha512"
	"errors"
	"io"
	"math/big"

	"golang.org/x/crypto/cryptobyte"
	"golang.org/x/crypto/cryptobyte/asn1"
)

A invertible implements fast inverse mod Curve.Params().N

Inverse returns the inverse of k in GF(P)

	Inverse(k *big.Int) *big.Int
}

combinedMult implements fast multiplication S1*g + S2*p (g - generator, p - arbitrary point)

type combinedMult interface {
	CombinedMult(bigX, bigY *big.Int, baseScalar, scalar []byte) (x, y *big.Int)
}

const (
	aesIV = "IV for ECDSA CTR"
)

PublicKey represents an ECDSA public key.

type PublicKey struct {
	elliptic.Curve
	X, Y *big.Int
}

Any methods implemented on PublicKey might need to also be implemented on PrivateKey, as the latter embeds the former and will expose its methods.

Equal reports whether pub and x have the same value. Two keys are only considered to have the same value if they have the same Curve value. Note that for example elliptic.P256() and elliptic.P256().Params() are different values, as the latter is a generic not constant time implementation.

func (pub *PublicKey) Equal(x crypto.PublicKey) bool {
	xx, ok := x.(*PublicKey)
	if !ok {
		return false
	}

Standard library Curve implementations are singletons, so this check will work for those. Other Curves might be equivalent even if not singletons, but there is no definitive way to check for that, and better to err on the side of safety.

		pub.Curve == xx.Curve
}

PrivateKey represents an ECDSA private key.

type PrivateKey struct {
	PublicKey
	D *big.Int
}

Public returns the public key corresponding to priv.

func (priv *PrivateKey) Public() crypto.PublicKey {
	return &priv.PublicKey
}

Equal reports whether priv and x have the same value. See PublicKey.Equal for details on how Curve is compared.

func (priv *PrivateKey) Equal(x crypto.PrivateKey) bool {
	xx, ok := x.(*PrivateKey)
	if !ok {
		return false
	}
	return priv.PublicKey.Equal(&xx.PublicKey) && priv.D.Cmp(xx.D) == 0
}

Sign signs digest with priv, reading randomness from rand. The opts argument is not currently used but, in keeping with the crypto.Signer interface, should be the hash function used to digest the message. 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.

func (priv *PrivateKey) Sign(rand io.Reader, digest []byte, opts crypto.SignerOpts) ([]byte, error) {
	r, s, err := Sign(rand, priv, digest)
	if err != nil {
		return nil, err
	}

	var b cryptobyte.Builder
	b.AddASN1(asn1.SEQUENCE, func(b *cryptobyte.Builder) {
		b.AddASN1BigInt(r)
		b.AddASN1BigInt(s)
	})
	return b.Bytes()
}

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.

func randFieldElement(c elliptic.Curve, rand io.Reader) (k *big.Int, err error) {
	params := c.Params()
	b := make([]byte, params.BitSize/8+8)
	_, err = io.ReadFull(rand, b)
	if err != nil {
		return
	}

	k = new(big.Int).SetBytes(b)
	n := new(big.Int).Sub(params.N, one)
	k.Mod(k, n)
	k.Add(k, one)
	return
}

GenerateKey generates a public and private key pair.

func GenerateKey(c elliptic.Curve, rand io.Reader) (*PrivateKey, error) {
	k, err := randFieldElement(c, rand)
	if err != nil {
		return nil, err
	}

	priv := new(PrivateKey)
	priv.PublicKey.Curve = c
	priv.D = k
	priv.PublicKey.X, priv.PublicKey.Y = c.ScalarBaseMult(k.Bytes())
	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.

func hashToInt(hash []byte, c elliptic.Curve) *big.Int {
	orderBits := c.Params().N.BitLen()
	orderBytes := (orderBits + 7) / 8
	if len(hash) > orderBytes {
		hash = hash[:orderBytes]
	}

	ret := new(big.Int).SetBytes(hash)
	excess := len(hash)*8 - orderBits
	if excess > 0 {
		ret.Rsh(ret, uint(excess))
	}
	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.

func fermatInverse(k, N *big.Int) *big.Int {
	two := big.NewInt(2)
	nMinus2 := new(big.Int).Sub(N, two)
	return new(big.Int).Exp(k, nMinus2, N)
}

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.

func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) {
	randutil.MaybeReadByte(rand)

Get min(log2(q) / 2, 256) bits of entropy from rand.

	entropylen := (priv.Curve.Params().BitSize + 7) / 16
	if entropylen > 32 {
		entropylen = 32
	}
	entropy := make([]byte, entropylen)
	_, err = io.ReadFull(rand, entropy)
	if err != nil {
		return
	}

Initialize an SHA-512 hash context; digest ...

	md := sha512.New()
	md.Write(priv.D.Bytes()) // the private key,
	md.Write(entropy)        // the entropy,
	md.Write(hash)           // and the input hash;

which is an indifferentiable MAC.

Create an AES-CTR instance to use as a CSPRNG.

	block, err := aes.NewCipher(key)
	if err != nil {
		return nil, nil, err
	}

Create a CSPRNG that xors a stream of zeros with the output of the AES-CTR instance.

	csprng := cipher.StreamReader{
		R: zeroReader,
		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) {
	N := c.Params().N
	if N.Sign() == 0 {
		return nil, nil, errZeroParam
	}
	var k, kInv *big.Int
	for {
		for {
			k, err = randFieldElement(c, *csprng)
			if err != nil {
				r = nil
				return
			}

			if in, ok := priv.Curve.(invertible); ok {
				kInv = in.Inverse(k)
			} else {
				kInv = fermatInverse(k, N) // N != 0
			}

			r, _ = priv.Curve.ScalarBaseMult(k.Bytes())
			r.Mod(r, N)
			if r.Sign() != 0 {
				break
			}
		}

		e := hashToInt(hash, c)
		s = new(big.Int).Mul(priv.D, r)
		s.Add(s, e)
		s.Mul(s, kInv)
		s.Mod(s, N) // N != 0
		if s.Sign() != 0 {
			break
		}
	}

	return
}

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.

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.

See [NSA] 3.4.2

	c := pub.Curve
	N := c.Params().N

	if r.Sign() <= 0 || s.Sign() <= 0 {
		return false
	}
	if r.Cmp(N) >= 0 || s.Cmp(N) >= 0 {
		return false
	}
	return verify(pub, c, hash, r, s)
}

func verifyGeneric(pub *PublicKey, c elliptic.Curve, hash []byte, r, s *big.Int) bool {
	e := hashToInt(hash, c)
	var w *big.Int
	N := c.Params().N
	if in, ok := c.(invertible); ok {
		w = in.Inverse(s)
	} else {
		w = new(big.Int).ModInverse(s, N)
	}

	u1 := e.Mul(e, w)
	u1.Mod(u1, N)
	u2 := w.Mul(r, w)
	u2.Mod(u2, N)

Check if implements S1*g + S2*p

	var x, y *big.Int
	if opt, ok := c.(combinedMult); ok {
		x, y = opt.CombinedMult(pub.X, pub.Y, u1.Bytes(), u2.Bytes())
	} else {
		x1, y1 := c.ScalarBaseMult(u1.Bytes())
		x2, y2 := c.ScalarMult(pub.X, pub.Y, u2.Bytes())
		x, y = c.Add(x1, y1, x2, y2)
	}

	if x.Sign() == 0 && y.Sign() == 0 {
		return false
	}
	x.Mod(x, N)
	return x.Cmp(r) == 0
}

VerifyASN1 verifies the ASN.1 encoded signature, sig, of hash using the public key, pub. Its return value records whether the signature is valid.

func VerifyASN1(pub *PublicKey, hash, sig []byte) bool {
	var (
		r, s  = &big.Int{}, &big.Int{}
		inner cryptobyte.String
	)
	input := cryptobyte.String(sig)
	if !input.ReadASN1(&inner, asn1.SEQUENCE) ||
		!input.Empty() ||
		!inner.ReadASN1Integer(r) ||
		!inner.ReadASN1Integer(s) ||
		!inner.Empty() {
		return false
	}
	return Verify(pub, hash, r, s)
}

type zr struct {
	io.Reader
}

Read replaces the contents of dst with zeros.

func (z *zr) Read(dst []byte) (n int, err error) {
	for i := range dst {
		dst[i] = 0
	}
	return len(dst), nil
}