1 // Copyright 2009 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 rsa implements RSA encryption as specified in PKCS #1 and RFC 8017.
6 //
7 // RSA is a single, fundamental operation that is used in this package to
8 // implement either public-key encryption or public-key signatures.
9 //
10 // The original specification for encryption and signatures with RSA is PKCS #1
11 // and the terms "RSA encryption" and "RSA signatures" by default refer to
12 // PKCS #1 version 1.5. However, that specification has flaws and new designs
13 // should use version 2, usually called by just OAEP and PSS, where
14 // possible.
15 //
16 // Two sets of interfaces are included in this package. When a more abstract
17 // interface isn't necessary, there are functions for encrypting/decrypting
18 // with v1.5/OAEP and signing/verifying with v1.5/PSS. If one needs to abstract
19 // over the public key primitive, the PrivateKey type implements the
20 // Decrypter and Signer interfaces from the crypto package.
21 //
22 // Operations involving private keys are implemented using constant-time
23 // algorithms, except for [GenerateKey] and for some operations involving
24 // deprecated multi-prime keys.
25 //
26 // # Minimum key size
27 //
28 // [GenerateKey] returns an error if a key of less than 1024 bits is requested,
29 // and all Sign, Verify, Encrypt, and Decrypt methods return an error if used
30 // with a key smaller than 1024 bits. Such keys are insecure and should not be
31 // used.
32 //
33 // The rsa1024min=0 GODEBUG setting suppresses this error, but we recommend
34 // doing so only in tests, if necessary. Tests can set this option using
35 // [testing.T.Setenv] or by including "//go:debug rsa1024min=0" in a *_test.go
36 // source file.
37 //
38 // Alternatively, see the [GenerateKey (TestKey)] example for a pregenerated
39 // test-only 2048-bit key.
40 //
41 // [GenerateKey (TestKey)]: https://pkg.go.dev/crypto/rsa#example-GenerateKey-TestKey
42 package rsa
43 44 import (
45 "crypto"
46 "crypto/internal/boring"
47 "crypto/internal/boring/bbig"
48 "crypto/internal/fips140/bigmod"
49 "crypto/internal/fips140/rsa"
50 "crypto/internal/fips140only"
51 "crypto/internal/randutil"
52 "crypto/rand"
53 "crypto/subtle"
54 "errors"
55 "fmt"
56 "internal/godebug"
57 "io"
58 "math"
59 "math/big"
60 )
61 62 var bigOne = big.NewInt(1)
63 64 // A PublicKey represents the public part of an RSA key.
65 //
66 // The values of N and E are not considered confidential, and may leak through
67 // side channels, or could be mathematically derived from other public values.
68 type PublicKey struct {
69 N *big.Int // modulus
70 E int // public exponent
71 }
72 73 // Any methods implemented on PublicKey might need to also be implemented on
74 // PrivateKey, as the latter embeds the former and will expose its methods.
75 76 // Size returns the modulus size in bytes. Raw signatures and ciphertexts
77 // for or by this public key will have the same size.
78 func (pub *PublicKey) Size() int {
79 return (pub.N.BitLen() + 7) / 8
80 }
81 82 // Equal reports whether pub and x have the same value.
83 func (pub *PublicKey) Equal(x crypto.PublicKey) bool {
84 xx, ok := x.(*PublicKey)
85 if !ok {
86 return false
87 }
88 return bigIntEqual(pub.N, xx.N) && pub.E == xx.E
89 }
90 91 // OAEPOptions is an interface for passing options to OAEP decryption using the
92 // crypto.Decrypter interface.
93 type OAEPOptions struct {
94 // Hash is the hash function that will be used when generating the mask.
95 Hash crypto.Hash
96 97 // MGFHash is the hash function used for MGF1.
98 // If zero, Hash is used instead.
99 MGFHash crypto.Hash
100 101 // Label is an arbitrary byte string that must be equal to the value
102 // used when encrypting.
103 Label []byte
104 }
105 106 // A PrivateKey represents an RSA key
107 type PrivateKey struct {
108 PublicKey // public part.
109 D *big.Int // private exponent
110 Primes []*big.Int // prime factors of N, has >= 2 elements.
111 112 // Precomputed contains precomputed values that speed up RSA operations,
113 // if available. It must be generated by calling PrivateKey.Precompute and
114 // must not be modified.
115 Precomputed PrecomputedValues
116 }
117 118 // Public returns the public key corresponding to priv.
119 func (priv *PrivateKey) Public() crypto.PublicKey {
120 return &priv.PublicKey
121 }
122 123 // Equal reports whether priv and x have equivalent values. It ignores
124 // Precomputed values.
125 func (priv *PrivateKey) Equal(x crypto.PrivateKey) bool {
126 xx, ok := x.(*PrivateKey)
127 if !ok {
128 return false
129 }
130 if !priv.PublicKey.Equal(&xx.PublicKey) || !bigIntEqual(priv.D, xx.D) {
131 return false
132 }
133 if len(priv.Primes) != len(xx.Primes) {
134 return false
135 }
136 for i := range priv.Primes {
137 if !bigIntEqual(priv.Primes[i], xx.Primes[i]) {
138 return false
139 }
140 }
141 return true
142 }
143 144 // bigIntEqual reports whether a and b are equal leaking only their bit length
145 // through timing side-channels.
146 func bigIntEqual(a, b *big.Int) bool {
147 return subtle.ConstantTimeCompare(a.Bytes(), b.Bytes()) == 1
148 }
149 150 // Sign signs digest with priv, reading randomness from rand. If opts is a
151 // *[PSSOptions] then the PSS algorithm will be used, otherwise PKCS #1 v1.5 will
152 // be used. digest must be the result of hashing the input message using
153 // opts.HashFunc().
154 //
155 // This method implements [crypto.Signer], which is an interface to support keys
156 // where the private part is kept in, for example, a hardware module. Common
157 // uses should use the Sign* functions in this package directly.
158 func (priv *PrivateKey) Sign(rand io.Reader, digest []byte, opts crypto.SignerOpts) ([]byte, error) {
159 if pssOpts, ok := opts.(*PSSOptions); ok {
160 return SignPSS(rand, priv, pssOpts.Hash, digest, pssOpts)
161 }
162 163 return SignPKCS1v15(rand, priv, opts.HashFunc(), digest)
164 }
165 166 // Decrypt decrypts ciphertext with priv. If opts is nil or of type
167 // *[PKCS1v15DecryptOptions] then PKCS #1 v1.5 decryption is performed. Otherwise
168 // opts must have type *[OAEPOptions] and OAEP decryption is done.
169 func (priv *PrivateKey) Decrypt(rand io.Reader, ciphertext []byte, opts crypto.DecrypterOpts) (plaintext []byte, err error) {
170 if opts == nil {
171 return DecryptPKCS1v15(rand, priv, ciphertext)
172 }
173 174 switch opts := opts.(type) {
175 case *OAEPOptions:
176 if opts.MGFHash == 0 {
177 return decryptOAEP(opts.Hash.New(), opts.Hash.New(), priv, ciphertext, opts.Label)
178 } else {
179 return decryptOAEP(opts.Hash.New(), opts.MGFHash.New(), priv, ciphertext, opts.Label)
180 }
181 182 case *PKCS1v15DecryptOptions:
183 if l := opts.SessionKeyLen; l > 0 {
184 plaintext = []byte{:l}
185 if _, err := io.ReadFull(rand, plaintext); err != nil {
186 return nil, err
187 }
188 if err := DecryptPKCS1v15SessionKey(rand, priv, ciphertext, plaintext); err != nil {
189 return nil, err
190 }
191 return plaintext, nil
192 } else {
193 return DecryptPKCS1v15(rand, priv, ciphertext)
194 }
195 196 default:
197 return nil, errors.New("crypto/rsa: invalid options for Decrypt")
198 }
199 }
200 201 type PrecomputedValues struct {
202 Dp, Dq *big.Int // D mod (P-1) (or mod Q-1)
203 Qinv *big.Int // Q^-1 mod P
204 205 // CRTValues is used for the 3rd and subsequent primes. Due to a
206 // historical accident, the CRT for the first two primes is handled
207 // differently in PKCS #1 and interoperability is sufficiently
208 // important that we mirror this.
209 //
210 // Deprecated: These values are still filled in by Precompute for
211 // backwards compatibility but are not used. Multi-prime RSA is very rare,
212 // and is implemented by this package without CRT optimizations to limit
213 // complexity.
214 CRTValues []CRTValue
215 216 fips *rsa.PrivateKey
217 }
218 219 // CRTValue contains the precomputed Chinese remainder theorem values.
220 type CRTValue struct {
221 Exp *big.Int // D mod (prime-1).
222 Coeff *big.Int // R·Coeff ≡ 1 mod Prime.
223 R *big.Int // product of primes prior to this (inc p and q).
224 }
225 226 // Validate performs basic sanity checks on the key.
227 // It returns nil if the key is valid, or else an error describing a problem.
228 //
229 // It runs faster on valid keys if run after [PrivateKey.Precompute].
230 func (priv *PrivateKey) Validate() error {
231 // We can operate on keys based on d alone, but it isn't possible to encode
232 // with [crypto/x509.MarshalPKCS1PrivateKey], which unfortunately doesn't
233 // return an error.
234 if len(priv.Primes) < 2 {
235 return errors.New("crypto/rsa: missing primes")
236 }
237 // If Precomputed.fips is set, then the key has been validated by
238 // [rsa.NewPrivateKey] or [rsa.NewPrivateKeyWithoutCRT].
239 if priv.Precomputed.fips != nil {
240 return nil
241 }
242 _, err := priv.precompute()
243 return err
244 }
245 246 // rsa1024min is a GODEBUG that re-enables weak RSA keys if set to "0".
247 // See https://go.dev/issue/68762.
248 var rsa1024min = godebug.New("rsa1024min")
249 250 func checkKeySize(size int) error {
251 if size >= 1024 {
252 return nil
253 }
254 if rsa1024min.Value() == "0" {
255 rsa1024min.IncNonDefault()
256 return nil
257 }
258 return fmt.Errorf("crypto/rsa: %d-bit keys are insecure (see https://go.dev/pkg/crypto/rsa#hdr-Minimum_key_size)", size)
259 }
260 261 func checkPublicKeySize(k *PublicKey) error {
262 if k.N == nil {
263 return errors.New("crypto/rsa: missing public modulus")
264 }
265 return checkKeySize(k.N.BitLen())
266 }
267 268 // GenerateKey generates a random RSA private key of the given bit size.
269 //
270 // If bits is less than 1024, [GenerateKey] returns an error. See the "[Minimum
271 // key size]" section for further details.
272 //
273 // Most applications should use [crypto/rand.Reader] as rand. Note that the
274 // returned key does not depend deterministically on the bytes read from rand,
275 // and may change between calls and/or between versions.
276 //
277 // [Minimum key size]: https://pkg.go.dev/crypto/rsa#hdr-Minimum_key_size
278 func GenerateKey(random io.Reader, bits int) (*PrivateKey, error) {
279 if err := checkKeySize(bits); err != nil {
280 return nil, err
281 }
282 283 if boring.Enabled && random == boring.RandReader &&
284 (bits == 2048 || bits == 3072 || bits == 4096) {
285 bN, bE, bD, bP, bQ, bDp, bDq, bQinv, err := boring.GenerateKeyRSA(bits)
286 if err != nil {
287 return nil, err
288 }
289 N := bbig.Dec(bN)
290 E := bbig.Dec(bE)
291 D := bbig.Dec(bD)
292 P := bbig.Dec(bP)
293 Q := bbig.Dec(bQ)
294 Dp := bbig.Dec(bDp)
295 Dq := bbig.Dec(bDq)
296 Qinv := bbig.Dec(bQinv)
297 e64 := E.Int64()
298 if !E.IsInt64() || int64(int(e64)) != e64 {
299 return nil, errors.New("crypto/rsa: generated key exponent too large")
300 }
301 302 key := &PrivateKey{
303 PublicKey: PublicKey{
304 N: N,
305 E: int(e64),
306 },
307 D: D,
308 Primes: []*big.Int{P, Q},
309 Precomputed: PrecomputedValues{
310 Dp: Dp,
311 Dq: Dq,
312 Qinv: Qinv,
313 CRTValues: []CRTValue{:0}, // non-nil, to match Precompute
314 },
315 }
316 return key, nil
317 }
318 319 if fips140only.Enabled && bits < 2048 {
320 return nil, errors.New("crypto/rsa: use of keys smaller than 2048 bits is not allowed in FIPS 140-only mode")
321 }
322 if fips140only.Enabled && bits%2 == 1 {
323 return nil, errors.New("crypto/rsa: use of keys with odd size is not allowed in FIPS 140-only mode")
324 }
325 if fips140only.Enabled && !fips140only.ApprovedRandomReader(random) {
326 return nil, errors.New("crypto/rsa: only crypto/rand.Reader is allowed in FIPS 140-only mode")
327 }
328 329 k, err := rsa.GenerateKey(random, bits)
330 if bits < 256 && err != nil {
331 // Toy-sized keys have a non-negligible chance of hitting two hard
332 // failure cases: p == q and d <= 2^(nlen / 2).
333 //
334 // Since these are impossible to hit for real keys, we don't want to
335 // make the production code path more complex and harder to think about
336 // to handle them.
337 //
338 // Instead, just rerun the whole process a total of 8 times, which
339 // brings the chance of failure for 32-bit keys down to the same as for
340 // 256-bit keys.
341 for i := 1; i < 8 && err != nil; i++ {
342 k, err = rsa.GenerateKey(random, bits)
343 }
344 }
345 if err != nil {
346 return nil, err
347 }
348 N, e, d, p, q, dP, dQ, qInv := k.Export()
349 key := &PrivateKey{
350 PublicKey: PublicKey{
351 N: (&big.Int{}).SetBytes(N),
352 E: e,
353 },
354 D: (&big.Int{}).SetBytes(d),
355 Primes: []*big.Int{(&big.Int{}).SetBytes(p), (&big.Int{}).SetBytes(q),
356 },
357 Precomputed: PrecomputedValues{
358 fips: k,
359 Dp: (&big.Int{}).SetBytes(dP),
360 Dq: (&big.Int{}).SetBytes(dQ),
361 Qinv: (&big.Int{}).SetBytes(qInv),
362 CRTValues: []CRTValue{:0}, // non-nil, to match Precompute
363 },
364 }
365 return key, nil
366 }
367 368 // GenerateMultiPrimeKey generates a multi-prime RSA keypair of the given bit
369 // size and the given random source.
370 //
371 // Table 1 in "[On the Security of Multi-prime RSA]" suggests maximum numbers of
372 // primes for a given bit size.
373 //
374 // Although the public keys are compatible (actually, indistinguishable) from
375 // the 2-prime case, the private keys are not. Thus it may not be possible to
376 // export multi-prime private keys in certain formats or to subsequently import
377 // them into other code.
378 //
379 // This package does not implement CRT optimizations for multi-prime RSA, so the
380 // keys with more than two primes will have worse performance.
381 //
382 // Deprecated: The use of this function with a number of primes different from
383 // two is not recommended for the above security, compatibility, and performance
384 // reasons. Use [GenerateKey] instead.
385 //
386 // [On the Security of Multi-prime RSA]: http://www.cacr.math.uwaterloo.ca/techreports/2006/cacr2006-16.pdf
387 func GenerateMultiPrimeKey(random io.Reader, nprimes int, bits int) (*PrivateKey, error) {
388 if nprimes == 2 {
389 return GenerateKey(random, bits)
390 }
391 if fips140only.Enabled {
392 return nil, errors.New("crypto/rsa: multi-prime RSA is not allowed in FIPS 140-only mode")
393 }
394 395 randutil.MaybeReadByte(random)
396 397 priv := &PrivateKey{}
398 priv.E = 65537
399 400 if nprimes < 2 {
401 return nil, errors.New("crypto/rsa: GenerateMultiPrimeKey: nprimes must be >= 2")
402 }
403 404 if bits < 64 {
405 primeLimit := float64(uint64(1) << uint(bits/nprimes))
406 // pi approximates the number of primes less than primeLimit
407 pi := primeLimit / (math.Log(primeLimit) - 1)
408 // Generated primes start with 11 (in binary) so we can only
409 // use a quarter of them.
410 pi /= 4
411 // Use a factor of two to ensure that key generation terminates
412 // in a reasonable amount of time.
413 pi /= 2
414 if pi <= float64(nprimes) {
415 return nil, errors.New("crypto/rsa: too few primes of given length to generate an RSA key")
416 }
417 }
418 419 primes := []*big.Int{:nprimes}
420 421 NextSetOfPrimes:
422 for {
423 todo := bits
424 // crypto/rand should set the top two bits in each prime.
425 // Thus each prime has the form
426 // p_i = 2^bitlen(p_i) × 0.11... (in base 2).
427 // And the product is:
428 // P = 2^todo × α
429 // where α is the product of nprimes numbers of the form 0.11...
430 //
431 // If α < 1/2 (which can happen for nprimes > 2), we need to
432 // shift todo to compensate for lost bits: the mean value of 0.11...
433 // is 7/8, so todo + shift - nprimes * log2(7/8) ~= bits - 1/2
434 // will give good results.
435 if nprimes >= 7 {
436 todo += (nprimes - 2) / 5
437 }
438 for i := 0; i < nprimes; i++ {
439 var err error
440 primes[i], err = rand.Prime(random, todo/(nprimes-i))
441 if err != nil {
442 return nil, err
443 }
444 todo -= primes[i].BitLen()
445 }
446 447 // Make sure that primes is pairwise unequal.
448 for i, prime := range primes {
449 for j := 0; j < i; j++ {
450 if prime.Cmp(primes[j]) == 0 {
451 continue NextSetOfPrimes
452 }
453 }
454 }
455 456 n := (&big.Int{}).Set(bigOne)
457 totient := (&big.Int{}).Set(bigOne)
458 pminus1 := &big.Int{}
459 for _, prime := range primes {
460 n.Mul(n, prime)
461 pminus1.Sub(prime, bigOne)
462 totient.Mul(totient, pminus1)
463 }
464 if n.BitLen() != bits {
465 // This should never happen for nprimes == 2 because
466 // crypto/rand should set the top two bits in each prime.
467 // For nprimes > 2 we hope it does not happen often.
468 continue NextSetOfPrimes
469 }
470 471 priv.D = &big.Int{}
472 e := big.NewInt(int64(priv.E))
473 ok := priv.D.ModInverse(e, totient)
474 475 if ok != nil {
476 priv.Primes = primes
477 priv.N = n
478 break
479 }
480 }
481 482 priv.Precompute()
483 if err := priv.Validate(); err != nil {
484 return nil, err
485 }
486 487 return priv, nil
488 }
489 490 // ErrMessageTooLong is returned when attempting to encrypt or sign a message
491 // which is too large for the size of the key. When using [SignPSS], this can also
492 // be returned if the size of the salt is too large.
493 var ErrMessageTooLong = errors.New("crypto/rsa: message too long for RSA key size")
494 495 // ErrDecryption represents a failure to decrypt a message.
496 // It is deliberately vague to avoid adaptive attacks.
497 var ErrDecryption = errors.New("crypto/rsa: decryption error")
498 499 // ErrVerification represents a failure to verify a signature.
500 // It is deliberately vague to avoid adaptive attacks.
501 var ErrVerification = errors.New("crypto/rsa: verification error")
502 503 // Precompute performs some calculations that speed up private key operations
504 // in the future. It is safe to run on non-validated private keys.
505 func (priv *PrivateKey) Precompute() {
506 if priv.Precomputed.fips != nil {
507 return
508 }
509 510 precomputed, err := priv.precompute()
511 if err != nil {
512 // We don't have a way to report errors, so just leave the key
513 // unmodified. Validate will re-run precompute.
514 return
515 }
516 priv.Precomputed = precomputed
517 }
518 519 func (priv *PrivateKey) precompute() (PrecomputedValues, error) {
520 var precomputed PrecomputedValues
521 522 if priv.N == nil {
523 return precomputed, errors.New("crypto/rsa: missing public modulus")
524 }
525 if priv.D == nil {
526 return precomputed, errors.New("crypto/rsa: missing private exponent")
527 }
528 if len(priv.Primes) != 2 {
529 return priv.precomputeLegacy()
530 }
531 if priv.Primes[0] == nil {
532 return precomputed, errors.New("crypto/rsa: prime P is nil")
533 }
534 if priv.Primes[1] == nil {
535 return precomputed, errors.New("crypto/rsa: prime Q is nil")
536 }
537 538 // If the CRT values are already set, use them.
539 if priv.Precomputed.Dp != nil && priv.Precomputed.Dq != nil && priv.Precomputed.Qinv != nil {
540 k, err := rsa.NewPrivateKeyWithPrecomputation(priv.N.Bytes(), priv.E, priv.D.Bytes(),
541 priv.Primes[0].Bytes(), priv.Primes[1].Bytes(),
542 priv.Precomputed.Dp.Bytes(), priv.Precomputed.Dq.Bytes(), priv.Precomputed.Qinv.Bytes())
543 if err != nil {
544 return precomputed, err
545 }
546 precomputed = priv.Precomputed
547 precomputed.fips = k
548 precomputed.CRTValues = []CRTValue{:0}
549 return precomputed, nil
550 }
551 552 k, err := rsa.NewPrivateKey(priv.N.Bytes(), priv.E, priv.D.Bytes(),
553 priv.Primes[0].Bytes(), priv.Primes[1].Bytes())
554 if err != nil {
555 return precomputed, err
556 }
557 558 precomputed.fips = k
559 _, _, _, _, _, dP, dQ, qInv := k.Export()
560 precomputed.Dp = (&big.Int{}).SetBytes(dP)
561 precomputed.Dq = (&big.Int{}).SetBytes(dQ)
562 precomputed.Qinv = (&big.Int{}).SetBytes(qInv)
563 precomputed.CRTValues = []CRTValue{:0}
564 return precomputed, nil
565 }
566 567 func (priv *PrivateKey) precomputeLegacy() (PrecomputedValues, error) {
568 var precomputed PrecomputedValues
569 570 k, err := rsa.NewPrivateKeyWithoutCRT(priv.N.Bytes(), priv.E, priv.D.Bytes())
571 if err != nil {
572 return precomputed, err
573 }
574 precomputed.fips = k
575 576 if len(priv.Primes) < 2 {
577 return precomputed, nil
578 }
579 580 // Ensure the Mod and ModInverse calls below don't panic.
581 for _, prime := range priv.Primes {
582 if prime == nil {
583 return precomputed, errors.New("crypto/rsa: prime factor is nil")
584 }
585 if prime.Cmp(bigOne) <= 0 {
586 return precomputed, errors.New("crypto/rsa: prime factor is <= 1")
587 }
588 }
589 590 precomputed.Dp = (&big.Int{}).Sub(priv.Primes[0], bigOne)
591 precomputed.Dp.Mod(priv.D, precomputed.Dp)
592 593 precomputed.Dq = (&big.Int{}).Sub(priv.Primes[1], bigOne)
594 precomputed.Dq.Mod(priv.D, precomputed.Dq)
595 596 precomputed.Qinv = (&big.Int{}).ModInverse(priv.Primes[1], priv.Primes[0])
597 if precomputed.Qinv == nil {
598 return precomputed, errors.New("crypto/rsa: prime factors are not relatively prime")
599 }
600 601 r := (&big.Int{}).Mul(priv.Primes[0], priv.Primes[1])
602 precomputed.CRTValues = []CRTValue{:len(priv.Primes)-2}
603 for i := 2; i < len(priv.Primes); i++ {
604 prime := priv.Primes[i]
605 values := &precomputed.CRTValues[i-2]
606 607 values.Exp = (&big.Int{}).Sub(prime, bigOne)
608 values.Exp.Mod(priv.D, values.Exp)
609 610 values.R = (&big.Int{}).Set(r)
611 values.Coeff = (&big.Int{}).ModInverse(r, prime)
612 if values.Coeff == nil {
613 return precomputed, errors.New("crypto/rsa: prime factors are not relatively prime")
614 }
615 616 r.Mul(r, prime)
617 }
618 619 return precomputed, nil
620 }
621 622 func fipsPublicKey(pub *PublicKey) (*rsa.PublicKey, error) {
623 N, err := bigmod.NewModulus(pub.N.Bytes())
624 if err != nil {
625 return nil, err
626 }
627 return &rsa.PublicKey{N: N, E: pub.E}, nil
628 }
629 630 func fipsPrivateKey(priv *PrivateKey) (*rsa.PrivateKey, error) {
631 if priv.Precomputed.fips != nil {
632 return priv.Precomputed.fips, nil
633 }
634 precomputed, err := priv.precompute()
635 if err != nil {
636 return nil, err
637 }
638 return precomputed.fips, nil
639 }
640