Is there a maximum number of encryptions I should make with the same RSA key?

Question

From an answer to the question RSA maximum bytes to encrypt, comparison to AES in terms of security? I learned that there is a theoretical limit of how much data can be safely encrypted with symmetric block ciphers (like AES for example) with the same key. The answer says that for a block size of n bits there are theoretical concerns when approaching 2^(n/2) encrypted blocks with the same key, and a comment suggests to use 2^(n/4) for a more defensive approach. For AES with its 16 bytes per block, both figures would be significantly more than any single AES key would ever encrypt in my application, so I needn't worry about that.

Nevertheless, even if this limitation bears no practical relevance for me and I have not understood why it exists, I still consider it "good to know" (e. g. because for other symmetric block ciphers with smaller block sizes, it might become relevant).

Hence I'm wondering: are there a similar hypothetical limitations for RSA? In other words: is there some kind of "maximum number of encryptions" I should do with the same RSA key, or is it truly infinite how many times I can encrypt something (in my case: varying 128-bit AES keys) with RSA (assuming the private key remains private forever and there's no attack found)?

Notes:

I haven't yet found anything about it, mainly because when something like this is asked, the answers tend to immediately focus on how much data can you encrypt at once, but they don't say anything about the maximum number of encryptions.

And finally, for completion's sake: I'll use RSA-2048+OAEP-SHA256, but the question is targeted towards RSA in general, for any padding algorithm, and if the answer varies by padding algorithm used, that'd be nice to know.

Answer 1

Is there a maximum number of encryptions I should make with the same RSA key?

No, at least, none that can be practically performed.

For RSA, we assume that the adversary has the public key, and hence is able to generate his own plaintext/ciphertext pairs, and in fact, can do that a huge number of times, should he find that helpful.

Hence, if RSA becomes insecure if you encrypt, say, $2^{80}$ messages, then a large adversary can go ahead and encrypt that many messages himself (and thus obtain whatever weakness that was posited.

The fact that we believe that, say, 3k RSA cannot be broken with less than $O(2^{128})$ operations would therefore say that it's safe to encrypt $2^{128}$ messages (and you'll never ever need to encrypt that many).

Answer 2

is there some kind of "maximum number of encryptions" I should do with the same RSA (public) key.

Not one worth consideration for the textbook-RSA part of RSA, because the message space [0,N) is so large when the public modulus N is large enough to be secure against factorization.

However, even when not used for hybrid encryption with AES, RSA is typically used with some kind of padding that does create a limitation. In particular, when enciphering using RSAES-PKCS1-v1_5 at its maximum message capacity (11 bytes below the byte size of the modulus), the random padding is only 8 bytes, that is 64-bit, therefore when enciphering the same message 2²⁴ times (that is <17 millions) to the same public key, there is probability about 2^2×24-64-1 = 2^-17 (that is >0.0007%, not quite negligible) that two ciphertexts are identical, which is detectable by an adversary, leaking that two identical messages have been sent. It is possible to construct use cases where that matters.

More modern RSA paddings (like RSAES-OAEP) typically use a random as wide as the hash, thus the limit is much higher and becomes practically immaterial.

---

There often are practical limits to the number of times it is safe to decipher or sign with the same RSA private key, due to side-channel attacks (timing, DPA) or (especially for decryption) padding-oracle attacks. But these are attacks against implementations, not against RSA itself. Their success or failure often depends more on the freedom the adversary has to submit queries, on how deeply s/he can observe, and on implementation/platform details, than on the number of attempts.

Answer 3

If you encrypt n messages with the same key, then the cost of cracking the key is constant, but the reward grows with n.

If you could crack a key at a cost of 100,000,000 and cracking a message is worth 10,000, you won’t try. If I encrypt 100,000 messages like that, you will crack the key.