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.
7package ecdsa
8
9// References:
10//   [NSA]: Suite B implementer's guide to FIPS 186-3,
11//     http://www.nsa.gov/ia/_files/ecdsa.pdf
12//   [SECG]: SECG, SEC1
13//     http://www.secg.org/download/aid-780/sec1-v2.pdf
14
15import (
16	"crypto/elliptic"
17	"io"
18	"math/big"
19)
20
21// PublicKey represents an ECDSA public key.
22type PublicKey struct {
23	elliptic.Curve
24	X, Y *big.Int
25}
26
27// PrivateKey represents a ECDSA private key.
28type PrivateKey struct {
29	PublicKey
30	D *big.Int
31}
32
33var one = new(big.Int).SetInt64(1)
34
35// randFieldElement returns a random element of the field underlying the given
36// curve using the procedure given in [NSA] A.2.1.
37func randFieldElement(c elliptic.Curve, rand io.Reader) (k *big.Int, err error) {
38	params := c.Params()
39	b := make([]byte, params.BitSize/8+8)
40	_, err = io.ReadFull(rand, b)
41	if err != nil {
42		return
43	}
44
45	k = new(big.Int).SetBytes(b)
46	n := new(big.Int).Sub(params.N, one)
47	k.Mod(k, n)
48	k.Add(k, one)
49	return
50}
51
52// GenerateKey generates a public and private key pair.
53func GenerateKey(c elliptic.Curve, rand io.Reader) (priv *PrivateKey, err error) {
54	k, err := randFieldElement(c, rand)
55	if err != nil {
56		return
57	}
58
59	priv = new(PrivateKey)
60	priv.PublicKey.Curve = c
61	priv.D = k
62	priv.PublicKey.X, priv.PublicKey.Y = c.ScalarBaseMult(k.Bytes())
63	return
64}
65
66// hashToInt converts a hash value to an integer. There is some disagreement
67// about how this is done. [NSA] suggests that this is done in the obvious
68// manner, but [SECG] truncates the hash to the bit-length of the curve order
69// first. We follow [SECG] because that's what OpenSSL does. Additionally,
70// OpenSSL right shifts excess bits from the number if the hash is too large
71// and we mirror that too.
72func hashToInt(hash []byte, c elliptic.Curve) *big.Int {
73	orderBits := c.Params().N.BitLen()
74	orderBytes := (orderBits + 7) / 8
75	if len(hash) > orderBytes {
76		hash = hash[:orderBytes]
77	}
78
79	ret := new(big.Int).SetBytes(hash)
80	excess := len(hash)*8 - orderBits
81	if excess > 0 {
82		ret.Rsh(ret, uint(excess))
83	}
84	return ret
85}
86
87// Sign signs an arbitrary length hash (which should be the result of hashing a
88// larger message) using the private key, priv. It returns the signature as a
89// pair of integers. The security of the private key depends on the entropy of
90// rand.
91func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) {
92	// See [NSA] 3.4.1
93	c := priv.PublicKey.Curve
94	N := c.Params().N
95
96	var k, kInv *big.Int
97	for {
98		for {
99			k, err = randFieldElement(c, rand)
100			if err != nil {
101				r = nil
102				return
103			}
104
105			kInv = new(big.Int).ModInverse(k, N)
106			r, _ = priv.Curve.ScalarBaseMult(k.Bytes())
107			r.Mod(r, N)
108			if r.Sign() != 0 {
109				break
110			}
111		}
112
113		e := hashToInt(hash, c)
114		s = new(big.Int).Mul(priv.D, r)
115		s.Add(s, e)
116		s.Mul(s, kInv)
117		s.Mod(s, N)
118		if s.Sign() != 0 {
119			break
120		}
121	}
122
123	return
124}
125
126// Verify verifies the signature in r, s of hash using the public key, pub. Its
127// return value records whether the signature is valid.
128func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
129	// See [NSA] 3.4.2
130	c := pub.Curve
131	N := c.Params().N
132
133	if r.Sign() == 0 || s.Sign() == 0 {
134		return false
135	}
136	if r.Cmp(N) >= 0 || s.Cmp(N) >= 0 {
137		return false
138	}
139	e := hashToInt(hash, c)
140	w := new(big.Int).ModInverse(s, N)
141
142	u1 := e.Mul(e, w)
143	u1.Mod(u1, N)
144	u2 := w.Mul(r, w)
145	u2.Mod(u2, N)
146
147	x1, y1 := c.ScalarBaseMult(u1.Bytes())
148	x2, y2 := c.ScalarMult(pub.X, pub.Y, u2.Bytes())
149	x, y := c.Add(x1, y1, x2, y2)
150	if x.Sign() == 0 && y.Sign() == 0 {
151		return false
152	}
153	x.Mod(x, N)
154	return x.Cmp(r) == 0
155}
156