We could perform a #CCA on El Gamal Encryption# with the following steps assuming that we have the ciphertext \(C = (c_1, c_2)\):
- Generate a random number \(r\)
- Compute \(c_2' = rc_2 \mod p\), which will be used as part of the chosen ciphertext
- Submit the chosen ciphertext \((c_1, c_2')\) where we will receive \(M' = rM \mod p\) (proof shown below)
- Deduce \(M\) with the formula \(M = M'r^{-1} = Mrr^{-1} \mod p\)
Prove \(M' = rM \mod p\):
$$ \begin{aligned} M' &= \frac{c_2'}{c_1^x}\\ &= \frac{rc_2}{c_1^x}\\ &= \frac{rMy^k}{g^{kx}}\\ &= \frac{rMy^k}{y^{k}}\\ &= rM \mod p \end{aligned} $$
Note: We know that \(c_2 = My^k \mod p\) and \(c_1 = g^k \mod p\) from El Gamal’s encryption algorithm and \(y = g^x \mod p\) from key generation part.