# 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$$ 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. Apr 27, 2022 at 0:12
• The last step of $X = \cdots$ 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? 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
May 11, 2022 at 8:22