After numerous attempts from myself and all of you guys, I finally came to understand RSA. I can now prove it and understand how I got there. But I still have some very few polishing questions.

1) We generate the keys by doing ed = 1 mod Phi. So when mathematically stating the equation, we know, that M^ed = M Mod N. We also know that M when coprime to N, we have M^Phi + 1 = M (mod N) (ommiting the k). I am a bit confused about the relation between [Phi + 1 and ED mod Phi.] If somebody could help me with that.

2) Lastly the equation works like Fermat's little theorem. When a and p are co primes, a^p = a mod p, which in this case is m^phi + 1 = m mod N, and Fermat's also says that a^p-1 = 1 mod p, but for the second part, when we use m as of the invertible elements of the group U(N), the answer does come 1, but for any element m, the solution to m^phi mod N, is not 1. So a part of Fermat's LT, is applying here as I see. If someone clears me on that part. Thanks...

  • $\begingroup$ Euler's Theorem! $\endgroup$ – kelalaka Mar 14 at 7:03
  • $\begingroup$ Thats not the answer :-) I have studied Euler's, Fermat's, Lagrange's, Groups, Rings, and mathematically can prove RSA no problem. What I want is a visual representation. M^ed mod N = M, So is fermat's a^p = a. Which exclusively is right when a or M here is a prime, and co-prime to a. So the converse a^p-1 = 1 mod N is right, but in case of the composite primes, and when M is !coprime to N, M^phi =! 1 mod N, but M^phi + 1 is M. I can't see the problem here. And the other qstn is, ED = 1 mod N, so M^ed is same as M^phi + 1. What is the relation between the 2. Also, is ED is in res class of 1? $\endgroup$ – C0DEV3IL Mar 14 at 15:03
  • 1
    $\begingroup$ "When $a$ and $p$ are coprime, $a^p\equiv a\pmod p$". Uh, no. Counterexample: $a=3$, $p=10$, $3^{10}=59049\not\equiv3\pmod{10}$. What holds is: when $p$ is prime, $a^p\equiv a\pmod p$. This holds regardless of $a$. This is why textbook RSA encryption/decryption restores the plaintext for all plaintexts in $[0,N)$. Contrast with Euler's theorem which can be stated as: If prime $p$ does not divide $a$, then $a^{p-1}\equiv1\pmod p$. $\endgroup$ – fgrieu Mar 19 at 7:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.