Breaking RSA if you know m^k = 1 mod n

  • Context: Graduate 
  • Thread starter Thread starter nudan
  • Start date Start date
Click For Summary
SUMMARY

The discussion centers on the mathematical foundations of RSA encryption, specifically the relationship between the private key (d, n) and the public key (e, n). It emphasizes that d and e are exponential inverses modulo n, and if x^d or x^e are congruent to 1, then d equals phi(n) or e equals phi(n) respectively. The conversation highlights the importance of understanding modular arithmetic and Euler's Theorem, which underpins the security of RSA by ensuring careful key selection.

PREREQUISITES
  • Modular arithmetic fundamentals
  • Understanding of RSA encryption
  • Knowledge of Euler's Theorem
  • Fermat's Little Theorem
NEXT STEPS
  • Study modular arithmetic in depth
  • Explore RSA key generation techniques
  • Learn about Euler's Theorem applications in cryptography
  • Investigate the implications of Fermat's Little Theorem on RSA security
USEFUL FOR

Cryptographers, security researchers, and anyone interested in the mathematical principles behind RSA encryption and its vulnerabilities.

nudan
Messages
1
Reaction score
0
Hello I'm looking for some guidance:
 
Last edited:
Physics news on Phys.org
You seem to assume that everyone knows what you are talking about--why?

You certainly have not defined terms, but when I look into this, it is my impression that you have no understanding of modular arithmetic. Why not check that out?
 
Look, RSA is built on the fact in the private key (d,n) and the public key (e,n) d and e are exponential inverses of each other mod n. If x^d or x^e are congruent to 1 then d = phi(n) or e = phi(n) respectively... Take a look at Euler's Theorem which is a generalize form of Fermat's Little Theorem. This is why in RSA there is so much care taken in picking keys.
 

Similar threads

Undergrad What is the size of the quotient group L/pZ^m?
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad How Do Properties of Modulus Algebra Apply to RSA and Diffie-Hellman?
  • · Replies 12 ·
Replies
12
Views
3K
Undergrad ##(p^k -1) \equiv X \mbox{(mod p)}## via Wilson's theorem
  • · Replies 2 ·
Replies
2
Views
1K
Comp Sci RSA to encrypt English Alphabets, any restrictions?
  • · Replies 7 ·
Replies
7
Views
2K
Undergrad How Does the Equation D x E mod Φ(N) = 1 Relate to RSA Encryption?
  • · Replies 1 ·
Replies
1
Views
1K
Graduate Coefficients of Chebyshev polynomials
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad ##S_{n}(\alpha)=\sum_{k=1}^{n} (-1)^{\lfloor{k\alpha\rfloor}}##
  • · Replies 2 ·
Replies
2
Views
1K
MHB Why do we get like that the message?
  • · Replies 2 ·
Replies
2
Views
1K
Graduate Decrypting RSA: Using d_K, d_p, d_q, M_p, M_q and x_p,x_q to Prove y^d=x mod n
  • · Replies 1 ·
Replies
1
Views
3K
Graduate When n*(n+1)/2 - k is never a square
  • · Replies 2 ·
Replies
2
Views
2K