Undergrad 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:
Here is a little puzzle from the book 100 Geometric Games by Pierre Berloquin. The side of a small square is one meter long and the side of a larger square one and a half meters long. One vertex of the large square is at the center of the small square. The side of the large square cuts two sides of the small square into one- third parts and two-thirds parts. What is the area where the squares overlap?

Similar threads

  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 14 ·
Replies
14
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 33 ·
2
Replies
33
Views
7K
  • · Replies 6 ·
Replies
6
Views
3K
  • · Replies 10 ·
Replies
10
Views
2K
  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 3 ·
Replies
3
Views
3K
  • · Replies 9 ·
Replies
9
Views
2K
  • · Replies 5 ·
Replies
5
Views
767