-3
$\begingroup$

Why plain RSA encryption does not achieve CPA-security?

$\endgroup$
3
$\begingroup$

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:

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.

$\endgroup$
  • $\begingroup$ Note that deterministic encryption schemes are not CPA-secure in the private-key setting as well; in that case the adversary is given an encryption oracle. $\endgroup$ – fkraiem May 18 '17 at 11:30
  • $\begingroup$ The link you give is about indistinguishability, not CPA security; the two are equivalent only in the public-key model. $\endgroup$ – fkraiem May 18 '17 at 11:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.