Why plain RSA encryption does not achieve CPA-security?

Question

Why plain RSA encryption does not achieve CPA-security?

Answer 1

Plain "textbook" RSA is not CPA-secure because it is deterministic: encrypting the same plaintext always yields the same ciphertext.

In the IND-CPA security game, the attacker gets to choose two different plaintext messages to be encrypted, receives one of them back encrypted, and needs to guess which one it is. If the attacker can do that with a probability significantly higher than $\frac12$, we say that the encryption system is not CPA-secure.

Because textbook RSA is deterministic, and because it's a public-key encryption system (meaning that everybody, including the attacker, can be assumed to know the public key and be able to encrypt messages), winning the IND-CPA game against textbook RSA is trivial:

1. Choose two distinct plaintext messages (say, $A$ and $B$) and submit them to the challenger.
2. Receive an encrypted ciphertext $c$ from the challenger.
3. Using the public key, encrypt $A$ and $B$ to obtain $c_A = E_{k_{pub}}(A)$ and $c_B = E_{k_{pub}}(B)$.
4. Check which of $c_A$ and $c_B$ is equal to $c$. Since the encryption scheme is deterministic, one of them should be.

To make RSA secure against such attacks, we need to pad the plaintext with random bits before encryption so that, when the attacker re-encrypts the same plaintext again, they won't get the same ciphertext that the challenger gave them. Properly constructed RSA padding (such as OAEP) does this, and more generally (pseudo-)randomizes the plaintext in such a way that what actually gets encrypted by the "textbook" part of RSA looks effectively like a random number, thereby defeating both this and various other attacks on textbook RSA.

---

Ps. Several questions similar to yours have been asked here before, such as:

• Chosen plaintext attack on textbook RSA decryption and
• How does a chosen plaintext attack on RSA work?

However, the first linked question seems to be mistitled, as it actually seems to be asking about a chosen ciphertext attack on textbook RSA, and the accepted answer to the second one also brushes off the CPA case as uninteresting, before proceeding to discuss a CCA attack on textbook RSA. Thus, I thought it reasonable to actually try and provide a clear answer to this basic question here.