# Proving that RSA CCA is possible

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.

• $$( a * b ) \bmod n = [(a \bmod n) * (b \bmod n)] \bmod n$$ Commented Apr 26, 2022 at 22:54
• Would you mind elaborating further. I can't see the extra mod on the right in any of the book's steps. Commented Apr 27, 2022 at 0:12
• The last step of $X = \cdots$ Commented Apr 27, 2022 at 0:16

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.
• 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 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$$.
• I might be missing something but what makes $0 <= Y < n$ hold? Commented May 11, 2022 at 7:46
• @Essam: by construction of $Y$ by textbook RSA decryption, $Y=X^d\bmod n$. This implies $0\le Y<n$ by definition of$\bmod$when that's a binary operator (that is when there is no opening parenthesis immediately on the left of$\bmod$and proper notation is used). See second bullet point in the answer.
– fgrieu
Commented May 11, 2022 at 8:22