0
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

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$.
$\endgroup$
2
  • $\begingroup$ I might be missing something but what makes $ 0 <= Y < n $ hold? $\endgroup$
    – Essam
    Commented May 11, 2022 at 7:46
  • $\begingroup$ @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. $\endgroup$
    – fgrieu
    Commented May 11, 2022 at 8:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.