1
2
3
4
5
6
7
8
9
10
11 package ecdsa
12
13
14
15
16
17
18
19
20
21
22 import (
23 "crypto"
24 "crypto/aes"
25 "crypto/cipher"
26 "crypto/elliptic"
27 "crypto/internal/boring"
28 "crypto/internal/boring/bbig"
29 "crypto/internal/randutil"
30 "crypto/sha512"
31 "errors"
32 "io"
33 "math/big"
34
35 "golang.org/x/crypto/cryptobyte"
36 "golang.org/x/crypto/cryptobyte/asn1"
37 )
38
39
40 type invertible interface {
41
42 Inverse(k *big.Int) *big.Int
43 }
44
45
46 type combinedMult interface {
47
48 CombinedMult(Px, Py *big.Int, s1, s2 []byte) (x, y *big.Int)
49 }
50
51 const (
52 aesIV = "IV for ECDSA CTR"
53 )
54
55
56 type PublicKey struct {
57 elliptic.Curve
58 X, Y *big.Int
59 }
60
61
62
63
64
65
66
67
68
69 func (pub *PublicKey) Equal(x crypto.PublicKey) bool {
70 xx, ok := x.(*PublicKey)
71 if !ok {
72 return false
73 }
74 return pub.X.Cmp(xx.X) == 0 && pub.Y.Cmp(xx.Y) == 0 &&
75
76
77
78
79 pub.Curve == xx.Curve
80 }
81
82
83 type PrivateKey struct {
84 PublicKey
85 D *big.Int
86 }
87
88
89 func (priv *PrivateKey) Public() crypto.PublicKey {
90 return &priv.PublicKey
91 }
92
93
94
95
96 func (priv *PrivateKey) Equal(x crypto.PrivateKey) bool {
97 xx, ok := x.(*PrivateKey)
98 if !ok {
99 return false
100 }
101 return priv.PublicKey.Equal(&xx.PublicKey) && priv.D.Cmp(xx.D) == 0
102 }
103
104
105
106
107
108
109
110
111 func (priv *PrivateKey) Sign(rand io.Reader, digest []byte, opts crypto.SignerOpts) ([]byte, error) {
112 if boring.Enabled && rand == boring.RandReader {
113 b, err := boringPrivateKey(priv)
114 if err != nil {
115 return nil, err
116 }
117 return boring.SignMarshalECDSA(b, digest)
118 }
119 boring.UnreachableExceptTests()
120
121 r, s, err := Sign(rand, priv, digest)
122 if err != nil {
123 return nil, err
124 }
125
126 var b cryptobyte.Builder
127 b.AddASN1(asn1.SEQUENCE, func(b *cryptobyte.Builder) {
128 b.AddASN1BigInt(r)
129 b.AddASN1BigInt(s)
130 })
131 return b.Bytes()
132 }
133
134 var one = new(big.Int).SetInt64(1)
135
136
137
138 func randFieldElement(c elliptic.Curve, rand io.Reader) (k *big.Int, err error) {
139 params := c.Params()
140
141
142 b := make([]byte, params.N.BitLen()/8+8)
143 _, err = io.ReadFull(rand, b)
144 if err != nil {
145 return
146 }
147
148 k = new(big.Int).SetBytes(b)
149 n := new(big.Int).Sub(params.N, one)
150 k.Mod(k, n)
151 k.Add(k, one)
152 return
153 }
154
155
156 func GenerateKey(c elliptic.Curve, rand io.Reader) (*PrivateKey, error) {
157 if boring.Enabled && rand == boring.RandReader {
158 x, y, d, err := boring.GenerateKeyECDSA(c.Params().Name)
159 if err != nil {
160 return nil, err
161 }
162 return &PrivateKey{PublicKey: PublicKey{Curve: c, X: bbig.Dec(x), Y: bbig.Dec(y)}, D: bbig.Dec(d)}, nil
163 }
164 boring.UnreachableExceptTests()
165
166 k, err := randFieldElement(c, rand)
167 if err != nil {
168 return nil, err
169 }
170
171 priv := new(PrivateKey)
172 priv.PublicKey.Curve = c
173 priv.D = k
174 priv.PublicKey.X, priv.PublicKey.Y = c.ScalarBaseMult(k.Bytes())
175 return priv, nil
176 }
177
178
179
180
181 func hashToInt(hash []byte, c elliptic.Curve) *big.Int {
182 orderBits := c.Params().N.BitLen()
183 orderBytes := (orderBits + 7) / 8
184 if len(hash) > orderBytes {
185 hash = hash[:orderBytes]
186 }
187
188 ret := new(big.Int).SetBytes(hash)
189 excess := len(hash)*8 - orderBits
190 if excess > 0 {
191 ret.Rsh(ret, uint(excess))
192 }
193 return ret
194 }
195
196
197
198
199
200
201 func fermatInverse(k, N *big.Int) *big.Int {
202 two := big.NewInt(2)
203 nMinus2 := new(big.Int).Sub(N, two)
204 return new(big.Int).Exp(k, nMinus2, N)
205 }
206
207 var errZeroParam = errors.New("zero parameter")
208
209
210
211
212
213
214 func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) {
215 randutil.MaybeReadByte(rand)
216
217 if boring.Enabled && rand == boring.RandReader {
218 b, err := boringPrivateKey(priv)
219 if err != nil {
220 return nil, nil, err
221 }
222 sig, err := boring.SignMarshalECDSA(b, hash)
223 if err != nil {
224 return nil, nil, err
225 }
226 var r, s big.Int
227 var inner cryptobyte.String
228 input := cryptobyte.String(sig)
229 if !input.ReadASN1(&inner, asn1.SEQUENCE) ||
230 !input.Empty() ||
231 !inner.ReadASN1Integer(&r) ||
232 !inner.ReadASN1Integer(&s) ||
233 !inner.Empty() {
234 return nil, nil, errors.New("invalid ASN.1 from boringcrypto")
235 }
236 return &r, &s, nil
237 }
238 boring.UnreachableExceptTests()
239
240
241
242
243
244
245
246
247
248
249
250
251
252 entropy := make([]byte, 32)
253 _, err = io.ReadFull(rand, entropy)
254 if err != nil {
255 return
256 }
257
258
259 md := sha512.New()
260 md.Write(priv.D.Bytes())
261 md.Write(entropy)
262 md.Write(hash)
263 key := md.Sum(nil)[:32]
264
265
266
267 block, err := aes.NewCipher(key)
268 if err != nil {
269 return nil, nil, err
270 }
271
272
273
274 csprng := &cipher.StreamReader{
275 R: zeroReader,
276 S: cipher.NewCTR(block, []byte(aesIV)),
277 }
278
279 c := priv.PublicKey.Curve
280 return sign(priv, csprng, c, hash)
281 }
282
283 func signGeneric(priv *PrivateKey, csprng *cipher.StreamReader, c elliptic.Curve, hash []byte) (r, s *big.Int, err error) {
284
285 N := c.Params().N
286 if N.Sign() == 0 {
287 return nil, nil, errZeroParam
288 }
289 var k, kInv *big.Int
290 for {
291 for {
292 k, err = randFieldElement(c, *csprng)
293 if err != nil {
294 r = nil
295 return
296 }
297
298 if in, ok := priv.Curve.(invertible); ok {
299 kInv = in.Inverse(k)
300 } else {
301 kInv = fermatInverse(k, N)
302 }
303
304 r, _ = priv.Curve.ScalarBaseMult(k.Bytes())
305 r.Mod(r, N)
306 if r.Sign() != 0 {
307 break
308 }
309 }
310
311 e := hashToInt(hash, c)
312 s = new(big.Int).Mul(priv.D, r)
313 s.Add(s, e)
314 s.Mul(s, kInv)
315 s.Mod(s, N)
316 if s.Sign() != 0 {
317 break
318 }
319 }
320
321 return
322 }
323
324
325
326
327
328 func SignASN1(rand io.Reader, priv *PrivateKey, hash []byte) ([]byte, error) {
329 return priv.Sign(rand, hash, nil)
330 }
331
332
333
334
335 func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
336 if boring.Enabled {
337 key, err := boringPublicKey(pub)
338 if err != nil {
339 return false
340 }
341 var b cryptobyte.Builder
342 b.AddASN1(asn1.SEQUENCE, func(b *cryptobyte.Builder) {
343 b.AddASN1BigInt(r)
344 b.AddASN1BigInt(s)
345 })
346 sig, err := b.Bytes()
347 if err != nil {
348 return false
349 }
350 return boring.VerifyECDSA(key, hash, sig)
351 }
352 boring.UnreachableExceptTests()
353
354 c := pub.Curve
355 N := c.Params().N
356
357 if r.Sign() <= 0 || s.Sign() <= 0 {
358 return false
359 }
360 if r.Cmp(N) >= 0 || s.Cmp(N) >= 0 {
361 return false
362 }
363 return verify(pub, c, hash, r, s)
364 }
365
366 func verifyGeneric(pub *PublicKey, c elliptic.Curve, hash []byte, r, s *big.Int) bool {
367
368 e := hashToInt(hash, c)
369 var w *big.Int
370 N := c.Params().N
371 if in, ok := c.(invertible); ok {
372 w = in.Inverse(s)
373 } else {
374 w = new(big.Int).ModInverse(s, N)
375 }
376
377 u1 := e.Mul(e, w)
378 u1.Mod(u1, N)
379 u2 := w.Mul(r, w)
380 u2.Mod(u2, N)
381
382
383 var x, y *big.Int
384 if opt, ok := c.(combinedMult); ok {
385 x, y = opt.CombinedMult(pub.X, pub.Y, u1.Bytes(), u2.Bytes())
386 } else {
387 x1, y1 := c.ScalarBaseMult(u1.Bytes())
388 x2, y2 := c.ScalarMult(pub.X, pub.Y, u2.Bytes())
389 x, y = c.Add(x1, y1, x2, y2)
390 }
391
392 if x.Sign() == 0 && y.Sign() == 0 {
393 return false
394 }
395 x.Mod(x, N)
396 return x.Cmp(r) == 0
397 }
398
399
400
401 func VerifyASN1(pub *PublicKey, hash, sig []byte) bool {
402 var (
403 r, s = &big.Int{}, &big.Int{}
404 inner cryptobyte.String
405 )
406 input := cryptobyte.String(sig)
407 if !input.ReadASN1(&inner, asn1.SEQUENCE) ||
408 !input.Empty() ||
409 !inner.ReadASN1Integer(r) ||
410 !inner.ReadASN1Integer(s) ||
411 !inner.Empty() {
412 return false
413 }
414 return Verify(pub, hash, r, s)
415 }
416
417 type zr struct{}
418
419
420 func (zr) Read(dst []byte) (n int, err error) {
421 for i := range dst {
422 dst[i] = 0
423 }
424 return len(dst), nil
425 }
426
427 var zeroReader = zr{}
428
View as plain text