A question about a small step in the proof of RSA encryption

  • I
  • Thread starter Leo Liu
  • Start date
  • #1
Leo Liu
345
146
1638205070973.png

From the paper https://people.csail.mit.edu/rivest/Rsapaper.pdf
Can someone explain the green highlight to me please? Sorry that I can't type much because this is the final week. Thanks.
 

Answers and Replies

  • #2
Gaussian97
Homework Helper
679
405
It should be evident from equation 5
 
  • #3
fresh_42
Mentor
Insights Author
2022 Award
17,645
18,322
From ##(5)## we have
\begin{align*}
ed\equiv 1 \mod \phi(n) &\Longleftrightarrow \phi(n)\,|\,(ed-1) \\
&\Longleftrightarrow \phi(n)\cdot k = ed-1 \text{ for some } k \in \mathbb{Z}\\
&\Longleftrightarrow \phi(n)\cdot k +1 = ed \text{ for some } k \in \mathbb{Z}\\
&\Longrightarrow M^{\phi(n)\cdot k +1} =M^{ed}
\end{align*}
 
Last edited:

Suggested for: A question about a small step in the proof of RSA encryption

  • Last Post
Replies
2
Views
180
  • Last Post
Replies
3
Views
487
Replies
8
Views
740
  • Last Post
Replies
2
Views
334
Replies
3
Views
39
  • Last Post
Replies
22
Views
931
  • Last Post
Replies
12
Views
477
Replies
1
Views
475
Replies
3
Views
295
Top