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.
5 // Package rsa implements RSA encryption as specified in PKCS #1 and RFC 8017.
7 // RSA is a single, fundamental operation that is used in this package to
8 // implement either public-key encryption or public-key signatures.
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
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.
22 // The RSA operations in this package are not implemented using constant-time algorithms.
35 "crypto/internal/randutil"
38 var bigZero
= big
.NewInt(0)
39 var bigOne
= big
.NewInt(1)
41 // A PublicKey represents the public part of an RSA key.
42 type PublicKey
struct {
44 E
int // public exponent
47 // Any methods implemented on PublicKey might need to also be implemented on
48 // PrivateKey, as the latter embeds the former and will expose its methods.
50 // Size returns the modulus size in bytes. Raw signatures and ciphertexts
51 // for or by this public key will have the same size.
52 func (pub
*PublicKey
) Size() int {
53 return (pub
.N
.BitLen() + 7) / 8
56 // Equal reports whether pub and x have the same value.
57 func (pub
*PublicKey
) Equal(x crypto
.PublicKey
) bool {
58 xx
, ok
:= x
.(*PublicKey
)
62 return pub
.N
.Cmp(xx
.N
) == 0 && pub
.E
== xx
.E
65 // OAEPOptions is an interface for passing options to OAEP decryption using the
66 // crypto.Decrypter interface.
67 type OAEPOptions
struct {
68 // Hash is the hash function that will be used when generating the mask.
70 // Label is an arbitrary byte string that must be equal to the value
71 // used when encrypting.
76 errPublicModulus
= errors
.New("crypto/rsa: missing public modulus")
77 errPublicExponentSmall
= errors
.New("crypto/rsa: public exponent too small")
78 errPublicExponentLarge
= errors
.New("crypto/rsa: public exponent too large")
81 // checkPub sanity checks the public key before we use it.
82 // We require pub.E to fit into a 32-bit integer so that we
83 // do not have different behavior depending on whether
84 // int is 32 or 64 bits. See also
85 // https://www.imperialviolet.org/2012/03/16/rsae.html.
86 func checkPub(pub
*PublicKey
) error
{
88 return errPublicModulus
91 return errPublicExponentSmall
94 return errPublicExponentLarge
99 // A PrivateKey represents an RSA key
100 type PrivateKey
struct {
101 PublicKey
// public part.
102 D
*big
.Int
// private exponent
103 Primes
[]*big
.Int
// prime factors of N, has >= 2 elements.
105 // Precomputed contains precomputed values that speed up private
106 // operations, if available.
107 Precomputed PrecomputedValues
110 // Public returns the public key corresponding to priv.
111 func (priv
*PrivateKey
) Public() crypto
.PublicKey
{
112 return &priv
.PublicKey
115 // Equal reports whether priv and x have equivalent values. It ignores
116 // Precomputed values.
117 func (priv
*PrivateKey
) Equal(x crypto
.PrivateKey
) bool {
118 xx
, ok
:= x
.(*PrivateKey
)
122 if !priv
.PublicKey
.Equal(&xx
.PublicKey
) || priv
.D
.Cmp(xx
.D
) != 0 {
125 if len(priv
.Primes
) != len(xx
.Primes
) {
128 for i
:= range priv
.Primes
{
129 if priv
.Primes
[i
].Cmp(xx
.Primes
[i
]) != 0 {
136 // Sign signs digest with priv, reading randomness from rand. If opts is a
137 // *PSSOptions then the PSS algorithm will be used, otherwise PKCS #1 v1.5 will
138 // be used. digest must be the result of hashing the input message using
141 // This method implements crypto.Signer, which is an interface to support keys
142 // where the private part is kept in, for example, a hardware module. Common
143 // uses should use the Sign* functions in this package directly.
144 func (priv
*PrivateKey
) Sign(rand io
.Reader
, digest
[]byte, opts crypto
.SignerOpts
) ([]byte, error
) {
145 if pssOpts
, ok
:= opts
.(*PSSOptions
); ok
{
146 return SignPSS(rand
, priv
, pssOpts
.Hash
, digest
, pssOpts
)
149 return SignPKCS1v15(rand
, priv
, opts
.HashFunc(), digest
)
152 // Decrypt decrypts ciphertext with priv. If opts is nil or of type
153 // *PKCS1v15DecryptOptions then PKCS #1 v1.5 decryption is performed. Otherwise
154 // opts must have type *OAEPOptions and OAEP decryption is done.
155 func (priv
*PrivateKey
) Decrypt(rand io
.Reader
, ciphertext
[]byte, opts crypto
.DecrypterOpts
) (plaintext
[]byte, err error
) {
157 return DecryptPKCS1v15(rand
, priv
, ciphertext
)
160 switch opts
:= opts
.(type) {
162 return DecryptOAEP(opts
.Hash
.New(), rand
, priv
, ciphertext
, opts
.Label
)
164 case *PKCS1v15DecryptOptions
:
165 if l
:= opts
.SessionKeyLen
; l
> 0 {
166 plaintext
= make([]byte, l
)
167 if _
, err
:= io
.ReadFull(rand
, plaintext
); err
!= nil {
170 if err
:= DecryptPKCS1v15SessionKey(rand
, priv
, ciphertext
, plaintext
); err
!= nil {
173 return plaintext
, nil
175 return DecryptPKCS1v15(rand
, priv
, ciphertext
)
179 return nil, errors
.New("crypto/rsa: invalid options for Decrypt")
183 type PrecomputedValues
struct {
184 Dp
, Dq
*big
.Int
// D mod (P-1) (or mod Q-1)
185 Qinv
*big
.Int
// Q^-1 mod P
187 // CRTValues is used for the 3rd and subsequent primes. Due to a
188 // historical accident, the CRT for the first two primes is handled
189 // differently in PKCS #1 and interoperability is sufficiently
190 // important that we mirror this.
194 // CRTValue contains the precomputed Chinese remainder theorem values.
195 type CRTValue
struct {
196 Exp
*big
.Int
// D mod (prime-1).
197 Coeff
*big
.Int
// R·Coeff ≡ 1 mod Prime.
198 R
*big
.Int
// product of primes prior to this (inc p and q).
201 // Validate performs basic sanity checks on the key.
202 // It returns nil if the key is valid, or else an error describing a problem.
203 func (priv
*PrivateKey
) Validate() error
{
204 if err
:= checkPub(&priv
.PublicKey
); err
!= nil {
208 // Check that Πprimes == n.
209 modulus
:= new(big
.Int
).Set(bigOne
)
210 for _
, prime
:= range priv
.Primes
{
211 // Any primes ≤ 1 will cause divide-by-zero panics later.
212 if prime
.Cmp(bigOne
) <= 0 {
213 return errors
.New("crypto/rsa: invalid prime value")
215 modulus
.Mul(modulus
, prime
)
217 if modulus
.Cmp(priv
.N
) != 0 {
218 return errors
.New("crypto/rsa: invalid modulus")
221 // Check that de ≡ 1 mod p-1, for each prime.
222 // This implies that e is coprime to each p-1 as e has a multiplicative
223 // inverse. Therefore e is coprime to lcm(p-1,q-1,r-1,...) =
224 // exponent(ℤ/nℤ). It also implies that a^de ≡ a mod p as a^(p-1) ≡ 1
225 // mod p. Thus a^de ≡ a mod n for all a coprime to n, as required.
226 congruence
:= new(big
.Int
)
227 de
:= new(big
.Int
).SetInt64(int64(priv
.E
))
229 for _
, prime
:= range priv
.Primes
{
230 pminus1
:= new(big
.Int
).Sub(prime
, bigOne
)
231 congruence
.Mod(de
, pminus1
)
232 if congruence
.Cmp(bigOne
) != 0 {
233 return errors
.New("crypto/rsa: invalid exponents")
239 // GenerateKey generates an RSA keypair of the given bit size using the
240 // random source random (for example, crypto/rand.Reader).
241 func GenerateKey(random io
.Reader
, bits
int) (*PrivateKey
, error
) {
242 return GenerateMultiPrimeKey(random
, 2, bits
)
245 // GenerateMultiPrimeKey generates a multi-prime RSA keypair of the given bit
246 // size and the given random source, as suggested in [1]. Although the public
247 // keys are compatible (actually, indistinguishable) from the 2-prime case,
248 // the private keys are not. Thus it may not be possible to export multi-prime
249 // private keys in certain formats or to subsequently import them into other
252 // Table 1 in [2] suggests maximum numbers of primes for a given size.
254 // [1] US patent 4405829 (1972, expired)
255 // [2] http://www.cacr.math.uwaterloo.ca/techreports/2006/cacr2006-16.pdf
256 func GenerateMultiPrimeKey(random io
.Reader
, nprimes
int, bits
int) (*PrivateKey
, error
) {
257 randutil
.MaybeReadByte(random
)
259 priv
:= new(PrivateKey
)
263 return nil, errors
.New("crypto/rsa: GenerateMultiPrimeKey: nprimes must be >= 2")
267 primeLimit
:= float64(uint64(1) << uint(bits
/nprimes
))
268 // pi approximates the number of primes less than primeLimit
269 pi
:= primeLimit
/ (math
.Log(primeLimit
) - 1)
270 // Generated primes start with 11 (in binary) so we can only
271 // use a quarter of them.
273 // Use a factor of two to ensure that key generation terminates
274 // in a reasonable amount of time.
276 if pi
<= float64(nprimes
) {
277 return nil, errors
.New("crypto/rsa: too few primes of given length to generate an RSA key")
281 primes
:= make([]*big
.Int
, nprimes
)
286 // crypto/rand should set the top two bits in each prime.
287 // Thus each prime has the form
288 // p_i = 2^bitlen(p_i) × 0.11... (in base 2).
289 // And the product is:
291 // where α is the product of nprimes numbers of the form 0.11...
293 // If α < 1/2 (which can happen for nprimes > 2), we need to
294 // shift todo to compensate for lost bits: the mean value of 0.11...
295 // is 7/8, so todo + shift - nprimes * log2(7/8) ~= bits - 1/2
296 // will give good results.
298 todo
+= (nprimes
- 2) / 5
300 for i
:= 0; i
< nprimes
; i
++ {
302 primes
[i
], err
= rand
.Prime(random
, todo
/(nprimes
-i
))
306 todo
-= primes
[i
].BitLen()
309 // Make sure that primes is pairwise unequal.
310 for i
, prime
:= range primes
{
311 for j
:= 0; j
< i
; j
++ {
312 if prime
.Cmp(primes
[j
]) == 0 {
313 continue NextSetOfPrimes
318 n
:= new(big
.Int
).Set(bigOne
)
319 totient
:= new(big
.Int
).Set(bigOne
)
320 pminus1
:= new(big
.Int
)
321 for _
, prime
:= range primes
{
323 pminus1
.Sub(prime
, bigOne
)
324 totient
.Mul(totient
, pminus1
)
326 if n
.BitLen() != bits
{
327 // This should never happen for nprimes == 2 because
328 // crypto/rand should set the top two bits in each prime.
329 // For nprimes > 2 we hope it does not happen often.
330 continue NextSetOfPrimes
333 priv
.D
= new(big
.Int
)
334 e
:= big
.NewInt(int64(priv
.E
))
335 ok
:= priv
.D
.ModInverse(e
, totient
)
348 // incCounter increments a four byte, big-endian counter.
349 func incCounter(c
*[4]byte) {
350 if c
[3]++; c
[3] != 0 {
353 if c
[2]++; c
[2] != 0 {
356 if c
[1]++; c
[1] != 0 {
362 // mgf1XOR XORs the bytes in out with a mask generated using the MGF1 function
363 // specified in PKCS #1 v2.1.
364 func mgf1XOR(out
[]byte, hash hash
.Hash
, seed
[]byte) {
369 for done
< len(out
) {
371 hash
.Write(counter
[0:4])
372 digest
= hash
.Sum(digest
[:0])
375 for i
:= 0; i
< len(digest
) && done
< len(out
); i
++ {
376 out
[done
] ^= digest
[i
]
383 // ErrMessageTooLong is returned when attempting to encrypt a message which is
384 // too large for the size of the public key.
385 var ErrMessageTooLong
= errors
.New("crypto/rsa: message too long for RSA public key size")
387 func encrypt(c
*big
.Int
, pub
*PublicKey
, m
*big
.Int
) *big
.Int
{
388 e
:= big
.NewInt(int64(pub
.E
))
393 // EncryptOAEP encrypts the given message with RSA-OAEP.
395 // OAEP is parameterised by a hash function that is used as a random oracle.
396 // Encryption and decryption of a given message must use the same hash function
397 // and sha256.New() is a reasonable choice.
399 // The random parameter is used as a source of entropy to ensure that
400 // encrypting the same message twice doesn't result in the same ciphertext.
402 // The label parameter may contain arbitrary data that will not be encrypted,
403 // but which gives important context to the message. For example, if a given
404 // public key is used to encrypt two types of messages then distinct label
405 // values could be used to ensure that a ciphertext for one purpose cannot be
406 // used for another by an attacker. If not required it can be empty.
408 // The message must be no longer than the length of the public modulus minus
409 // twice the hash length, minus a further 2.
410 func EncryptOAEP(hash hash
.Hash
, random io
.Reader
, pub
*PublicKey
, msg
[]byte, label
[]byte) ([]byte, error
) {
411 if err
:= checkPub(pub
); err
!= nil {
416 if len(msg
) > k
-2*hash
.Size()-2 {
417 return nil, ErrMessageTooLong
421 lHash
:= hash
.Sum(nil)
424 em
:= make([]byte, k
)
425 seed
:= em
[1 : 1+hash
.Size()]
426 db
:= em
[1+hash
.Size():]
428 copy(db
[0:hash
.Size()], lHash
)
429 db
[len(db
)-len(msg
)-1] = 1
430 copy(db
[len(db
)-len(msg
):], msg
)
432 _
, err
:= io
.ReadFull(random
, seed
)
437 mgf1XOR(db
, hash
, seed
)
438 mgf1XOR(seed
, hash
, db
)
442 c
:= encrypt(new(big
.Int
), pub
, m
)
444 out
:= make([]byte, k
)
445 return c
.FillBytes(out
), nil
448 // ErrDecryption represents a failure to decrypt a message.
449 // It is deliberately vague to avoid adaptive attacks.
450 var ErrDecryption
= errors
.New("crypto/rsa: decryption error")
452 // ErrVerification represents a failure to verify a signature.
453 // It is deliberately vague to avoid adaptive attacks.
454 var ErrVerification
= errors
.New("crypto/rsa: verification error")
456 // Precompute performs some calculations that speed up private key operations
458 func (priv
*PrivateKey
) Precompute() {
459 if priv
.Precomputed
.Dp
!= nil {
463 priv
.Precomputed
.Dp
= new(big
.Int
).Sub(priv
.Primes
[0], bigOne
)
464 priv
.Precomputed
.Dp
.Mod(priv
.D
, priv
.Precomputed
.Dp
)
466 priv
.Precomputed
.Dq
= new(big
.Int
).Sub(priv
.Primes
[1], bigOne
)
467 priv
.Precomputed
.Dq
.Mod(priv
.D
, priv
.Precomputed
.Dq
)
469 priv
.Precomputed
.Qinv
= new(big
.Int
).ModInverse(priv
.Primes
[1], priv
.Primes
[0])
471 r
:= new(big
.Int
).Mul(priv
.Primes
[0], priv
.Primes
[1])
472 priv
.Precomputed
.CRTValues
= make([]CRTValue
, len(priv
.Primes
)-2)
473 for i
:= 2; i
< len(priv
.Primes
); i
++ {
474 prime
:= priv
.Primes
[i
]
475 values
:= &priv
.Precomputed
.CRTValues
[i
-2]
477 values
.Exp
= new(big
.Int
).Sub(prime
, bigOne
)
478 values
.Exp
.Mod(priv
.D
, values
.Exp
)
480 values
.R
= new(big
.Int
).Set(r
)
481 values
.Coeff
= new(big
.Int
).ModInverse(r
, prime
)
487 // decrypt performs an RSA decryption, resulting in a plaintext integer. If a
488 // random source is given, RSA blinding is used.
489 func decrypt(random io
.Reader
, priv
*PrivateKey
, c
*big
.Int
) (m
*big
.Int
, err error
) {
490 // TODO(agl): can we get away with reusing blinds?
491 if c
.Cmp(priv
.N
) > 0 {
495 if priv
.N
.Sign() == 0 {
496 return nil, ErrDecryption
501 randutil
.MaybeReadByte(random
)
503 // Blinding enabled. Blinding involves multiplying c by r^e.
504 // Then the decryption operation performs (m^e * r^e)^d mod n
505 // which equals mr mod n. The factor of r can then be removed
506 // by multiplying by the multiplicative inverse of r.
511 r
, err
= rand
.Int(random
, priv
.N
)
515 if r
.Cmp(bigZero
) == 0 {
518 ok
:= ir
.ModInverse(r
, priv
.N
)
523 bigE
:= big
.NewInt(int64(priv
.E
))
524 rpowe
:= new(big
.Int
).Exp(r
, bigE
, priv
.N
) // N != 0
525 cCopy
:= new(big
.Int
).Set(c
)
526 cCopy
.Mul(cCopy
, rpowe
)
527 cCopy
.Mod(cCopy
, priv
.N
)
531 if priv
.Precomputed
.Dp
== nil {
532 m
= new(big
.Int
).Exp(c
, priv
.D
, priv
.N
)
534 // We have the precalculated values needed for the CRT.
535 m
= new(big
.Int
).Exp(c
, priv
.Precomputed
.Dp
, priv
.Primes
[0])
536 m2
:= new(big
.Int
).Exp(c
, priv
.Precomputed
.Dq
, priv
.Primes
[1])
539 m
.Add(m
, priv
.Primes
[0])
541 m
.Mul(m
, priv
.Precomputed
.Qinv
)
542 m
.Mod(m
, priv
.Primes
[0])
543 m
.Mul(m
, priv
.Primes
[1])
546 for i
, values
:= range priv
.Precomputed
.CRTValues
{
547 prime
:= priv
.Primes
[2+i
]
548 m2
.Exp(c
, values
.Exp
, prime
)
550 m2
.Mul(m2
, values
.Coeff
)
569 func decryptAndCheck(random io
.Reader
, priv
*PrivateKey
, c
*big
.Int
) (m
*big
.Int
, err error
) {
570 m
, err
= decrypt(random
, priv
, c
)
575 // In order to defend against errors in the CRT computation, m^e is
576 // calculated, which should match the original ciphertext.
577 check
:= encrypt(new(big
.Int
), &priv
.PublicKey
, m
)
578 if c
.Cmp(check
) != 0 {
579 return nil, errors
.New("rsa: internal error")
584 // DecryptOAEP decrypts ciphertext using RSA-OAEP.
586 // OAEP is parameterised by a hash function that is used as a random oracle.
587 // Encryption and decryption of a given message must use the same hash function
588 // and sha256.New() is a reasonable choice.
590 // The random parameter, if not nil, is used to blind the private-key operation
591 // and avoid timing side-channel attacks. Blinding is purely internal to this
592 // function – the random data need not match that used when encrypting.
594 // The label parameter must match the value given when encrypting. See
595 // EncryptOAEP for details.
596 func DecryptOAEP(hash hash
.Hash
, random io
.Reader
, priv
*PrivateKey
, ciphertext
[]byte, label
[]byte) ([]byte, error
) {
597 if err
:= checkPub(&priv
.PublicKey
); err
!= nil {
601 if len(ciphertext
) > k ||
602 k
< hash
.Size()*2+2 {
603 return nil, ErrDecryption
606 c
:= new(big
.Int
).SetBytes(ciphertext
)
608 m
, err
:= decrypt(random
, priv
, c
)
614 lHash
:= hash
.Sum(nil)
617 // We probably leak the number of leading zeros.
618 // It's not clear that we can do anything about this.
619 em
:= m
.FillBytes(make([]byte, k
))
621 firstByteIsZero
:= subtle
.ConstantTimeByteEq(em
[0], 0)
623 seed
:= em
[1 : hash
.Size()+1]
624 db
:= em
[hash
.Size()+1:]
626 mgf1XOR(seed
, hash
, db
)
627 mgf1XOR(db
, hash
, seed
)
629 lHash2
:= db
[0:hash
.Size()]
631 // We have to validate the plaintext in constant time in order to avoid
632 // attacks like: J. Manger. A Chosen Ciphertext Attack on RSA Optimal
633 // Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1
634 // v2.0. In J. Kilian, editor, Advances in Cryptology.
635 lHash2Good
:= subtle
.ConstantTimeCompare(lHash
, lHash2
)
637 // The remainder of the plaintext must be zero or more 0x00, followed
638 // by 0x01, followed by the message.
639 // lookingForIndex: 1 iff we are still looking for the 0x01
640 // index: the offset of the first 0x01 byte
641 // invalid: 1 iff we saw a non-zero byte before the 0x01.
642 var lookingForIndex
, index
, invalid
int
644 rest
:= db
[hash
.Size():]
646 for i
:= 0; i
< len(rest
); i
++ {
647 equals0
:= subtle
.ConstantTimeByteEq(rest
[i
], 0)
648 equals1
:= subtle
.ConstantTimeByteEq(rest
[i
], 1)
649 index
= subtle
.ConstantTimeSelect(lookingForIndex
&equals1
, i
, index
)
650 lookingForIndex
= subtle
.ConstantTimeSelect(equals1
, 0, lookingForIndex
)
651 invalid
= subtle
.ConstantTimeSelect(lookingForIndex
&^equals0
, 1, invalid
)
654 if firstByteIsZero
&lHash2Good
&^invalid
&^lookingForIndex
!= 1 {
655 return nil, ErrDecryption
658 return rest
[index
+1:], nil