Why is padding used for RSA encryption given that it is not a block cipher?

Question

1. 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?

2. 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?

Answer 1

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.

1. Malleability: If we have a strict format for messages, i.e. that the first or last bytes contain a specific value, simply multiplying both message and ciphertext will decrease the probability of creating a valid (in terms of padding) message.

2. Semantical Security: Add randomness such that RSA is not deterministic anymore (a deterministic encryption scheme yields always the same $x$ for each instance of $x = enc_{pubkey}(m)$ for constant $m$ and $pubkey$). See OAEP as an example on how to achieve this.

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.

Answer 2

We use padding because RSA is not secure without padding. See the following research paper:

• Why Textbook ElGamal and RSA Encryption are Insecure, Dan Boneh, Antoine Joux, Phong Nguyen, ASIACRYPT 2000.

See also:

• Attacks against plain RSA

• Padding schemes

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.

Answer 3

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.

Answer 4

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:

Because RSA encryption is a deterministic encryption algorithm (i.e., has no random component) an attacker can successfully launch a chosen plaintext attack against the cryptosystem, by encrypting likely plaintexts under the public key and test if they are equal to the ciphertext. A cryptosystem is called semantically secure if an attacker cannot distinguish two encryptions from each other even if the attacker knows (or has chosen) the corresponding plaintexts. As described above, RSA without padding is not semantically secure.

See Attacks against plain RSA and Padding schemes for more detail.