How to prove that RSA is not IND-CCA2?

Question

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?

Answer 1

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\}$.

2. $\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$

3. $\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).

4. $\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!