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

  • Thread starter Thread starter Leo Liu
  • Start date Start date
  • Tags Tags
    Encryption Proof
Click For Summary
The discussion centers on a specific step in the RSA encryption proof, particularly focusing on the implications of equation 5 from the referenced paper. It clarifies that the relationship \( ed \equiv 1 \mod \phi(n) \) leads to the conclusion that \( \phi(n) \) divides \( ed - 1 \). This division implies that there exists an integer \( k \) such that \( ed \) can be expressed as \( \phi(n) \cdot k + 1 \). Consequently, this formulation allows for the equivalence \( M^{\phi(n) \cdot k + 1} = M^{ed} \). Understanding this step is crucial for grasping the foundational principles of RSA encryption.
Leo Liu
Messages
353
Reaction score
156
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.
 
Mathematics news on Phys.org
It should be evident from equation 5
 
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:

Similar threads

Replies
1
Views
1K
  • · Replies 7 ·
Replies
7
Views
2K
  • · Replies 3 ·
Replies
3
Views
3K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 4 ·
Replies
4
Views
1K
Replies
2
Views
3K
  • · Replies 13 ·
Replies
13
Views
2K
  • · Replies 22 ·
Replies
22
Views
3K
  • · Replies 14 ·
Replies
14
Views
2K
  • · Replies 9 ·
Replies
9
Views
2K