Proving that RSA CCA is possible

Question

I'm reading from William Stalling's Cryptography & Network Security - 7th Edition

To me the first line suggests

$$(M^e\bmod n)\times(2^e\bmod n)=((2M)^e\bmod n)$$ which means that if we want to define a message $X$ such that when decrypted it gives $2M$ then we should consider $X=(M^e\bmod n)\times(2^e\bmod n)=C\times(2^e \bmod n)$

The book for some reason is however suggesting $X=(C\times2^e)\bmod n$ and I can't see that they are the same expression.

Answer 1

The author forgot a few $\bmod n$ along the way. In particular, equation 9.2 is wrong, and should be $$E(PU,M_1)\times E(PU,M_2)\bmod n=E(PU,(M_1\times M_2\bmod n))$$ Also, what follows "note that" is wrong in the first line, then when going from the second to the last line (the conclusion is correct).

This mess can be avoided by using congruence modulo $n$, an equivalence relation in $\mathbb Z$ noted $\equiv$ with$\pmod n$ at the end of the line. Recall that for $n,k\in\mathbb N^*$, $u,v\in\mathbb Z$

• the statement $u\equiv v\pmod n$ means $v-u$ is a multiple of $n$
• the statement $u=v\bmod n$ additionally means $0\le u<n$.
• it holds $$\begin{align} (u\bmod n)+v&\equiv u+v&\pmod n\\ (u\bmod n)\times v&\equiv u\times v&\pmod n\\ (u\bmod n)^k&\equiv u^k&\pmod n\\ \end{align}$$

With that $\equiv$ notation, the proof becomes:

• define $X:=C\times2^e\bmod N$ and submit this for decryption, yielding $Y:=X^d\bmod n$.
• it holds $Y\equiv X^d\equiv(C\times2^e)^d\equiv C^d\times(2^e)^d\equiv C^d\times2\pmod n$, noting that $(2^e)^d\equiv2\pmod n$ because $2$ gets encrypted and decrypted.
• since $0\le Y<n$ it holds $Y=2M\bmod n$, which lets us find $M$ from $Y$: if $Y$ is even then $M:=Y/2$, otherwise $M:=(Y+n)/2$.