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 "bytes"
24 "crypto"
25 "crypto/aes"
26 "crypto/cipher"
27 "crypto/ecdh"
28 "crypto/elliptic"
29 "crypto/internal/bigmod"
30 "crypto/internal/boring"
31 "crypto/internal/boring/bbig"
32 "crypto/internal/nistec"
33 "crypto/internal/randutil"
34 "crypto/sha512"
35 "crypto/subtle"
36 "errors"
37 "io"
38 "math/big"
39 "sync"
40
41 "golang.org/x/crypto/cryptobyte"
42 "golang.org/x/crypto/cryptobyte/asn1"
43 )
44
45
46 type PublicKey struct {
47 elliptic.Curve
48 X, Y *big.Int
49 }
50
51
52
53
54
55
56
57 func (k *PublicKey) ECDH() (*ecdh.PublicKey, error) {
58 c := curveToECDH(k.Curve)
59 if c == nil {
60 return nil, errors.New("ecdsa: unsupported curve by crypto/ecdh")
61 }
62 if !k.Curve.IsOnCurve(k.X, k.Y) {
63 return nil, errors.New("ecdsa: invalid public key")
64 }
65 return c.NewPublicKey(elliptic.Marshal(k.Curve, k.X, k.Y))
66 }
67
68
69
70
71
72
73 func (pub *PublicKey) Equal(x crypto.PublicKey) bool {
74 xx, ok := x.(*PublicKey)
75 if !ok {
76 return false
77 }
78 return bigIntEqual(pub.X, xx.X) && bigIntEqual(pub.Y, xx.Y) &&
79
80
81
82
83 pub.Curve == xx.Curve
84 }
85
86
87 type PrivateKey struct {
88 PublicKey
89 D *big.Int
90 }
91
92
93
94
95 func (k *PrivateKey) ECDH() (*ecdh.PrivateKey, error) {
96 c := curveToECDH(k.Curve)
97 if c == nil {
98 return nil, errors.New("ecdsa: unsupported curve by crypto/ecdh")
99 }
100 size := (k.Curve.Params().N.BitLen() + 7) / 8
101 if k.D.BitLen() > size*8 {
102 return nil, errors.New("ecdsa: invalid private key")
103 }
104 return c.NewPrivateKey(k.D.FillBytes(make([]byte, size)))
105 }
106
107 func curveToECDH(c elliptic.Curve) ecdh.Curve {
108 switch c {
109 case elliptic.P256():
110 return ecdh.P256()
111 case elliptic.P384():
112 return ecdh.P384()
113 case elliptic.P521():
114 return ecdh.P521()
115 default:
116 return nil
117 }
118 }
119
120
121 func (priv *PrivateKey) Public() crypto.PublicKey {
122 return &priv.PublicKey
123 }
124
125
126
127
128 func (priv *PrivateKey) Equal(x crypto.PrivateKey) bool {
129 xx, ok := x.(*PrivateKey)
130 if !ok {
131 return false
132 }
133 return priv.PublicKey.Equal(&xx.PublicKey) && bigIntEqual(priv.D, xx.D)
134 }
135
136
137
138 func bigIntEqual(a, b *big.Int) bool {
139 return subtle.ConstantTimeCompare(a.Bytes(), b.Bytes()) == 1
140 }
141
142
143
144
145
146
147
148
149 func (priv *PrivateKey) Sign(rand io.Reader, digest []byte, opts crypto.SignerOpts) ([]byte, error) {
150 return SignASN1(rand, priv, digest)
151 }
152
153
154
155
156
157
158 func GenerateKey(c elliptic.Curve, rand io.Reader) (*PrivateKey, error) {
159 randutil.MaybeReadByte(rand)
160
161 if boring.Enabled && rand == boring.RandReader {
162 x, y, d, err := boring.GenerateKeyECDSA(c.Params().Name)
163 if err != nil {
164 return nil, err
165 }
166 return &PrivateKey{PublicKey: PublicKey{Curve: c, X: bbig.Dec(x), Y: bbig.Dec(y)}, D: bbig.Dec(d)}, nil
167 }
168 boring.UnreachableExceptTests()
169
170 switch c.Params() {
171 case elliptic.P224().Params():
172 return generateNISTEC(p224(), rand)
173 case elliptic.P256().Params():
174 return generateNISTEC(p256(), rand)
175 case elliptic.P384().Params():
176 return generateNISTEC(p384(), rand)
177 case elliptic.P521().Params():
178 return generateNISTEC(p521(), rand)
179 default:
180 return generateLegacy(c, rand)
181 }
182 }
183
184 func generateNISTEC[Point nistPoint[Point]](c *nistCurve[Point], rand io.Reader) (*PrivateKey, error) {
185 k, Q, err := randomPoint(c, rand)
186 if err != nil {
187 return nil, err
188 }
189
190 priv := new(PrivateKey)
191 priv.PublicKey.Curve = c.curve
192 priv.D = new(big.Int).SetBytes(k.Bytes(c.N))
193 priv.PublicKey.X, priv.PublicKey.Y, err = c.pointToAffine(Q)
194 if err != nil {
195 return nil, err
196 }
197 return priv, nil
198 }
199
200
201
202 func randomPoint[Point nistPoint[Point]](c *nistCurve[Point], rand io.Reader) (k *bigmod.Nat, p Point, err error) {
203 k = bigmod.NewNat()
204 for {
205 b := make([]byte, c.N.Size())
206 if _, err = io.ReadFull(rand, b); err != nil {
207 return
208 }
209
210
211
212
213
214 if excess := len(b)*8 - c.N.BitLen(); excess > 0 {
215
216
217 if excess != 0 && c.curve.Params().Name != "P-521" {
218 panic("ecdsa: internal error: unexpectedly masking off bits")
219 }
220 b[0] >>= excess
221 }
222
223
224
225
226
227 if _, err = k.SetBytes(b, c.N); err == nil && k.IsZero() == 0 {
228 break
229 }
230
231 if testingOnlyRejectionSamplingLooped != nil {
232 testingOnlyRejectionSamplingLooped()
233 }
234 }
235
236 p, err = c.newPoint().ScalarBaseMult(k.Bytes(c.N))
237 return
238 }
239
240
241
242 var testingOnlyRejectionSamplingLooped func()
243
244
245
246 var errNoAsm = errors.New("no assembly implementation available")
247
248
249
250
251
252
253
254
255
256 func SignASN1(rand io.Reader, priv *PrivateKey, hash []byte) ([]byte, error) {
257 randutil.MaybeReadByte(rand)
258
259 if boring.Enabled && rand == boring.RandReader {
260 b, err := boringPrivateKey(priv)
261 if err != nil {
262 return nil, err
263 }
264 return boring.SignMarshalECDSA(b, hash)
265 }
266 boring.UnreachableExceptTests()
267
268 csprng, err := mixedCSPRNG(rand, priv, hash)
269 if err != nil {
270 return nil, err
271 }
272
273 if sig, err := signAsm(priv, csprng, hash); err != errNoAsm {
274 return sig, err
275 }
276
277 switch priv.Curve.Params() {
278 case elliptic.P224().Params():
279 return signNISTEC(p224(), priv, csprng, hash)
280 case elliptic.P256().Params():
281 return signNISTEC(p256(), priv, csprng, hash)
282 case elliptic.P384().Params():
283 return signNISTEC(p384(), priv, csprng, hash)
284 case elliptic.P521().Params():
285 return signNISTEC(p521(), priv, csprng, hash)
286 default:
287 return signLegacy(priv, csprng, hash)
288 }
289 }
290
291 func signNISTEC[Point nistPoint[Point]](c *nistCurve[Point], priv *PrivateKey, csprng io.Reader, hash []byte) (sig []byte, err error) {
292
293
294 k, R, err := randomPoint(c, csprng)
295 if err != nil {
296 return nil, err
297 }
298
299
300 kInv := bigmod.NewNat()
301 inverse(c, kInv, k)
302
303 Rx, err := R.BytesX()
304 if err != nil {
305 return nil, err
306 }
307 r, err := bigmod.NewNat().SetOverflowingBytes(Rx, c.N)
308 if err != nil {
309 return nil, err
310 }
311
312
313
314
315 if r.IsZero() == 1 {
316 return nil, errors.New("ecdsa: internal error: r is zero")
317 }
318
319 e := bigmod.NewNat()
320 hashToNat(c, e, hash)
321
322 s, err := bigmod.NewNat().SetBytes(priv.D.Bytes(), c.N)
323 if err != nil {
324 return nil, err
325 }
326 s.Mul(r, c.N)
327 s.Add(e, c.N)
328 s.Mul(kInv, c.N)
329
330
331 if s.IsZero() == 1 {
332 return nil, errors.New("ecdsa: internal error: s is zero")
333 }
334
335 return encodeSignature(r.Bytes(c.N), s.Bytes(c.N))
336 }
337
338 func encodeSignature(r, s []byte) ([]byte, error) {
339 var b cryptobyte.Builder
340 b.AddASN1(asn1.SEQUENCE, func(b *cryptobyte.Builder) {
341 addASN1IntBytes(b, r)
342 addASN1IntBytes(b, s)
343 })
344 return b.Bytes()
345 }
346
347
348
349 func addASN1IntBytes(b *cryptobyte.Builder, bytes []byte) {
350 for len(bytes) > 0 && bytes[0] == 0 {
351 bytes = bytes[1:]
352 }
353 if len(bytes) == 0 {
354 b.SetError(errors.New("invalid integer"))
355 return
356 }
357 b.AddASN1(asn1.INTEGER, func(c *cryptobyte.Builder) {
358 if bytes[0]&0x80 != 0 {
359 c.AddUint8(0)
360 }
361 c.AddBytes(bytes)
362 })
363 }
364
365
366 func inverse[Point nistPoint[Point]](c *nistCurve[Point], kInv, k *bigmod.Nat) {
367 if c.curve.Params().Name == "P-256" {
368 kBytes, err := nistec.P256OrdInverse(k.Bytes(c.N))
369
370 if err == nil {
371 _, err := kInv.SetBytes(kBytes, c.N)
372 if err != nil {
373 panic("ecdsa: internal error: P256OrdInverse produced an invalid value")
374 }
375 return
376 }
377 }
378
379
380
381 kInv.Exp(k, c.nMinus2, c.N)
382 }
383
384
385
386 func hashToNat[Point nistPoint[Point]](c *nistCurve[Point], e *bigmod.Nat, hash []byte) {
387
388
389
390
391 if size := c.N.Size(); len(hash) >= size {
392 hash = hash[:size]
393 if excess := len(hash)*8 - c.N.BitLen(); excess > 0 {
394 hash = bytes.Clone(hash)
395 for i := len(hash) - 1; i >= 0; i-- {
396 hash[i] >>= excess
397 if i > 0 {
398 hash[i] |= hash[i-1] << (8 - excess)
399 }
400 }
401 }
402 }
403 _, err := e.SetOverflowingBytes(hash, c.N)
404 if err != nil {
405 panic("ecdsa: internal error: truncated hash is too long")
406 }
407 }
408
409
410
411
412
413 func mixedCSPRNG(rand io.Reader, priv *PrivateKey, hash []byte) (io.Reader, error) {
414
415
416
417
418
419
420
421
422
423
424
425
426 entropy := make([]byte, 32)
427 if _, err := io.ReadFull(rand, entropy); err != nil {
428 return nil, err
429 }
430
431
432 md := sha512.New()
433 md.Write(priv.D.Bytes())
434 md.Write(entropy)
435 md.Write(hash)
436 key := md.Sum(nil)[:32]
437
438
439
440 block, err := aes.NewCipher(key)
441 if err != nil {
442 return nil, err
443 }
444
445
446
447 const aesIV = "IV for ECDSA CTR"
448 return &cipher.StreamReader{
449 R: zeroReader,
450 S: cipher.NewCTR(block, []byte(aesIV)),
451 }, nil
452 }
453
454 type zr struct{}
455
456 var zeroReader = zr{}
457
458
459 func (zr) Read(dst []byte) (n int, err error) {
460 clear(dst)
461 return len(dst), nil
462 }
463
464
465
466 func VerifyASN1(pub *PublicKey, hash, sig []byte) bool {
467 if boring.Enabled {
468 key, err := boringPublicKey(pub)
469 if err != nil {
470 return false
471 }
472 return boring.VerifyECDSA(key, hash, sig)
473 }
474 boring.UnreachableExceptTests()
475
476 if err := verifyAsm(pub, hash, sig); err != errNoAsm {
477 return err == nil
478 }
479
480 switch pub.Curve.Params() {
481 case elliptic.P224().Params():
482 return verifyNISTEC(p224(), pub, hash, sig)
483 case elliptic.P256().Params():
484 return verifyNISTEC(p256(), pub, hash, sig)
485 case elliptic.P384().Params():
486 return verifyNISTEC(p384(), pub, hash, sig)
487 case elliptic.P521().Params():
488 return verifyNISTEC(p521(), pub, hash, sig)
489 default:
490 return verifyLegacy(pub, hash, sig)
491 }
492 }
493
494 func verifyNISTEC[Point nistPoint[Point]](c *nistCurve[Point], pub *PublicKey, hash, sig []byte) bool {
495 rBytes, sBytes, err := parseSignature(sig)
496 if err != nil {
497 return false
498 }
499
500 Q, err := c.pointFromAffine(pub.X, pub.Y)
501 if err != nil {
502 return false
503 }
504
505
506
507 r, err := bigmod.NewNat().SetBytes(rBytes, c.N)
508 if err != nil || r.IsZero() == 1 {
509 return false
510 }
511 s, err := bigmod.NewNat().SetBytes(sBytes, c.N)
512 if err != nil || s.IsZero() == 1 {
513 return false
514 }
515
516 e := bigmod.NewNat()
517 hashToNat(c, e, hash)
518
519
520 w := bigmod.NewNat()
521 inverse(c, w, s)
522
523
524 p1, err := c.newPoint().ScalarBaseMult(e.Mul(w, c.N).Bytes(c.N))
525 if err != nil {
526 return false
527 }
528
529 p2, err := Q.ScalarMult(Q, w.Mul(r, c.N).Bytes(c.N))
530 if err != nil {
531 return false
532 }
533
534 Rx, err := p1.Add(p1, p2).BytesX()
535 if err != nil {
536 return false
537 }
538
539 v, err := bigmod.NewNat().SetOverflowingBytes(Rx, c.N)
540 if err != nil {
541 return false
542 }
543
544 return v.Equal(r) == 1
545 }
546
547 func parseSignature(sig []byte) (r, s []byte, err error) {
548 var inner cryptobyte.String
549 input := cryptobyte.String(sig)
550 if !input.ReadASN1(&inner, asn1.SEQUENCE) ||
551 !input.Empty() ||
552 !inner.ReadASN1Integer(&r) ||
553 !inner.ReadASN1Integer(&s) ||
554 !inner.Empty() {
555 return nil, nil, errors.New("invalid ASN.1")
556 }
557 return r, s, nil
558 }
559
560 type nistCurve[Point nistPoint[Point]] struct {
561 newPoint func() Point
562 curve elliptic.Curve
563 N *bigmod.Modulus
564 nMinus2 []byte
565 }
566
567
568 type nistPoint[T any] interface {
569 Bytes() []byte
570 BytesX() ([]byte, error)
571 SetBytes([]byte) (T, error)
572 Add(T, T) T
573 ScalarMult(T, []byte) (T, error)
574 ScalarBaseMult([]byte) (T, error)
575 }
576
577
578 func (curve *nistCurve[Point]) pointFromAffine(x, y *big.Int) (p Point, err error) {
579 bitSize := curve.curve.Params().BitSize
580
581 if x.Sign() < 0 || y.Sign() < 0 {
582 return p, errors.New("negative coordinate")
583 }
584 if x.BitLen() > bitSize || y.BitLen() > bitSize {
585 return p, errors.New("overflowing coordinate")
586 }
587
588 byteLen := (bitSize + 7) / 8
589 buf := make([]byte, 1+2*byteLen)
590 buf[0] = 4
591 x.FillBytes(buf[1 : 1+byteLen])
592 y.FillBytes(buf[1+byteLen : 1+2*byteLen])
593 return curve.newPoint().SetBytes(buf)
594 }
595
596
597 func (curve *nistCurve[Point]) pointToAffine(p Point) (x, y *big.Int, err error) {
598 out := p.Bytes()
599 if len(out) == 1 && out[0] == 0 {
600
601 return nil, nil, errors.New("ecdsa: public key point is the infinity")
602 }
603 byteLen := (curve.curve.Params().BitSize + 7) / 8
604 x = new(big.Int).SetBytes(out[1 : 1+byteLen])
605 y = new(big.Int).SetBytes(out[1+byteLen:])
606 return x, y, nil
607 }
608
609 var p224Once sync.Once
610 var _p224 *nistCurve[*nistec.P224Point]
611
612 func p224() *nistCurve[*nistec.P224Point] {
613 p224Once.Do(func() {
614 _p224 = &nistCurve[*nistec.P224Point]{
615 newPoint: func() *nistec.P224Point { return nistec.NewP224Point() },
616 }
617 precomputeParams(_p224, elliptic.P224())
618 })
619 return _p224
620 }
621
622 var p256Once sync.Once
623 var _p256 *nistCurve[*nistec.P256Point]
624
625 func p256() *nistCurve[*nistec.P256Point] {
626 p256Once.Do(func() {
627 _p256 = &nistCurve[*nistec.P256Point]{
628 newPoint: func() *nistec.P256Point { return nistec.NewP256Point() },
629 }
630 precomputeParams(_p256, elliptic.P256())
631 })
632 return _p256
633 }
634
635 var p384Once sync.Once
636 var _p384 *nistCurve[*nistec.P384Point]
637
638 func p384() *nistCurve[*nistec.P384Point] {
639 p384Once.Do(func() {
640 _p384 = &nistCurve[*nistec.P384Point]{
641 newPoint: func() *nistec.P384Point { return nistec.NewP384Point() },
642 }
643 precomputeParams(_p384, elliptic.P384())
644 })
645 return _p384
646 }
647
648 var p521Once sync.Once
649 var _p521 *nistCurve[*nistec.P521Point]
650
651 func p521() *nistCurve[*nistec.P521Point] {
652 p521Once.Do(func() {
653 _p521 = &nistCurve[*nistec.P521Point]{
654 newPoint: func() *nistec.P521Point { return nistec.NewP521Point() },
655 }
656 precomputeParams(_p521, elliptic.P521())
657 })
658 return _p521
659 }
660
661 func precomputeParams[Point nistPoint[Point]](c *nistCurve[Point], curve elliptic.Curve) {
662 params := curve.Params()
663 c.curve = curve
664 var err error
665 c.N, err = bigmod.NewModulusFromBig(params.N)
666 if err != nil {
667 panic(err)
668 }
669 c.nMinus2 = new(big.Int).Sub(params.N, big.NewInt(2)).Bytes()
670 }
671
View as plain text