Why does adding PKCS#1 v1.5 padding make RSA encryption non-deterministic?

Question

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:
    public_key = RSA.importKey(public_key_file.read())

message = b'hi'

print("Encrypting without padding:")
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:
14cdd5f88f2858aca9e12b3a282783e80e2cc3aff70c1afe2e71e107a0528f4b5feba278175c6ed32300c4fa916d033de55c4b43d1254012f94ced05763bc87475395a04a50f7bf18b4a6f4cc711a07e5447a1470f24d22bc6c01d9ed03b26d151cd4fa6d7999ee14ef50f550b3cd39ac2be7b7f22408bcc7592de437796bf147174c097f5e3237aeaae17ec994a5d370e06301389b31cca3542e19b182df58aab5c74401da11eafb57f9beca920dca7acee556e26b133f945c7477745b5f29f7fd77fc624faa7e2db3a6d43d806cc5918b54e68094becb5b57a18530c955d354869a446441391bdca142aa035addb2e2303a2dc776ce40ba4eb44ff21033951
14cdd5f88f2858aca9e12b3a282783e80e2cc3aff70c1afe2e71e107a0528f4b5feba278175c6ed32300c4fa916d033de55c4b43d1254012f94ced05763bc87475395a04a50f7bf18b4a6f4cc711a07e5447a1470f24d22bc6c01d9ed03b26d151cd4fa6d7999ee14ef50f550b3cd39ac2be7b7f22408bcc7592de437796bf147174c097f5e3237aeaae17ec994a5d370e06301389b31cca3542e19b182df58aab5c74401da11eafb57f9beca920dca7acee556e26b133f945c7477745b5f29f7fd77fc624faa7e2db3a6d43d806cc5918b54e68094becb5b57a18530c955d354869a446441391bdca142aa035addb2e2303a2dc776ce40ba4eb44ff21033951
14cdd5f88f2858aca9e12b3a282783e80e2cc3aff70c1afe2e71e107a0528f4b5feba278175c6ed32300c4fa916d033de55c4b43d1254012f94ced05763bc87475395a04a50f7bf18b4a6f4cc711a07e5447a1470f24d22bc6c01d9ed03b26d151cd4fa6d7999ee14ef50f550b3cd39ac2be7b7f22408bcc7592de437796bf147174c097f5e3237aeaae17ec994a5d370e06301389b31cca3542e19b182df58aab5c74401da11eafb57f9beca920dca7acee556e26b133f945c7477745b5f29f7fd77fc624faa7e2db3a6d43d806cc5918b54e68094becb5b57a18530c955d354869a446441391bdca142aa035addb2e2303a2dc776ce40ba4eb44ff21033951

Encrypting with PKCS1#v1.5
1c5fb53f2814b2521b89bc6051c82c145ff5141c2cd3e2e76a9072d24b54940157283a0d897621aaef9aa1f315f3cec574616cdb00ce5c999eb7cb47bc65af3650af22f94322e930ce3f95829f50aa980293ee2a1eb225812b89ffb552283fb6649b07b14b6c2903cdd30ea5e91b7aef15aba11b9caf588c6150639718afd9a4c176f2a6221ce84db437a697b3ae6cde54dc272ac5363357f4ba8122d347b241636563e9a948aad8d016b03f03bfc17e6634cc7436f46751619227821089fb0245b444e58e6723f30e73f9ac9095d3f014a3c6aaaf95069159efff3e59ef21cc0f35601df3cac0551da6a62213f4cefff8ef7b4d8b6e40ca4e4a05975203c233
b5cc3075a7e604bbf1d6fdddf33b5f59d778066cb45d37faef5bb3853f9b78d9222c77ba483e6b90bab81ead44504b6b61535eb6f2f3aebfb6f9a350cc87a095337a678d6f088c87d95fd27f4f2fb1f5e2ee4ad46afa8b78a4e5aceb33e7fd7a42df0ce458478be8ecca81b432eb690de68041d9126bbcb6881c016e49b844400930fd41fb96235588f038cbb4ef858082b053496c9dd4bd67ac23197e170189198c2c228c89c9ba016a5da78f7451a1e134cd33de3507b2bcd0c4f7480afc735e265da8f95674710725b5bbb6ac550d0e13e8724b0fcf624b7d6f001ca68a5be6841dab06cfc905340afab10a925813e20c7230592d182fd3ccfd319739da59
710b7690cd3c682aceb125561ab826188add17ea6cb714831ad4f749d6d2b9573635cb4c5fc79990653216db99cc13fc1bb8cbe7f966718462d4e11a8d124b4745355eba34e6bf5674b7e2ee9b2c1d855edc086bfe629b13f5cf38b6a4c2fc3739a12e5cea6269f7f2b9e8c1cea0e9c380bba196c5f797a3dec3f11123796193755497c6448c9c495f2599feb9ec75c2bf2564d3e0683bebe101f8baa687f6a8da1934b0f0de48ec79d62693bffe9f8befc39dcfd833b8311eb3866da40a245553a2840de036a9ed5c19353af97ccd191392f6292e9f0ebe3cf6e9c5de5ed9d8f32ffc26cd136e0e36e1d76cac842880d28a997ce3dac415a47416c8a38be438

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?

Answer 1

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.

Answer 2

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.