We can take advantage of the multiplicative nature of #Rivest-Shamir-Adleman (RSA) and utilise it in our attempts to carry out #CCA. The multiplicative properties of RSA is stated below:
- Let \(C_1 = M_1^e \mod n\) and \(C_2 = M_2^e \mod n\) then \(C_1 C_2 = (M_1 M_2)^e \mod n\).
The steps to carry out a CCA is as follows:
- Generate random \(r\) from \(Z_n^*\)
- Compute the chosen ciphertext \(C' = Cr^e \mod n\)
- Submit \(C'\) and get back \(M' = C'^d \mod n = Mr \mod n\) (proof is shown below)
- Deduce \(M\) with \((Mr)r^{-1} \mod n\) (proof is shown below)
Prove \(M' = Mr \mod n\):
$$ \begin{aligned} C' &= (C \mod n) (r^e \mod n)\\ &= (M^e \mod n) (r^e \mod n)\\ &= (Mr)^e \mod n\\\\ M' &= C'^d \mod n\\ &= (Mr)^{ed} \mod n\\ &= Mr \mod n \end{aligned} $$
Note: \(C = M^e \mod n\) is from basic #Rivest-Shamir-Adleman (RSA) encryption formula.
Note: \(ed = 1\) due to \(de = 1 + k \phi(n)\) (Modular Arithmetic#) and \(M^{\phi(n)} \mod n = 1\) (Euler’s Theorem#). Full proof is shown in #Rivest-Shamir-Adleman (RSA).
Prove \(M = (Mr)r^{-1} \mod n\):
$$ \begin{aligned} M' &= Mr \mod n\\ M'r^{-1} &= M \mod n\\ M &= M'r^{-1} \mod n\\ &\text{Substitute } M'\\ M &= (Mr)r^{-1} \mod n \end{aligned} $$
The attack can be countered by random padding of plaintext or use Optimal Asymmetric Encryption Padding (OAEP).