I'm quite a beginner to cryptography, but have been implementing some encryption according to a specification over the last few weeks using the PyCrypto library.

I've discovered that when encrypting using RSA public keys alone, encryption appears to be deterministic (meaning encrypting the same message multiple times results in the same cipher text). However, once I add PKCS#1 v1.5 padding, it becomes non-deterministic (the cipher text differs on subsequent encryptions).

This is demonstrated in the following Python3/PyCrypto code:

import os

from Crypto.Cipher import PKCS1_v1_5
from Crypto.PublicKey import RSA

with open(os.path.expanduser('~/.ssh/id_rsa.pub')) as public_key_file:

message = b'hi'

print(public_key.encrypt(message, None)[0].hex())
print(public_key.encrypt(message, None)[0].hex())
print(public_key.encrypt(message, None)[0].hex())

cipher = PKCS1_v1_5.new(public_key)

print("Encrypting with PKCS1#v1.5")
print(cipher.encrypt(message).hex())
print(cipher.encrypt(message).hex())
print(cipher.encrypt(message).hex())


Which outputs the following:

Encrypting without padding:

Encrypting with PKCS1#v1.5


My question is: why are there differences in determinism in these two cases? I understand why non-determinism in encryption is useful (to prevent an interceptor noticing two messages are the same), but why does RSA encryption alone not offer this, and how does padding add this? Is this one of the purposes of padding?

When you use textbook RSA, the public key is $$(e,N)$$ and the ciphertext of a message $$m$$ is $$c = m^e\bmod N$$. The encryption process of textbook RSA involves no randomness; this causes the problem.

It is easy to see that when having $$m_1=m_2$$ the ciphertexts of them $$m_1^e =m_2^e \bmod N$$. Deterministic encryption is not CPA-secure.

When using a Padding scheme like PKCS#1 v1.5, one important aspect is that the padding is random, thus differs each time when you encrypt.

In PKCS#1 v1.5 for RSA, $$m$$ is padded to $$x=0\text{x}00||0\text{x}02||r||0\text{x}00||m$$ and the ciphertext is $$c=x^e\bmod N$$ instead of $$m^e\bmod N$$. Here $$r$$ is a long enough random string. Therefore, even having $$m_1=m_2$$, the ciphertexts of them will be produced over $$x_1\ne x_2$$, thus will looks totally different.

Of course, the length of $$r$$ is very important, if it is too short, then there won't be enough randomness and attacks are still possible. In the standard, it rules that

• Let $$N$$ be $$k$$ bytes long, then $$m$$ must be $$\leq$$ $$k-11$$ bytes long.
• The padded string ($$x$$) must be $$k$$ bytes long.

Thus $$r$$ is of $$k-3-|m|$$ bytes long ($$|m|$$ is how many bytes the plaintext $$m$$ is), which is at least 8 bytes long. However, this may still not be enough. I remember in Kats & Lindell's book, it mentions that $$r$$ needs to be roughly half the length of $$N$$, in order for us to consider RSA CPA secure.

• Katz and Lindell do not state that "$r$ needs to be roughly half the length of $N$" for security They say that it is believed sufficient, not that it's believed necessary.
– fgrieu
Commented Jul 10, 2023 at 9:16

It is nice that you have tested if from the first hands.

The textbook RSA encryption is deterministic in the sense that given a public key $$(e,n)$$ and two plaintext $$0 \leq m_1,m_2 < n$$ if

$$c_1=\operatorname{Enc}_{k_{pub}}(m_1)$$ $$c_2 = \operatorname{Enc}_{k_{pub}}(m_2)$$

than $$c_1 = c_2 \text{ iff } m_1 =m_2.$$

We already say that textbook RSA insecure since:

1. The encryption of same messages have the same ciphertext
2. The encrypted message is malleable that is

$$\operatorname{Enc}_{k_{pub}}(2) \cdot c = \operatorname{Enc}_{k_{pub}}(2) \cdot \operatorname{Enc}_{k_{pub}}(m) = \operatorname{Enc}_{k_{pub}}(2\cdot m)$$

So, an attacker can modify the ciphertext and create valid plaintexts.

In order to prevent these, a padding scheme is necessary. Insert randomness to prevent 1 and format the data in order to see the modification in the ciphertext.

• The homomorphic example should be $Enc_{pk}(2)\cdot c = Enc_{pk}(2\cdot m)$. Commented Jan 16, 2019 at 12:58