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

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.


Comparing the two directly is a little like comparing a tractor to a train - they're both vehicles but have completely different function and construction.

RSA is an asymmetric cipher. It is ideal for secure exchange of messages across an untrusted network, because the public key can be known by everyone - a message encrypted with the public key can only be decrypted by the private key. As such, if two parties know each other's public keys, they can exchange messages securely. This means that no secret information has to be transmitted - as long as authenticity and integrity are maintained you're safe. Thankfully, RSA provides a method of generating signatures on data, which help prove that it is authentic. Given a message signed by a private key, it is possible to verify that signature using the corresponding public key.

As a rule of thumb, you can only encrypt data as large as the RSA key length. So, if you've got a 4096-bit RSA key, you can only encrypt messages up to 4096 bits long. Not only that, but it's incredibly slow. RSA isn't designed as a full-speed data transport cipher.

AES is a symmetric block cipher, and is incredibly fast. The plaintext is split into chunks called blocks, and each block is encrypted in a chain. There are different ways of doing this, but a common one is called Cipher Block Chaining, or CBC for short. This allows for theoretically infinite message sizes. However, symmetric ciphers like AES require a secret key to be exchanged first. Unlike RSA, the shared key must remain unknown to attackers, so you have to provide authenticity, integrity, and secrecy. That's difficult to do directly.

What you'll tend to find is that both schemes are implemented together, such that RSA is used to exchange the key for a block cipher like AES:

  1. Alice and Bob know each other's RSA public keys. In general these are exchanged out-of-band, e.g. via a certificate being deployed as part of your operating system.
  2. Alice picks a random 256-bit key for AES, and encrypts that key with Bob's public key. She signs this message with her private key, and sends it to Bob.
  3. Bob uses Alice's public key to verify the signature. He then uses his private key to decrypt the message.
  4. Eve (an eavesdropper) has seen the encrypted message, but cannot decrypt it without knowing Bob's private key. She also cannot alter the message, since it would render the signature incorrect. She cannot re-generate a valid signature without knowing Alice's private key.
  5. Alice and Bob now share a secret 256-bit key, and use that to encrypt messages using a symmetric cipher, such as AES.

This satisfies a few requirements:

  • The conversation can occur over an untrusted network without an attacker being able to read the messages.
  • The session key exchange can be done in a safe manner, i.e. authenticity and integrity are maintained on the key.
  • Performance of encryption and decryption for the actual conversation data is very good.

In terms of level of security, it doesn't really make much sense to compare RSA and AES. They do different jobs. We currently assume that 128-bit AES keys are safe, and that 2048-bit RSA keys are safe, but this is entirely dependant on individual security requirements. Using 256-bit AES and 4096-bit RSA keys should be more than enough for the next decade, assuming the implementation is sound.

Note that all of this is a simplification, as there are many caveats and details involved, and describing and RSA exchange as "encryption" isn't strictly correct, but all in all this should be a reasonable high-level overview of the way the two types of crypto work.


According to the GoLang crypto package "The message must be no longer than the length of the public modulus minus 11 bytes". http://golang.org/pkg/crypto/rsa/#EncryptPKCS1v15

Tags:

Aes

Rsa