In AES we use some padded bytes at end of message to fit 128/256 byte blocks. But as RSA is not a block cipher why is padding used?
Can the message size be any byte length (is the encrypting agent free to choose) or must it be a certain byte length to use RSA encryption?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
RSA without padding is also called Textbook RSA. The question why RSA without padding is insecure has already been answered in this question.
We can fix a few issues by introducing padding.
Edit: To answer the second question, RSA plain text are (unlike AES plain texts) limited by an upper bound. Messages must not be longer than the $N$ of the public key. It is also noteworthy, that common cipher schemes don't handle or pad blocks of RSA ciphertexts at all. Usually, the message is encrypted using a symmetric cipher (like AES) and only the key to this seperate cipher text is encrypted using an asymmetric cipher (like RSA). This is also called hybrid encryption.
1. Why do we use padding?
Both block ciphers and RSA are permutations on a block(RSA's block isn't an integral number of bytes), so it's clear that both of them need some kind of padding if the data size doesn't correspond to the block size.
With block ciphers the padding doesn't do much: It fills up the remainder of the block, and tells you how much padding there was.
With RSA the padding is essential for its core function. RSA has a lot of mathematical structure, which leads to weaknesses. Using correct padding prevents those weaknesses.
For example RSA Encryption padding is randomized, ensuring that encryption the same message encrypted multiple times looks different each time. It also avoids other weaknesses, such as encrypting the same message using different RSA keys leaking the message, or an attacker creating messages derived from some other ciphertexts.
RSA padding should always be used, and it has a minimum size of dozens of bytes, as opposed to a single byte with most block cipher paddings.
2. Can the message size be any byte length or must it be a certain byte length to use RSA encryption?
Using a single RSA operation you can only encrypt a small constant amount of bytes (100 or so).
In principle one could chain multiple RSA operations similar to how we chain block ciphers. In practice (almost) nobody does that. RSA is slow, decrypting perhaps 100kB/s instead of >100MB/s with AES. The padding also bloats the ciphertext unnecessarily.
What we actually do is generating a random symmetric key, and encrypting the message with that key and AES. And then we encrypt the key with RSA. This is efficient, and at least as secure as encrypting the message with RSA.
According to Wikipedia the purpose of adding random padding to the clear text before encrypting it is to prevent a successful chosen plaintext attack, from Wikipedia:
We use padding because RSA is not secure without padding. See the following research paper:
There are no particular requirements on the length of the message, except that it can't be too long. Usually, we generate a random symmetric key (e.g., an AES key), encrypt the AES key with RSA, and then encrypt the real message using AES. This way, we get past the length limits.