1
2
3
4
5
6
7
8
9
10
11 package ecdsa
12
13
14
15
16
17
18
19 import (
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 "crypto/internal/randutil"
31 )
32
33
34 type invertible interface {
35
36 Inverse(k *big.Int) *big.Int
37 }
38
39
40 type combinedMult interface {
41 CombinedMult(bigX, bigY *big.Int, baseScalar, scalar []byte) (x, y *big.Int)
42 }
43
44 const (
45 aesIV = "IV for ECDSA CTR"
46 )
47
48
49 type PublicKey struct {
50 elliptic.Curve
51 X, Y *big.Int
52 }
53
54
55 type PrivateKey struct {
56 PublicKey
57 D *big.Int
58 }
59
60 type ecdsaSignature struct {
61 R, S *big.Int
62 }
63
64
65 func (priv *PrivateKey) Public() crypto.PublicKey {
66 return &priv.PublicKey
67 }
68
69
70
71
72
73
74
75
76 func (priv *PrivateKey) Sign(rand io.Reader, digest []byte, opts crypto.SignerOpts) ([]byte, error) {
77 r, s, err := Sign(rand, priv, digest)
78 if err != nil {
79 return nil, err
80 }
81
82 return asn1.Marshal(ecdsaSignature{r, s})
83 }
84
85 var one = new(big.Int).SetInt64(1)
86
87
88
89 func randFieldElement(c elliptic.Curve, rand io.Reader) (k *big.Int, err error) {
90 params := c.Params()
91 b := make([]byte, params.BitSize/8+8)
92 _, err = io.ReadFull(rand, b)
93 if err != nil {
94 return
95 }
96
97 k = new(big.Int).SetBytes(b)
98 n := new(big.Int).Sub(params.N, one)
99 k.Mod(k, n)
100 k.Add(k, one)
101 return
102 }
103
104
105 func GenerateKey(c elliptic.Curve, rand io.Reader) (*PrivateKey, error) {
106 k, err := randFieldElement(c, rand)
107 if err != nil {
108 return nil, err
109 }
110
111 priv := new(PrivateKey)
112 priv.PublicKey.Curve = c
113 priv.D = k
114 priv.PublicKey.X, priv.PublicKey.Y = c.ScalarBaseMult(k.Bytes())
115 return priv, nil
116 }
117
118
119
120
121
122
123
124 func hashToInt(hash []byte, c elliptic.Curve) *big.Int {
125 orderBits := c.Params().N.BitLen()
126 orderBytes := (orderBits + 7) / 8
127 if len(hash) > orderBytes {
128 hash = hash[:orderBytes]
129 }
130
131 ret := new(big.Int).SetBytes(hash)
132 excess := len(hash)*8 - orderBits
133 if excess > 0 {
134 ret.Rsh(ret, uint(excess))
135 }
136 return ret
137 }
138
139
140
141
142
143 func fermatInverse(k, N *big.Int) *big.Int {
144 two := big.NewInt(2)
145 nMinus2 := new(big.Int).Sub(N, two)
146 return new(big.Int).Exp(k, nMinus2, N)
147 }
148
149 var errZeroParam = errors.New("zero parameter")
150
151
152
153
154
155
156 func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) {
157 randutil.MaybeReadByte(rand)
158
159
160 entropylen := (priv.Curve.Params().BitSize + 7) / 16
161 if entropylen > 32 {
162 entropylen = 32
163 }
164 entropy := make([]byte, entropylen)
165 _, err = io.ReadFull(rand, entropy)
166 if err != nil {
167 return
168 }
169
170
171 md := sha512.New()
172 md.Write(priv.D.Bytes())
173 md.Write(entropy)
174 md.Write(hash)
175 key := md.Sum(nil)[:32]
176
177
178
179 block, err := aes.NewCipher(key)
180 if err != nil {
181 return nil, nil, err
182 }
183
184
185
186 csprng := cipher.StreamReader{
187 R: zeroReader,
188 S: cipher.NewCTR(block, []byte(aesIV)),
189 }
190
191
192 c := priv.PublicKey.Curve
193 N := c.Params().N
194 if N.Sign() == 0 {
195 return nil, nil, errZeroParam
196 }
197 var k, kInv *big.Int
198 for {
199 for {
200 k, err = randFieldElement(c, csprng)
201 if err != nil {
202 r = nil
203 return
204 }
205
206 if in, ok := priv.Curve.(invertible); ok {
207 kInv = in.Inverse(k)
208 } else {
209 kInv = fermatInverse(k, N)
210 }
211
212 r, _ = priv.Curve.ScalarBaseMult(k.Bytes())
213 r.Mod(r, N)
214 if r.Sign() != 0 {
215 break
216 }
217 }
218
219 e := hashToInt(hash, c)
220 s = new(big.Int).Mul(priv.D, r)
221 s.Add(s, e)
222 s.Mul(s, kInv)
223 s.Mod(s, N)
224 if s.Sign() != 0 {
225 break
226 }
227 }
228
229 return
230 }
231
232
233
234 func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
235
236 c := pub.Curve
237 N := c.Params().N
238
239 if r.Sign() <= 0 || s.Sign() <= 0 {
240 return false
241 }
242 if r.Cmp(N) >= 0 || s.Cmp(N) >= 0 {
243 return false
244 }
245 e := hashToInt(hash, c)
246
247 var w *big.Int
248 if in, ok := c.(invertible); ok {
249 w = in.Inverse(s)
250 } else {
251 w = new(big.Int).ModInverse(s, N)
252 }
253
254 u1 := e.Mul(e, w)
255 u1.Mod(u1, N)
256 u2 := w.Mul(r, w)
257 u2.Mod(u2, N)
258
259
260 var x, y *big.Int
261 if opt, ok := c.(combinedMult); ok {
262 x, y = opt.CombinedMult(pub.X, pub.Y, u1.Bytes(), u2.Bytes())
263 } else {
264 x1, y1 := c.ScalarBaseMult(u1.Bytes())
265 x2, y2 := c.ScalarMult(pub.X, pub.Y, u2.Bytes())
266 x, y = c.Add(x1, y1, x2, y2)
267 }
268
269 if x.Sign() == 0 && y.Sign() == 0 {
270 return false
271 }
272 x.Mod(x, N)
273 return x.Cmp(r) == 0
274 }
275
276 type zr struct {
277 io.Reader
278 }
279
280
281 func (z *zr) Read(dst []byte) (n int, err error) {
282 for i := range dst {
283 dst[i] = 0
284 }
285 return len(dst), nil
286 }
287
288 var zeroReader = &zr{}
289
View as plain text