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-3.
7//
8// This implementation  derives the nonce from an AES-CTR CSPRNG keyed by
9// ChopMD(256, SHA2-512(priv.D || entropy || hash)). The CSPRNG key is IRO by
10// a result of Coron; the AES-CTR stream is IRO under standard assumptions.
11package ecdsa
12
13// References:
14//   [NSA]: Suite B implementer's guide to FIPS 186-3,
15//     http://www.nsa.gov/ia/_files/ecdsa.pdf
16//   [SECG]: SECG, SEC1
17//     http://www.secg.org/sec1-v2.pdf
18
19import (
20	"crypto"
21	"crypto/aes"
22	"crypto/cipher"
23	"crypto/elliptic"
24	"crypto/sha512"
25	"encoding/asn1"
26	"errors"
27	"io"
28	"math/big"
29)
30
31// A invertible implements fast inverse mod Curve.Params().N
32type invertible interface {
33	// Inverse returns the inverse of k in GF(P)
34	Inverse(k *big.Int) *big.Int
35}
36
37// combinedMult implements fast multiplication S1*g + S2*p (g - generator, p - arbitrary point)
38type combinedMult interface {
39	CombinedMult(bigX, bigY *big.Int, baseScalar, scalar []byte) (x, y *big.Int)
40}
41
42const (
43	aesIV = "IV for ECDSA CTR"
44)
45
46// PublicKey represents an ECDSA public key.
47type PublicKey struct {
48	elliptic.Curve
49	X, Y *big.Int
50}
51
52// PrivateKey represents a ECDSA private key.
53type PrivateKey struct {
54	PublicKey
55	D *big.Int
56}
57
58type ecdsaSignature struct {
59	R, S *big.Int
60}
61
62// Public returns the public key corresponding to priv.
63func (priv *PrivateKey) Public() crypto.PublicKey {
64	return &priv.PublicKey
65}
66
67// Sign signs msg with priv, reading randomness from rand. This method is
68// intended to support keys where the private part is kept in, for example, a
69// hardware module. Common uses should use the Sign function in this package
70// directly.
71func (priv *PrivateKey) Sign(rand io.Reader, msg []byte, opts crypto.SignerOpts) ([]byte, error) {
72	r, s, err := Sign(rand, priv, msg)
73	if err != nil {
74		return nil, err
75	}
76
77	return asn1.Marshal(ecdsaSignature{r, s})
78}
79
80var one = new(big.Int).SetInt64(1)
81
82// randFieldElement returns a random element of the field underlying the given
83// curve using the procedure given in [NSA] A.2.1.
84func randFieldElement(c elliptic.Curve, rand io.Reader) (k *big.Int, err error) {
85	params := c.Params()
86	b := make([]byte, params.BitSize/8+8)
87	_, err = io.ReadFull(rand, b)
88	if err != nil {
89		return
90	}
91
92	k = new(big.Int).SetBytes(b)
93	n := new(big.Int).Sub(params.N, one)
94	k.Mod(k, n)
95	k.Add(k, one)
96	return
97}
98
99// GenerateKey generates a public and private key pair.
100func GenerateKey(c elliptic.Curve, rand io.Reader) (priv *PrivateKey, err error) {
101	k, err := randFieldElement(c, rand)
102	if err != nil {
103		return
104	}
105
106	priv = new(PrivateKey)
107	priv.PublicKey.Curve = c
108	priv.D = k
109	priv.PublicKey.X, priv.PublicKey.Y = c.ScalarBaseMult(k.Bytes())
110	return
111}
112
113// hashToInt converts a hash value to an integer. There is some disagreement
114// about how this is done. [NSA] suggests that this is done in the obvious
115// manner, but [SECG] truncates the hash to the bit-length of the curve order
116// first. We follow [SECG] because that's what OpenSSL does. Additionally,
117// OpenSSL right shifts excess bits from the number if the hash is too large
118// and we mirror that too.
119func hashToInt(hash []byte, c elliptic.Curve) *big.Int {
120	orderBits := c.Params().N.BitLen()
121	orderBytes := (orderBits + 7) / 8
122	if len(hash) > orderBytes {
123		hash = hash[:orderBytes]
124	}
125
126	ret := new(big.Int).SetBytes(hash)
127	excess := len(hash)*8 - orderBits
128	if excess > 0 {
129		ret.Rsh(ret, uint(excess))
130	}
131	return ret
132}
133
134// fermatInverse calculates the inverse of k in GF(P) using Fermat's method.
135// This has better constant-time properties than Euclid's method (implemented
136// in math/big.Int.ModInverse) although math/big itself isn't strictly
137// constant-time so it's not perfect.
138func fermatInverse(k, N *big.Int) *big.Int {
139	two := big.NewInt(2)
140	nMinus2 := new(big.Int).Sub(N, two)
141	return new(big.Int).Exp(k, nMinus2, N)
142}
143
144var errZeroParam = errors.New("zero parameter")
145
146// Sign signs an arbitrary length hash (which should be the result of hashing a
147// larger message) using the private key, priv. It returns the signature as a
148// pair of integers. The security of the private key depends on the entropy of
149// rand.
150func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) {
151	// Get max(log2(q) / 2, 256) bits of entropy from rand.
152	entropylen := (priv.Curve.Params().BitSize + 7) / 16
153	if entropylen > 32 {
154		entropylen = 32
155	}
156	entropy := make([]byte, entropylen)
157	_, err = io.ReadFull(rand, entropy)
158	if err != nil {
159		return
160	}
161
162	// Initialize an SHA-512 hash context; digest ...
163	md := sha512.New()
164	md.Write(priv.D.Bytes()) // the private key,
165	md.Write(entropy)        // the entropy,
166	md.Write(hash)           // and the input hash;
167	key := md.Sum(nil)[:32]  // and compute ChopMD-256(SHA-512),
168	// which is an indifferentiable MAC.
169
170	// Create an AES-CTR instance to use as a CSPRNG.
171	block, err := aes.NewCipher(key)
172	if err != nil {
173		return nil, nil, err
174	}
175
176	// Create a CSPRNG that xors a stream of zeros with
177	// the output of the AES-CTR instance.
178	csprng := cipher.StreamReader{
179		R: zeroReader,
180		S: cipher.NewCTR(block, []byte(aesIV)),
181	}
182
183	// See [NSA] 3.4.1
184	c := priv.PublicKey.Curve
185	N := c.Params().N
186	if N.Sign() == 0 {
187		return nil, nil, errZeroParam
188	}
189	var k, kInv *big.Int
190	for {
191		for {
192			k, err = randFieldElement(c, csprng)
193			if err != nil {
194				r = nil
195				return
196			}
197
198			if in, ok := priv.Curve.(invertible); ok {
199				kInv = in.Inverse(k)
200			} else {
201				kInv = fermatInverse(k, N) // N != 0
202			}
203
204			r, _ = priv.Curve.ScalarBaseMult(k.Bytes())
205			r.Mod(r, N)
206			if r.Sign() != 0 {
207				break
208			}
209		}
210
211		e := hashToInt(hash, c)
212		s = new(big.Int).Mul(priv.D, r)
213		s.Add(s, e)
214		s.Mul(s, kInv)
215		s.Mod(s, N) // N != 0
216		if s.Sign() != 0 {
217			break
218		}
219	}
220
221	return
222}
223
224// Verify verifies the signature in r, s of hash using the public key, pub. Its
225// return value records whether the signature is valid.
226func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
227	// See [NSA] 3.4.2
228	c := pub.Curve
229	N := c.Params().N
230
231	if r.Sign() == 0 || s.Sign() == 0 {
232		return false
233	}
234	if r.Cmp(N) >= 0 || s.Cmp(N) >= 0 {
235		return false
236	}
237	e := hashToInt(hash, c)
238
239	var w *big.Int
240	if in, ok := c.(invertible); ok {
241		w = in.Inverse(s)
242	} else {
243		w = new(big.Int).ModInverse(s, N)
244	}
245
246	u1 := e.Mul(e, w)
247	u1.Mod(u1, N)
248	u2 := w.Mul(r, w)
249	u2.Mod(u2, N)
250
251	// Check if implements S1*g + S2*p
252	var x, y *big.Int
253	if opt, ok := c.(combinedMult); ok {
254		x, y = opt.CombinedMult(pub.X, pub.Y, u1.Bytes(), u2.Bytes())
255	} else {
256		x1, y1 := c.ScalarBaseMult(u1.Bytes())
257		x2, y2 := c.ScalarMult(pub.X, pub.Y, u2.Bytes())
258		x, y = c.Add(x1, y1, x2, y2)
259	}
260
261	if x.Sign() == 0 && y.Sign() == 0 {
262		return false
263	}
264	x.Mod(x, N)
265	return x.Cmp(r) == 0
266}
267
268type zr struct {
269	io.Reader
270}
271
272// Read replaces the contents of dst with zeros.
273func (z *zr) Read(dst []byte) (n int, err error) {
274	for i := range dst {
275		dst[i] = 0
276	}
277	return len(dst), nil
278}
279
280var zeroReader = &zr{}
281