RSA maximum bytes to encrypt, comparison to AES in terms of security?

  • What is the maximum number of bytes for encrypting a plaintext message using RSA that is reasonably secure and also efficient and would AES be better for the same size in bytes? The encryption doesn't have to be public by the way, I'm just wondering if AES is just as good on a short message as it is on a large document. Basically the message or document would be sent encrypted but the key would never be made public. I guess that would also defeat the purpose of RSA but I've read a few times online that RSA is good for short messages and AES is good for long ones.

  • RSA, as defined by PKCS#1, encrypts "messages" of limited size. With the commonly used "v1.5 padding" and a 2048-bit RSA key, the maximum size of data which can be encrypted with RSA is 245 bytes. No more.

    When you "encrypt data with RSA", in practice, you are actually encrypting a random symmetric key with RSA, and then encrypt the data with a symmetric encryption algorithm, which is not limited in size. This is how it works in SSL, S/MIME, OpenPGP... Regularly, some people suggest doing "RSA only" by splitting the input message into 245-byte chunks and encrypting each of them more or less separately. This is a bad idea because:

    • There can be substantial weaknesses in how the data is split and then rebuilt. There is no well-studied standard for that.
    • Each chunk, when encrypted, grows a bit (with a 2048-bit key, the 245 bytes of data become 256 bytes); when processing large amounts of data, the size overhead becomes significant.
    • Decryption of a large message may become intolerably expensive.

    When encrypting data with a symmetric block cipher, which uses blocks of n bits, some security concerns begin to appear when the amount of data encrypted with a single key comes close to 2n/2 blocks, i.e. n*2n/2 bits. With AES, n = 128 (AES-128, AES-192 and AES-256 all use 128-bit blocks). This means a limit of more than 250 millions of terabytes, which is sufficiently large not to be a problem. That's precisely why AES was defined with 128-bit blocks, instead of the more common (at that time) 64-bit blocks: so that data size is practically unlimited.

    "There can be substantial weaknesses in how the data is split and then rebuilt." -Can you please elaborate? An example would be good.

    I wouldn't use n*2^(n/2) bits in any sort of recommendation. Once you reach that number of bits the probability of a collision will grow quickly and you will be way over 50% probability of a collision by the time you reach 2*n*2^(n/2) bits. In order to keep the probability of a collision negligible I recommend encrypting no more than n*2^(n/4) bits with the same key. In the case of AES that works out to 64GB.

    @kasperd to be clear is that a single key, or a single key/iv pair? In other words, can I safely encrypt 256GB by splitting into 4 chunks, with a single key, and 4 IVs?

License under CC-BY-SA with attribution

Content dated before 7/24/2021 11:53 AM