Score:0

Proving that RSA CCA is possible

cn flag

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

enter image description here

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.

kelalaka avatar
in flag
$$( a * b ) \bmod n = [(a \bmod n) * (b \bmod n)] \bmod n$$
Essam avatar
cn flag
Would you mind elaborating further. I can't see the extra mod on the right in any of the book's steps.
kelalaka avatar
in flag
The last step of $X = \cdots$
Score:1
ng flag

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$.
Essam avatar
cn flag
I might be missing something but what makes $ 0 <= Y < n $ hold?
fgrieu avatar
ng flag
@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.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.