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.
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 two, 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 struct 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.
36 var bigZero
= big
.NewInt(0)
37 var bigOne
= big
.NewInt(1)
39 // A PublicKey represents the public part of an RSA key.
40 type PublicKey
struct {
42 E
int // public exponent
45 // OAEPOptions is an interface for passing options to OAEP decryption using the
46 // crypto.Decrypter interface.
47 type OAEPOptions
struct {
48 // Hash is the hash function that will be used when generating the mask.
50 // Label is an arbitrary byte string that must be equal to the value
51 // used when encrypting.
56 errPublicModulus
= errors
.New("crypto/rsa: missing public modulus")
57 errPublicExponentSmall
= errors
.New("crypto/rsa: public exponent too small")
58 errPublicExponentLarge
= errors
.New("crypto/rsa: public exponent too large")
61 // checkPub sanity checks the public key before we use it.
62 // We require pub.E to fit into a 32-bit integer so that we
63 // do not have different behavior depending on whether
64 // int is 32 or 64 bits. See also
65 // http://www.imperialviolet.org/2012/03/16/rsae.html.
66 func checkPub(pub
*PublicKey
) error
{
68 return errPublicModulus
71 return errPublicExponentSmall
74 return errPublicExponentLarge
79 // A PrivateKey represents an RSA key
80 type PrivateKey
struct {
81 PublicKey
// public part.
82 D
*big
.Int
// private exponent
83 Primes
[]*big
.Int
// prime factors of N, has >= 2 elements.
85 // Precomputed contains precomputed values that speed up private
86 // operations, if available.
87 Precomputed PrecomputedValues
90 // Public returns the public key corresponding to priv.
91 func (priv
*PrivateKey
) Public() crypto
.PublicKey
{
92 return &priv
.PublicKey
95 // Sign signs digest with priv, reading randomness from rand. If opts is a
96 // *PSSOptions then the PSS algorithm will be used, otherwise PKCS#1 v1.5 will
99 // This method implements crypto.Signer, which is an interface to support keys
100 // where the private part is kept in, for example, a hardware module. Common
101 // uses should use the Sign* functions in this package directly.
102 func (priv
*PrivateKey
) Sign(rand io
.Reader
, digest
[]byte, opts crypto
.SignerOpts
) ([]byte, error
) {
103 if pssOpts
, ok
:= opts
.(*PSSOptions
); ok
{
104 return SignPSS(rand
, priv
, pssOpts
.Hash
, digest
, pssOpts
)
107 return SignPKCS1v15(rand
, priv
, opts
.HashFunc(), digest
)
110 // Decrypt decrypts ciphertext with priv. If opts is nil or of type
111 // *PKCS1v15DecryptOptions then PKCS#1 v1.5 decryption is performed. Otherwise
112 // opts must have type *OAEPOptions and OAEP decryption is done.
113 func (priv
*PrivateKey
) Decrypt(rand io
.Reader
, ciphertext
[]byte, opts crypto
.DecrypterOpts
) (plaintext
[]byte, err error
) {
115 return DecryptPKCS1v15(rand
, priv
, ciphertext
)
118 switch opts
:= opts
.(type) {
120 return DecryptOAEP(opts
.Hash
.New(), rand
, priv
, ciphertext
, opts
.Label
)
122 case *PKCS1v15DecryptOptions
:
123 if l
:= opts
.SessionKeyLen
; l
> 0 {
124 plaintext
= make([]byte, l
)
125 if _
, err
:= io
.ReadFull(rand
, plaintext
); err
!= nil {
128 if err
:= DecryptPKCS1v15SessionKey(rand
, priv
, ciphertext
, plaintext
); err
!= nil {
131 return plaintext
, nil
133 return DecryptPKCS1v15(rand
, priv
, ciphertext
)
137 return nil, errors
.New("crypto/rsa: invalid options for Decrypt")
141 type PrecomputedValues
struct {
142 Dp
, Dq
*big
.Int
// D mod (P-1) (or mod Q-1)
143 Qinv
*big
.Int
// Q^-1 mod P
145 // CRTValues is used for the 3rd and subsequent primes. Due to a
146 // historical accident, the CRT for the first two primes is handled
147 // differently in PKCS#1 and interoperability is sufficiently
148 // important that we mirror this.
152 // CRTValue contains the precomputed Chinese remainder theorem values.
153 type CRTValue
struct {
154 Exp
*big
.Int
// D mod (prime-1).
155 Coeff
*big
.Int
// R·Coeff ≡ 1 mod Prime.
156 R
*big
.Int
// product of primes prior to this (inc p and q).
159 // Validate performs basic sanity checks on the key.
160 // It returns nil if the key is valid, or else an error describing a problem.
161 func (priv
*PrivateKey
) Validate() error
{
162 if err
:= checkPub(&priv
.PublicKey
); err
!= nil {
166 // Check that Πprimes == n.
167 modulus
:= new(big
.Int
).Set(bigOne
)
168 for _
, prime
:= range priv
.Primes
{
169 // Any primes ≤ 1 will cause divide-by-zero panics later.
170 if prime
.Cmp(bigOne
) <= 0 {
171 return errors
.New("crypto/rsa: invalid prime value")
173 modulus
.Mul(modulus
, prime
)
175 if modulus
.Cmp(priv
.N
) != 0 {
176 return errors
.New("crypto/rsa: invalid modulus")
179 // Check that de ≡ 1 mod p-1, for each prime.
180 // This implies that e is coprime to each p-1 as e has a multiplicative
181 // inverse. Therefore e is coprime to lcm(p-1,q-1,r-1,...) =
182 // exponent(ℤ/nℤ). It also implies that a^de ≡ a mod p as a^(p-1) ≡ 1
183 // mod p. Thus a^de ≡ a mod n for all a coprime to n, as required.
184 congruence
:= new(big
.Int
)
185 de
:= new(big
.Int
).SetInt64(int64(priv
.E
))
187 for _
, prime
:= range priv
.Primes
{
188 pminus1
:= new(big
.Int
).Sub(prime
, bigOne
)
189 congruence
.Mod(de
, pminus1
)
190 if congruence
.Cmp(bigOne
) != 0 {
191 return errors
.New("crypto/rsa: invalid exponents")
197 // GenerateKey generates an RSA keypair of the given bit size using the
198 // random source random (for example, crypto/rand.Reader).
199 func GenerateKey(random io
.Reader
, bits
int) (*PrivateKey
, error
) {
200 return GenerateMultiPrimeKey(random
, 2, bits
)
203 // GenerateMultiPrimeKey generates a multi-prime RSA keypair of the given bit
204 // size and the given random source, as suggested in [1]. Although the public
205 // keys are compatible (actually, indistinguishable) from the 2-prime case,
206 // the private keys are not. Thus it may not be possible to export multi-prime
207 // private keys in certain formats or to subsequently import them into other
210 // Table 1 in [2] suggests maximum numbers of primes for a given size.
212 // [1] US patent 4405829 (1972, expired)
213 // [2] http://www.cacr.math.uwaterloo.ca/techreports/2006/cacr2006-16.pdf
214 func GenerateMultiPrimeKey(random io
.Reader
, nprimes
int, bits
int) (*PrivateKey
, error
) {
215 priv
:= new(PrivateKey
)
219 return nil, errors
.New("crypto/rsa: GenerateMultiPrimeKey: nprimes must be >= 2")
223 primeLimit
:= float64(uint64(1) << uint(bits
/nprimes
))
224 // pi approximates the number of primes less than primeLimit
225 pi
:= primeLimit
/ (math
.Log(primeLimit
) - 1)
226 // Generated primes start with 11 (in binary) so we can only
227 // use a quarter of them.
229 // Use a factor of two to ensure that key generation terminates
230 // in a reasonable amount of time.
232 if pi
<= float64(nprimes
) {
233 return nil, errors
.New("crypto/rsa: too few primes of given length to generate an RSA key")
237 primes
:= make([]*big
.Int
, nprimes
)
242 // crypto/rand should set the top two bits in each prime.
243 // Thus each prime has the form
244 // p_i = 2^bitlen(p_i) × 0.11... (in base 2).
245 // And the product is:
247 // where α is the product of nprimes numbers of the form 0.11...
249 // If α < 1/2 (which can happen for nprimes > 2), we need to
250 // shift todo to compensate for lost bits: the mean value of 0.11...
251 // is 7/8, so todo + shift - nprimes * log2(7/8) ~= bits - 1/2
252 // will give good results.
254 todo
+= (nprimes
- 2) / 5
256 for i
:= 0; i
< nprimes
; i
++ {
258 primes
[i
], err
= rand
.Prime(random
, todo
/(nprimes
-i
))
262 todo
-= primes
[i
].BitLen()
265 // Make sure that primes is pairwise unequal.
266 for i
, prime
:= range primes
{
267 for j
:= 0; j
< i
; j
++ {
268 if prime
.Cmp(primes
[j
]) == 0 {
269 continue NextSetOfPrimes
274 n
:= new(big
.Int
).Set(bigOne
)
275 totient
:= new(big
.Int
).Set(bigOne
)
276 pminus1
:= new(big
.Int
)
277 for _
, prime
:= range primes
{
279 pminus1
.Sub(prime
, bigOne
)
280 totient
.Mul(totient
, pminus1
)
282 if n
.BitLen() != bits
{
283 // This should never happen for nprimes == 2 because
284 // crypto/rand should set the top two bits in each prime.
285 // For nprimes > 2 we hope it does not happen often.
286 continue NextSetOfPrimes
290 priv
.D
= new(big
.Int
)
291 e
:= big
.NewInt(int64(priv
.E
))
292 g
.GCD(priv
.D
, nil, e
, totient
)
294 if g
.Cmp(bigOne
) == 0 {
295 if priv
.D
.Sign() < 0 {
296 priv
.D
.Add(priv
.D
, totient
)
309 // incCounter increments a four byte, big-endian counter.
310 func incCounter(c
*[4]byte) {
311 if c
[3]++; c
[3] != 0 {
314 if c
[2]++; c
[2] != 0 {
317 if c
[1]++; c
[1] != 0 {
323 // mgf1XOR XORs the bytes in out with a mask generated using the MGF1 function
324 // specified in PKCS#1 v2.1.
325 func mgf1XOR(out
[]byte, hash hash
.Hash
, seed
[]byte) {
330 for done
< len(out
) {
332 hash
.Write(counter
[0:4])
333 digest
= hash
.Sum(digest
[:0])
336 for i
:= 0; i
< len(digest
) && done
< len(out
); i
++ {
337 out
[done
] ^= digest
[i
]
344 // ErrMessageTooLong is returned when attempting to encrypt a message which is
345 // too large for the size of the public key.
346 var ErrMessageTooLong
= errors
.New("crypto/rsa: message too long for RSA public key size")
348 func encrypt(c
*big
.Int
, pub
*PublicKey
, m
*big
.Int
) *big
.Int
{
349 e
:= big
.NewInt(int64(pub
.E
))
354 // EncryptOAEP encrypts the given message with RSA-OAEP.
356 // OAEP is parameterised by a hash function that is used as a random oracle.
357 // Encryption and decryption of a given message must use the same hash function
358 // and sha256.New() is a reasonable choice.
360 // The random parameter is used as a source of entropy to ensure that
361 // encrypting the same message twice doesn't result in the same ciphertext.
363 // The label parameter may contain arbitrary data that will not be encrypted,
364 // but which gives important context to the message. For example, if a given
365 // public key is used to decrypt two types of messages then distinct label
366 // values could be used to ensure that a ciphertext for one purpose cannot be
367 // used for another by an attacker. If not required it can be empty.
369 // The message must be no longer than the length of the public modulus minus
370 // twice the hash length, minus a further 2.
371 func EncryptOAEP(hash hash
.Hash
, random io
.Reader
, pub
*PublicKey
, msg
[]byte, label
[]byte) ([]byte, error
) {
372 if err
:= checkPub(pub
); err
!= nil {
376 k
:= (pub
.N
.BitLen() + 7) / 8
377 if len(msg
) > k
-2*hash
.Size()-2 {
378 return nil, ErrMessageTooLong
382 lHash
:= hash
.Sum(nil)
385 em
:= make([]byte, k
)
386 seed
:= em
[1 : 1+hash
.Size()]
387 db
:= em
[1+hash
.Size():]
389 copy(db
[0:hash
.Size()], lHash
)
390 db
[len(db
)-len(msg
)-1] = 1
391 copy(db
[len(db
)-len(msg
):], msg
)
393 _
, err
:= io
.ReadFull(random
, seed
)
398 mgf1XOR(db
, hash
, seed
)
399 mgf1XOR(seed
, hash
, db
)
403 c
:= encrypt(new(big
.Int
), pub
, m
)
407 // If the output is too small, we need to left-pad with zeros.
409 copy(t
[k
-len(out
):], out
)
416 // ErrDecryption represents a failure to decrypt a message.
417 // It is deliberately vague to avoid adaptive attacks.
418 var ErrDecryption
= errors
.New("crypto/rsa: decryption error")
420 // ErrVerification represents a failure to verify a signature.
421 // It is deliberately vague to avoid adaptive attacks.
422 var ErrVerification
= errors
.New("crypto/rsa: verification error")
424 // modInverse returns ia, the inverse of a in the multiplicative group of prime
425 // order n. It requires that a be a member of the group (i.e. less than n).
426 func modInverse(a
, n
*big
.Int
) (ia
*big
.Int
, ok
bool) {
430 if g
.Cmp(bigOne
) != 0 {
431 // In this case, a and n aren't coprime and we cannot calculate
432 // the inverse. This happens because the values of n are nearly
433 // prime (being the product of two primes) rather than truly
438 if x
.Cmp(bigOne
) < 0 {
439 // 0 is not the multiplicative inverse of any element so, if x
440 // < 1, then x is negative.
447 // Precompute performs some calculations that speed up private key operations
449 func (priv
*PrivateKey
) Precompute() {
450 if priv
.Precomputed
.Dp
!= nil {
454 priv
.Precomputed
.Dp
= new(big
.Int
).Sub(priv
.Primes
[0], bigOne
)
455 priv
.Precomputed
.Dp
.Mod(priv
.D
, priv
.Precomputed
.Dp
)
457 priv
.Precomputed
.Dq
= new(big
.Int
).Sub(priv
.Primes
[1], bigOne
)
458 priv
.Precomputed
.Dq
.Mod(priv
.D
, priv
.Precomputed
.Dq
)
460 priv
.Precomputed
.Qinv
= new(big
.Int
).ModInverse(priv
.Primes
[1], priv
.Primes
[0])
462 r
:= new(big
.Int
).Mul(priv
.Primes
[0], priv
.Primes
[1])
463 priv
.Precomputed
.CRTValues
= make([]CRTValue
, len(priv
.Primes
)-2)
464 for i
:= 2; i
< len(priv
.Primes
); i
++ {
465 prime
:= priv
.Primes
[i
]
466 values
:= &priv
.Precomputed
.CRTValues
[i
-2]
468 values
.Exp
= new(big
.Int
).Sub(prime
, bigOne
)
469 values
.Exp
.Mod(priv
.D
, values
.Exp
)
471 values
.R
= new(big
.Int
).Set(r
)
472 values
.Coeff
= new(big
.Int
).ModInverse(r
, prime
)
478 // decrypt performs an RSA decryption, resulting in a plaintext integer. If a
479 // random source is given, RSA blinding is used.
480 func decrypt(random io
.Reader
, priv
*PrivateKey
, c
*big
.Int
) (m
*big
.Int
, err error
) {
481 // TODO(agl): can we get away with reusing blinds?
482 if c
.Cmp(priv
.N
) > 0 {
486 if priv
.N
.Sign() == 0 {
487 return nil, ErrDecryption
492 // Blinding enabled. Blinding involves multiplying c by r^e.
493 // Then the decryption operation performs (m^e * r^e)^d mod n
494 // which equals mr mod n. The factor of r can then be removed
495 // by multiplying by the multiplicative inverse of r.
500 r
, err
= rand
.Int(random
, priv
.N
)
504 if r
.Cmp(bigZero
) == 0 {
508 ir
, ok
= modInverse(r
, priv
.N
)
513 bigE
:= big
.NewInt(int64(priv
.E
))
514 rpowe
:= new(big
.Int
).Exp(r
, bigE
, priv
.N
) // N != 0
515 cCopy
:= new(big
.Int
).Set(c
)
516 cCopy
.Mul(cCopy
, rpowe
)
517 cCopy
.Mod(cCopy
, priv
.N
)
521 if priv
.Precomputed
.Dp
== nil {
522 m
= new(big
.Int
).Exp(c
, priv
.D
, priv
.N
)
524 // We have the precalculated values needed for the CRT.
525 m
= new(big
.Int
).Exp(c
, priv
.Precomputed
.Dp
, priv
.Primes
[0])
526 m2
:= new(big
.Int
).Exp(c
, priv
.Precomputed
.Dq
, priv
.Primes
[1])
529 m
.Add(m
, priv
.Primes
[0])
531 m
.Mul(m
, priv
.Precomputed
.Qinv
)
532 m
.Mod(m
, priv
.Primes
[0])
533 m
.Mul(m
, priv
.Primes
[1])
536 for i
, values
:= range priv
.Precomputed
.CRTValues
{
537 prime
:= priv
.Primes
[2+i
]
538 m2
.Exp(c
, values
.Exp
, prime
)
540 m2
.Mul(m2
, values
.Coeff
)
559 func decryptAndCheck(random io
.Reader
, priv
*PrivateKey
, c
*big
.Int
) (m
*big
.Int
, err error
) {
560 m
, err
= decrypt(random
, priv
, c
)
565 // In order to defend against errors in the CRT computation, m^e is
566 // calculated, which should match the original ciphertext.
567 check
:= encrypt(new(big
.Int
), &priv
.PublicKey
, m
)
568 if c
.Cmp(check
) != 0 {
569 return nil, errors
.New("rsa: internal error")
574 // DecryptOAEP decrypts ciphertext using RSA-OAEP.
576 // OAEP is parameterised by a hash function that is used as a random oracle.
577 // Encryption and decryption of a given message must use the same hash function
578 // and sha256.New() is a reasonable choice.
580 // The random parameter, if not nil, is used to blind the private-key operation
581 // and avoid timing side-channel attacks. Blinding is purely internal to this
582 // function – the random data need not match that used when encrypting.
584 // The label parameter must match the value given when encrypting. See
585 // EncryptOAEP for details.
586 func DecryptOAEP(hash hash
.Hash
, random io
.Reader
, priv
*PrivateKey
, ciphertext
[]byte, label
[]byte) ([]byte, error
) {
587 if err
:= checkPub(&priv
.PublicKey
); err
!= nil {
590 k
:= (priv
.N
.BitLen() + 7) / 8
591 if len(ciphertext
) > k ||
592 k
< hash
.Size()*2+2 {
593 return nil, ErrDecryption
596 c
:= new(big
.Int
).SetBytes(ciphertext
)
598 m
, err
:= decrypt(random
, priv
, c
)
604 lHash
:= hash
.Sum(nil)
607 // Converting the plaintext number to bytes will strip any
608 // leading zeros so we may have to left pad. We do this unconditionally
609 // to avoid leaking timing information. (Although we still probably
610 // leak the number of leading zeros. It's not clear that we can do
611 // anything about this.)
612 em
:= leftPad(m
.Bytes(), k
)
614 firstByteIsZero
:= subtle
.ConstantTimeByteEq(em
[0], 0)
616 seed
:= em
[1 : hash
.Size()+1]
617 db
:= em
[hash
.Size()+1:]
619 mgf1XOR(seed
, hash
, db
)
620 mgf1XOR(db
, hash
, seed
)
622 lHash2
:= db
[0:hash
.Size()]
624 // We have to validate the plaintext in constant time in order to avoid
625 // attacks like: J. Manger. A Chosen Ciphertext Attack on RSA Optimal
626 // Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1
627 // v2.0. In J. Kilian, editor, Advances in Cryptology.
628 lHash2Good
:= subtle
.ConstantTimeCompare(lHash
, lHash2
)
630 // The remainder of the plaintext must be zero or more 0x00, followed
631 // by 0x01, followed by the message.
632 // lookingForIndex: 1 iff we are still looking for the 0x01
633 // index: the offset of the first 0x01 byte
634 // invalid: 1 iff we saw a non-zero byte before the 0x01.
635 var lookingForIndex
, index
, invalid
int
637 rest
:= db
[hash
.Size():]
639 for i
:= 0; i
< len(rest
); i
++ {
640 equals0
:= subtle
.ConstantTimeByteEq(rest
[i
], 0)
641 equals1
:= subtle
.ConstantTimeByteEq(rest
[i
], 1)
642 index
= subtle
.ConstantTimeSelect(lookingForIndex
&equals1
, i
, index
)
643 lookingForIndex
= subtle
.ConstantTimeSelect(equals1
, 0, lookingForIndex
)
644 invalid
= subtle
.ConstantTimeSelect(lookingForIndex
&^equals0
, 1, invalid
)
647 if firstByteIsZero
&lHash2Good
&^invalid
&^lookingForIndex
!= 1 {
648 return nil, ErrDecryption
651 return rest
[index
+1:], nil
654 // leftPad returns a new slice of length size. The contents of input are right
655 // aligned in the new slice.
656 func leftPad(input
[]byte, size
int) (out
[]byte) {
661 out
= make([]byte, size
)
662 copy(out
[len(out
)-n
:], input
)