1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 package rsa
24
25 import (
26 "crypto"
27 "crypto/internal/boring"
28 "crypto/internal/boring/bbig"
29 "crypto/internal/randutil"
30 "crypto/rand"
31 "crypto/subtle"
32 "errors"
33 "hash"
34 "io"
35 "math"
36 "math/big"
37 )
38
39 var bigZero = big.NewInt(0)
40 var bigOne = big.NewInt(1)
41
42
43 type PublicKey struct {
44 N *big.Int
45 E int
46 }
47
48
49
50
51
52
53 func (pub *PublicKey) Size() int {
54 return (pub.N.BitLen() + 7) / 8
55 }
56
57
58 func (pub *PublicKey) Equal(x crypto.PublicKey) bool {
59 xx, ok := x.(*PublicKey)
60 if !ok {
61 return false
62 }
63 return pub.N.Cmp(xx.N) == 0 && pub.E == xx.E
64 }
65
66
67
68 type OAEPOptions struct {
69
70 Hash crypto.Hash
71
72
73 Label []byte
74 }
75
76 var (
77 errPublicModulus = errors.New("crypto/rsa: missing public modulus")
78 errPublicExponentSmall = errors.New("crypto/rsa: public exponent too small")
79 errPublicExponentLarge = errors.New("crypto/rsa: public exponent too large")
80 )
81
82
83
84
85
86
87 func checkPub(pub *PublicKey) error {
88 if pub.N == nil {
89 return errPublicModulus
90 }
91 if pub.E < 2 {
92 return errPublicExponentSmall
93 }
94 if pub.E > 1<<31-1 {
95 return errPublicExponentLarge
96 }
97 return nil
98 }
99
100
101 type PrivateKey struct {
102 PublicKey
103 D *big.Int
104 Primes []*big.Int
105
106
107
108 Precomputed PrecomputedValues
109 }
110
111
112 func (priv *PrivateKey) Public() crypto.PublicKey {
113 return &priv.PublicKey
114 }
115
116
117
118 func (priv *PrivateKey) Equal(x crypto.PrivateKey) bool {
119 xx, ok := x.(*PrivateKey)
120 if !ok {
121 return false
122 }
123 if !priv.PublicKey.Equal(&xx.PublicKey) || priv.D.Cmp(xx.D) != 0 {
124 return false
125 }
126 if len(priv.Primes) != len(xx.Primes) {
127 return false
128 }
129 for i := range priv.Primes {
130 if priv.Primes[i].Cmp(xx.Primes[i]) != 0 {
131 return false
132 }
133 }
134 return true
135 }
136
137
138
139
140
141
142
143
144
145 func (priv *PrivateKey) Sign(rand io.Reader, digest []byte, opts crypto.SignerOpts) ([]byte, error) {
146 if pssOpts, ok := opts.(*PSSOptions); ok {
147 return SignPSS(rand, priv, pssOpts.Hash, digest, pssOpts)
148 }
149
150 return SignPKCS1v15(rand, priv, opts.HashFunc(), digest)
151 }
152
153
154
155
156 func (priv *PrivateKey) Decrypt(rand io.Reader, ciphertext []byte, opts crypto.DecrypterOpts) (plaintext []byte, err error) {
157 if opts == nil {
158 return DecryptPKCS1v15(rand, priv, ciphertext)
159 }
160
161 switch opts := opts.(type) {
162 case *OAEPOptions:
163 return DecryptOAEP(opts.Hash.New(), rand, priv, ciphertext, opts.Label)
164
165 case *PKCS1v15DecryptOptions:
166 if l := opts.SessionKeyLen; l > 0 {
167 plaintext = make([]byte, l)
168 if _, err := io.ReadFull(rand, plaintext); err != nil {
169 return nil, err
170 }
171 if err := DecryptPKCS1v15SessionKey(rand, priv, ciphertext, plaintext); err != nil {
172 return nil, err
173 }
174 return plaintext, nil
175 } else {
176 return DecryptPKCS1v15(rand, priv, ciphertext)
177 }
178
179 default:
180 return nil, errors.New("crypto/rsa: invalid options for Decrypt")
181 }
182 }
183
184 type PrecomputedValues struct {
185 Dp, Dq *big.Int
186 Qinv *big.Int
187
188
189
190
191
192 CRTValues []CRTValue
193 }
194
195
196 type CRTValue struct {
197 Exp *big.Int
198 Coeff *big.Int
199 R *big.Int
200 }
201
202
203
204 func (priv *PrivateKey) Validate() error {
205 if err := checkPub(&priv.PublicKey); err != nil {
206 return err
207 }
208
209
210 modulus := new(big.Int).Set(bigOne)
211 for _, prime := range priv.Primes {
212
213 if prime.Cmp(bigOne) <= 0 {
214 return errors.New("crypto/rsa: invalid prime value")
215 }
216 modulus.Mul(modulus, prime)
217 }
218 if modulus.Cmp(priv.N) != 0 {
219 return errors.New("crypto/rsa: invalid modulus")
220 }
221
222
223
224
225
226
227 congruence := new(big.Int)
228 de := new(big.Int).SetInt64(int64(priv.E))
229 de.Mul(de, priv.D)
230 for _, prime := range priv.Primes {
231 pminus1 := new(big.Int).Sub(prime, bigOne)
232 congruence.Mod(de, pminus1)
233 if congruence.Cmp(bigOne) != 0 {
234 return errors.New("crypto/rsa: invalid exponents")
235 }
236 }
237 return nil
238 }
239
240
241
242 func GenerateKey(random io.Reader, bits int) (*PrivateKey, error) {
243 return GenerateMultiPrimeKey(random, 2, bits)
244 }
245
246
247
248
249
250
251
252
253
254
255
256
257 func GenerateMultiPrimeKey(random io.Reader, nprimes int, bits int) (*PrivateKey, error) {
258 randutil.MaybeReadByte(random)
259
260 if boring.Enabled && random == boring.RandReader && nprimes == 2 && (bits == 2048 || bits == 3072) {
261 bN, bE, bD, bP, bQ, bDp, bDq, bQinv, err := boring.GenerateKeyRSA(bits)
262 if err != nil {
263 return nil, err
264 }
265 N := bbig.Dec(bN)
266 E := bbig.Dec(bE)
267 D := bbig.Dec(bD)
268 P := bbig.Dec(bP)
269 Q := bbig.Dec(bQ)
270 Dp := bbig.Dec(bDp)
271 Dq := bbig.Dec(bDq)
272 Qinv := bbig.Dec(bQinv)
273 e64 := E.Int64()
274 if !E.IsInt64() || int64(int(e64)) != e64 {
275 return nil, errors.New("crypto/rsa: generated key exponent too large")
276 }
277 key := &PrivateKey{
278 PublicKey: PublicKey{
279 N: N,
280 E: int(e64),
281 },
282 D: D,
283 Primes: []*big.Int{P, Q},
284 Precomputed: PrecomputedValues{
285 Dp: Dp,
286 Dq: Dq,
287 Qinv: Qinv,
288 CRTValues: make([]CRTValue, 0),
289 },
290 }
291 return key, nil
292 }
293
294 priv := new(PrivateKey)
295 priv.E = 65537
296
297 if nprimes < 2 {
298 return nil, errors.New("crypto/rsa: GenerateMultiPrimeKey: nprimes must be >= 2")
299 }
300
301 if bits < 64 {
302 primeLimit := float64(uint64(1) << uint(bits/nprimes))
303
304 pi := primeLimit / (math.Log(primeLimit) - 1)
305
306
307 pi /= 4
308
309
310 pi /= 2
311 if pi <= float64(nprimes) {
312 return nil, errors.New("crypto/rsa: too few primes of given length to generate an RSA key")
313 }
314 }
315
316 primes := make([]*big.Int, nprimes)
317
318 NextSetOfPrimes:
319 for {
320 todo := bits
321
322
323
324
325
326
327
328
329
330
331
332 if nprimes >= 7 {
333 todo += (nprimes - 2) / 5
334 }
335 for i := 0; i < nprimes; i++ {
336 var err error
337 primes[i], err = rand.Prime(random, todo/(nprimes-i))
338 if err != nil {
339 return nil, err
340 }
341 todo -= primes[i].BitLen()
342 }
343
344
345 for i, prime := range primes {
346 for j := 0; j < i; j++ {
347 if prime.Cmp(primes[j]) == 0 {
348 continue NextSetOfPrimes
349 }
350 }
351 }
352
353 n := new(big.Int).Set(bigOne)
354 totient := new(big.Int).Set(bigOne)
355 pminus1 := new(big.Int)
356 for _, prime := range primes {
357 n.Mul(n, prime)
358 pminus1.Sub(prime, bigOne)
359 totient.Mul(totient, pminus1)
360 }
361 if n.BitLen() != bits {
362
363
364
365 continue NextSetOfPrimes
366 }
367
368 priv.D = new(big.Int)
369 e := big.NewInt(int64(priv.E))
370 ok := priv.D.ModInverse(e, totient)
371
372 if ok != nil {
373 priv.Primes = primes
374 priv.N = n
375 break
376 }
377 }
378
379 priv.Precompute()
380 return priv, nil
381 }
382
383
384 func incCounter(c *[4]byte) {
385 if c[3]++; c[3] != 0 {
386 return
387 }
388 if c[2]++; c[2] != 0 {
389 return
390 }
391 if c[1]++; c[1] != 0 {
392 return
393 }
394 c[0]++
395 }
396
397
398
399 func mgf1XOR(out []byte, hash hash.Hash, seed []byte) {
400 var counter [4]byte
401 var digest []byte
402
403 done := 0
404 for done < len(out) {
405 hash.Write(seed)
406 hash.Write(counter[0:4])
407 digest = hash.Sum(digest[:0])
408 hash.Reset()
409
410 for i := 0; i < len(digest) && done < len(out); i++ {
411 out[done] ^= digest[i]
412 done++
413 }
414 incCounter(&counter)
415 }
416 }
417
418
419
420 var ErrMessageTooLong = errors.New("crypto/rsa: message too long for RSA public key size")
421
422 func encrypt(c *big.Int, pub *PublicKey, m *big.Int) *big.Int {
423 boring.Unreachable()
424 e := big.NewInt(int64(pub.E))
425 c.Exp(m, e, pub.N)
426 return c
427 }
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446 func EncryptOAEP(hash hash.Hash, random io.Reader, pub *PublicKey, msg []byte, label []byte) ([]byte, error) {
447 if err := checkPub(pub); err != nil {
448 return nil, err
449 }
450 hash.Reset()
451 k := pub.Size()
452 if len(msg) > k-2*hash.Size()-2 {
453 return nil, ErrMessageTooLong
454 }
455
456 if boring.Enabled && random == boring.RandReader {
457 bkey, err := boringPublicKey(pub)
458 if err != nil {
459 return nil, err
460 }
461 return boring.EncryptRSAOAEP(hash, bkey, msg, label)
462 }
463 boring.UnreachableExceptTests()
464
465 hash.Write(label)
466 lHash := hash.Sum(nil)
467 hash.Reset()
468
469 em := make([]byte, k)
470 seed := em[1 : 1+hash.Size()]
471 db := em[1+hash.Size():]
472
473 copy(db[0:hash.Size()], lHash)
474 db[len(db)-len(msg)-1] = 1
475 copy(db[len(db)-len(msg):], msg)
476
477 _, err := io.ReadFull(random, seed)
478 if err != nil {
479 return nil, err
480 }
481
482 mgf1XOR(db, hash, seed)
483 mgf1XOR(seed, hash, db)
484
485 if boring.Enabled {
486 var bkey *boring.PublicKeyRSA
487 bkey, err = boringPublicKey(pub)
488 if err != nil {
489 return nil, err
490 }
491 return boring.EncryptRSANoPadding(bkey, em)
492 }
493
494 m := new(big.Int)
495 m.SetBytes(em)
496 c := encrypt(new(big.Int), pub, m)
497
498 out := make([]byte, k)
499 return c.FillBytes(out), nil
500 }
501
502
503
504 var ErrDecryption = errors.New("crypto/rsa: decryption error")
505
506
507
508 var ErrVerification = errors.New("crypto/rsa: verification error")
509
510
511
512 func (priv *PrivateKey) Precompute() {
513 if priv.Precomputed.Dp != nil {
514 return
515 }
516
517 priv.Precomputed.Dp = new(big.Int).Sub(priv.Primes[0], bigOne)
518 priv.Precomputed.Dp.Mod(priv.D, priv.Precomputed.Dp)
519
520 priv.Precomputed.Dq = new(big.Int).Sub(priv.Primes[1], bigOne)
521 priv.Precomputed.Dq.Mod(priv.D, priv.Precomputed.Dq)
522
523 priv.Precomputed.Qinv = new(big.Int).ModInverse(priv.Primes[1], priv.Primes[0])
524
525 r := new(big.Int).Mul(priv.Primes[0], priv.Primes[1])
526 priv.Precomputed.CRTValues = make([]CRTValue, len(priv.Primes)-2)
527 for i := 2; i < len(priv.Primes); i++ {
528 prime := priv.Primes[i]
529 values := &priv.Precomputed.CRTValues[i-2]
530
531 values.Exp = new(big.Int).Sub(prime, bigOne)
532 values.Exp.Mod(priv.D, values.Exp)
533
534 values.R = new(big.Int).Set(r)
535 values.Coeff = new(big.Int).ModInverse(r, prime)
536
537 r.Mul(r, prime)
538 }
539 }
540
541
542
543 func decrypt(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err error) {
544 if len(priv.Primes) <= 2 {
545 boring.Unreachable()
546 }
547
548 if c.Cmp(priv.N) > 0 {
549 err = ErrDecryption
550 return
551 }
552 if priv.N.Sign() == 0 {
553 return nil, ErrDecryption
554 }
555
556 var ir *big.Int
557 if random != nil {
558 randutil.MaybeReadByte(random)
559
560
561
562
563
564
565 var r *big.Int
566 ir = new(big.Int)
567 for {
568 r, err = rand.Int(random, priv.N)
569 if err != nil {
570 return
571 }
572 if r.Cmp(bigZero) == 0 {
573 r = bigOne
574 }
575 ok := ir.ModInverse(r, priv.N)
576 if ok != nil {
577 break
578 }
579 }
580 bigE := big.NewInt(int64(priv.E))
581 rpowe := new(big.Int).Exp(r, bigE, priv.N)
582 cCopy := new(big.Int).Set(c)
583 cCopy.Mul(cCopy, rpowe)
584 cCopy.Mod(cCopy, priv.N)
585 c = cCopy
586 }
587
588 if priv.Precomputed.Dp == nil {
589 m = new(big.Int).Exp(c, priv.D, priv.N)
590 } else {
591
592 m = new(big.Int).Exp(c, priv.Precomputed.Dp, priv.Primes[0])
593 m2 := new(big.Int).Exp(c, priv.Precomputed.Dq, priv.Primes[1])
594 m.Sub(m, m2)
595 if m.Sign() < 0 {
596 m.Add(m, priv.Primes[0])
597 }
598 m.Mul(m, priv.Precomputed.Qinv)
599 m.Mod(m, priv.Primes[0])
600 m.Mul(m, priv.Primes[1])
601 m.Add(m, m2)
602
603 for i, values := range priv.Precomputed.CRTValues {
604 prime := priv.Primes[2+i]
605 m2.Exp(c, values.Exp, prime)
606 m2.Sub(m2, m)
607 m2.Mul(m2, values.Coeff)
608 m2.Mod(m2, prime)
609 if m2.Sign() < 0 {
610 m2.Add(m2, prime)
611 }
612 m2.Mul(m2, values.R)
613 m.Add(m, m2)
614 }
615 }
616
617 if ir != nil {
618
619 m.Mul(m, ir)
620 m.Mod(m, priv.N)
621 }
622
623 return
624 }
625
626 func decryptAndCheck(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err error) {
627 m, err = decrypt(random, priv, c)
628 if err != nil {
629 return nil, err
630 }
631
632
633
634 check := encrypt(new(big.Int), &priv.PublicKey, m)
635 if c.Cmp(check) != 0 {
636 return nil, errors.New("rsa: internal error")
637 }
638 return m, nil
639 }
640
641
642
643
644
645
646
647
648
649
650
651
652
653 func DecryptOAEP(hash hash.Hash, random io.Reader, priv *PrivateKey, ciphertext []byte, label []byte) ([]byte, error) {
654 if err := checkPub(&priv.PublicKey); err != nil {
655 return nil, err
656 }
657 k := priv.Size()
658 if len(ciphertext) > k ||
659 k < hash.Size()*2+2 {
660 return nil, ErrDecryption
661 }
662
663 if boring.Enabled {
664 bkey, err := boringPrivateKey(priv)
665 if err != nil {
666 return nil, err
667 }
668 out, err := boring.DecryptRSAOAEP(hash, bkey, ciphertext, label)
669 if err != nil {
670 return nil, ErrDecryption
671 }
672 return out, nil
673 }
674 c := new(big.Int).SetBytes(ciphertext)
675
676 m, err := decrypt(random, priv, c)
677 if err != nil {
678 return nil, err
679 }
680
681 hash.Write(label)
682 lHash := hash.Sum(nil)
683 hash.Reset()
684
685
686
687 em := m.FillBytes(make([]byte, k))
688
689 firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0)
690
691 seed := em[1 : hash.Size()+1]
692 db := em[hash.Size()+1:]
693
694 mgf1XOR(seed, hash, db)
695 mgf1XOR(db, hash, seed)
696
697 lHash2 := db[0:hash.Size()]
698
699
700
701
702
703 lHash2Good := subtle.ConstantTimeCompare(lHash, lHash2)
704
705
706
707
708
709
710 var lookingForIndex, index, invalid int
711 lookingForIndex = 1
712 rest := db[hash.Size():]
713
714 for i := 0; i < len(rest); i++ {
715 equals0 := subtle.ConstantTimeByteEq(rest[i], 0)
716 equals1 := subtle.ConstantTimeByteEq(rest[i], 1)
717 index = subtle.ConstantTimeSelect(lookingForIndex&equals1, i, index)
718 lookingForIndex = subtle.ConstantTimeSelect(equals1, 0, lookingForIndex)
719 invalid = subtle.ConstantTimeSelect(lookingForIndex&^equals0, 1, invalid)
720 }
721
722 if firstByteIsZero&lHash2Good&^invalid&^lookingForIndex != 1 {
723 return nil, ErrDecryption
724 }
725
726 return rest[index+1:], nil
727 }
728
View as plain text