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?
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ 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. $\endgroup$ – fgrieu♦ May 23 '20 at 10:10
Add a comment
|
$\begingroup$
$\endgroup$
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:
- $\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\}$.
- $\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$
$\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).
$\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!
