Being a non mathematics student, I started to understand RSA. Now I am at a place where I can show someone how to do it or prove it mathematically. What I don't understand is why we do the maths that we need to do? Mathematically it's easy to follow laws of indices, and other theorems and get to a point, but I want a visual understanding of whats happening. In short, I want to understand it like a 5 year old.
What I do understand and have tried
- Choose 2 primes P and Q,
- Find their product N,
- Find Totient of N -> p-1 x q-1
- find a co-prime number E to the Phi
- Find the inverse of E, such that ED = 1 mod Phi
- To encrypt, use M^E Mod N, and to decrypt, (M^E)^E Mod N
- The End
Now, As I have scratched my head for a few months now, I get that Finding the original primes are hard, and that is the basis of RSA. And that's why finding the Phi or Totient is also hard. Which makes it a trap door.
What I don't understand:
- We could have done the same process without the Totient aswell. Find the E with respect to N and the inverse would have worked aswell. Why not? So I went ahead and tried it myself, came to understand, that N is the public number and anyone with the E and N can compute the D, so no use of RSA at all. So we probably use the Totient. but what I have learnt, is that Totient is the total number of numbers that are co-prime to N. But if we look at RSA calculations, The totient is hugely used other than just a simple number used, that is harder to calculate from a huge N, but we see the Phi of N and the N has a lot of mathematical relation aswell. For example, ED = 1 Mod Phi. but on the other hand, Euler's theorem says a^PhiN = 1 Mod N. Here we see there is a mathematical relation of Phi of N and N. What is the relation? I want to know desperately. Even during encryption and decryption process, we use M^ed MOD N. We know we found ed with respect to mod Phi, but RSA works during enc/dec by performing mod with N. So there has to be some relation between Phi and N beside just the count of co-prime numbers.
- I deduced another thing from the ED = 1 thing, that it's the exponent that we use over the message. It's more like M^1 mod N. Any number powered with 1 yields the original number or M in this case. If I am even remotely right, Any 2 numbers could have done that. We wouldn't have to know Fermat's or Euler's theorem to have any 2 numbers that would yield 1 when multiplied. The scientists must have chosen this method for a reason. And that reason directly asks the relation between Phi and N. Please tell me what's that.
- Even if point 2 of what I thought was right, that we just needed 2 numbers to yield 1 when multiplied, then why do we need the mod number to be N during enc/dec? Why it couldn't have been any number?
- Lastly, if we look at Fermat, or Euler, we see that having 1 as a result is too damn important. A^p-1 = 1 mod P, a^phi = 1 mod N. In every case, getting 1 is so important. Why exactly? When I looked up at the purpose for Euler's or Fermat's theorem, the internet said, Fermat is used to easily calculate big exponents mod some number. Euler's says, that it gives the order of the multiplicative group of integers modulo n (the group of units of the ring ℤ/nℤ). What does this mean aswell?
Thanks for taking out the time. I would really love a more visual explanation instead of just mathematical equations. Thanks a lot guys :-)