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

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 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 3

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.

Answer 4

RSA requires padding for entirely different reasons than CBC mode encryption.

---

Block ciphers such as AES and (triple) DES can only be used to permute one block of plaintext to one block of ciphertext. This is not very useful as generally we would like to encrypt multiple messages of variable size.

Furthermore, the mode of operation needs to have some kind of initialization vector so that the resulting cipher is not deterministic. If the result is deterministic then an attacker would be able to easily test if two input messages are identical.

Only a few modes of operation for block ciphers require padding. However, the CBC mode of operation is used quite often, and requires either padding or ciphertext stealing. For block ciphers - that basically consist of bitwise operations and reordering operations - the padding is just used to fill the last block of data, preferably in such a way that the message may contain any byte value.

---

RSA is not a block cipher like DES or AES. The main RSA operation is modular exponentiation of a number. That number is a numerical representation of the input message using padding. However, not all numbers work equally well for RSA. For instance, if the number is simply zero or one then RSA would spectacularly fail. For this and many other reasons, RSA requires a padding scheme to be secure. That padding scheme needs to adhere to specific requirements to be secure; just being able to encode/decode a message to a specific size is just one of the many requirements.

Using the word padding for RSA is by now rather incorrect - it's basically still called "padding" for historical reasons. The padding schemes for RSA did simply extend the message before converting a number. But newer schemes actually alter the message itself as well; the message cannot directly be identified in the number before exponentiation by RSA. OAEP is one of the schemes where the entire message is randomly transformed before RSA modular exponentiation.

If the message is directly encrypted by RSA then yes, the message is required to be within certain limits. As modular exponentiation is used the message + padding is required to be within the limits of the modulus. The size of the message depends therefore on the modulus size as well as on the overhead introduced by the padding.

For the old, insecure (but simpler for demonstration purposes) RSA scheme using PKCS#1 v1.5 padding the maximum message size is the modulus size in bytes, minus 11 for the padding overhead. So a 2048 bit RSA key can then be used to encrypt (2048 / 8) - 11 = 245 bytes. There is no minimum, so the size of the message that can be encrypted is zero to 245 bytes.

Note that this does mean that only ~64 bits of randomness is used within the PKCS#1 v1.5 scheme; for a higher security level you'd want to have about 128 bits of randomness, which limit your messages to about 19 bytes smaller than the modulus. For the more secure OAEP, a nice table of overhead & maximum message size is displayed in this answer.

---

However, in actual operation, hybrid encryption schemes are used instead of schemes where the data is directly encrypted by RSA. In that case a symmetric cipher such as AES (with a particular mode of operation such as CBC) is used to encrypt the actual message. RSA is then used to either encrypt/decrypt the symmetric key. In that case the message size is only dependent on the mode of operation for the symmetric cipher (usually multiple gigabytes or more for AES in any mode of operation). An AES(-256) key should always easily fit into any RSA calculation for a secure size of the modulus, independent of the padding scheme used.

Another method is to use RSA KEM where no key or message is encrypted by RSA at all. RSA KEM is used to derive a symmetric key for hybrid encryption instead.

Answer 5

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.