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

  • Context: Undergrad 
  • Thread starter Thread starter Leo Liu
  • Start date Start date
  • Tags Tags
    Encryption Proof
Click For Summary
SUMMARY

The discussion centers on a specific step in the proof of RSA encryption as outlined in the paper by Rivest et al. The highlighted section refers to the equivalence of \( ed \equiv 1 \mod \phi(n) \), demonstrating that \( \phi(n) \) divides \( ed - 1 \). This leads to the conclusion that \( M^{\phi(n) \cdot k + 1} = M^{ed} \) for some integer \( k \), establishing a critical relationship in the RSA algorithm's mathematical foundation.

PREREQUISITES
  • Understanding of RSA encryption principles
  • Familiarity with modular arithmetic
  • Knowledge of Euler's totient function, \( \phi(n) \)
  • Basic grasp of integer properties and proofs
NEXT STEPS
  • Study the mathematical foundations of RSA encryption
  • Learn about modular exponentiation techniques
  • Explore the implications of Euler's theorem in cryptography
  • Review the complete RSA algorithm implementation
USEFUL FOR

Cryptography students, mathematicians, and software developers interested in secure communication protocols will benefit from this discussion.

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
 
Reply
  • Like
Likes   Reactions: mfb
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:
Reply
  • Like
Likes   Reactions: Leo Liu

Similar threads

High School How do mathematicians come up with new proofs?
  • · Replies 4 ·
Replies
4
Views
2K
Suggestions for HS geometry book (proofs)
  • · Replies 14 ·
Replies
14
Views
3K
Undergrad Questions regarding Kurepa's Conjecture
  • · Replies 1 ·
Replies
1
Views
2K
Graduate How did Saccheri prove Euclid's Fifth Postulate?
  • · Replies 6 ·
Replies
6
Views
3K
Graduate Shinichi Mochizuki's ABC Conjecture and Replication Crisis in Maths
  • · Replies 33 ·
2
Replies
33
Views
8K
Undergrad Questions about non existence of GCDs vs (coimages, cokernels)
  • · Replies 12 ·
Replies
12
Views
826
Undergrad Video on imaginary numbers and some queries
  • · Replies 3 ·
Replies
3
Views
2K
Graduate Question about proof of Great Picard Theorem
  • · Replies 3 ·
Replies
3
Views
3K
The angle of tilt of a gyroscope
  • · Replies 9 ·
Replies
9
Views
2K
Undergrad Question about Cantor's Diagonal Proof
  • · Replies 22 ·
Replies
22
Views
4K