# How to prove that RSA is not IND-CCA2?

RSA is homomorphic wrt multiplication and therefore it is not IND-CCA2. But how to show it. What are the steps to win IND-CCA2 game?

How is the probability of winning calculated?

• Anything unclear after pondering wikipedia's entry on IND-CCA2 at length? Also: "RSA is homomorphic" holds for textbook RSA, but not RSA encryption as practiced (e.g. RSA-OAEP). And textbook RSA is not even IND-CPA, thus considering it's IND-CCA2 security is a bit strange. The question might not be about RSA in particular. – fgrieu May 23 '20 at 10:10

## 1 Answer

yes, plain textbook RSA is only OW-CPA (not even IND-CPA).

You can construct an adversary $$\mathcal{A}$$ which wins in the IND-CCA2 game:

1. $$\mathcal{A}$$ sends $$m_0=0$$ and $$m_1=1$$ as challenge ciphertexts to be encrypted

$$\mathcal{A}$$ receives the ciphertext $$c_b = Enc(pk, m_b) = (m_b) ^ e \mod N$$ for some uniform random $$b \in \{0,1\}$$.

1. $$\mathcal{A}$$ uses the homomorphic property of RSA to obtain a ciphertext for $$2\cdot m_b$$:

$$\mathcal{A}$$ computes $$c_b' = (2^e \cdot c_b) \mod N = (2 \cdot m_b) ^ e \mod N$$

1. $$\mathcal{A}$$ sends $$c_b'$$ to the decryption oracle. and receives the decryption which is either 0 (then $$b$$ was 0) or 2 (then $$b$$ was 1).

2. $$\mathcal{A}$$ outputs $$b$$.

$$\mathcal{A}$$ can query the decryption oracle on the ciphertext $$c_b'$$ since this ciphertext wasn't received by $$\mathcal{A}$$ from the encryption oracle.

The decryption oracle doesn't do any integrity checks, so it will successfully decrypt the ciphertext.

If I didn't miss anything, the probability of $$\mathcal{A}$$ winning this game is 1.

You could also beak RSA IND-CPA security by testing which message was encrypted (by encrypting both messages yourself). This works because textbook-RSA encryption is deterministic. A scheme that isn't IND-CPA secure, can't be IND-CCA secure.

I hope I could help!