What's the REASON behind the mathematics of RSA?

Question

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

1. Choose 2 primes P and Q,
2. Find their product N,
3. Find Totient of N -> p-1 x q-1
4. find a co-prime number E to the Phi
5. Find the inverse of E, such that ED = 1 mod Phi
6. To encrypt, use M^E Mod N, and to decrypt, (M^E)^E Mod N
7. 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:

1. 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.
2. 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.
3. 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?
4. 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 :-)

Answer 1

This is just Euler's theorem at work. You could use any modulus $N$ and any two exponents $E,D$ where you know that $$\tag1(x^E)^D=x^{ED}\equiv x\pmod N$$ holds for (nearly) all $x$. The point is that for general $N$, it is extremely hard to find suitable $D$ for given $E$; if it were not hard, any eavesdropper could just find one themselves.

Thanks to Euler, we know that $(1)$ holds if only we can find our $E,D$ such that $$ ED\equiv 1\pmod{\phi(N)}.$$ That's good news for us because finding a multiplicative inverse to $E$ modulo $\phi(N)$ (where $E$ must be coprime to $\phi(N)$) is very easy and can by done with Euclid's algorithm. The problem is that for arbitrary $N$, it is extremely hard to compute $\phi(N)$; if it were not hard, any eavesdropper could just compute $\phi(N)$ themselves and find $D$ from $E$ (or vice versa).

Fortunately, we are not given $N$ but can choose it to our liking. If we know that prime factorization of $N$, then computing $\phi(N)$ is very easy. For example, if $N$ itself is a prime, then $\phi(N)=N-1$ and we are go. Unfortunately, picking prime $N$ is no good idea as the enemy can readily check that $N$ is prime and hence can also immediately compute $\phi(N)$ etc. What if we make $N$ the product of many primes? In that case most of these primes must be much, much smaller than $N$. Finding small prime factors is easy by just doing trial division - so we do not want that.

It seems the best compromise is to pick two big (and random) primes $p,q$ and take $N=pq$. Then we know that $\phi(N)=(p-1)(q-1)$ and are go. But factoring $N$ without knowing $p,q$ is hard - yay!

---

Of course there is also some fine print to check, such as:

• Neither $p$ nor $q$ are allowed to be "small"
• $q$ should not be $\approx p$ or else an enemy might simply succeed by checking primes near $\sqrt N$
• More generally, $\frac qp$ should not be unusually close to any very simple fraction (because there are known algorithms that may well succeed in such a case)
• $E$ should neither be $\pm1\pmod p$ nor $\pm1\pmod q$
• The prime numbers should really be random within their ranges. Otherwise it might happen that many keys are generated with some "favourite" primes, and from knowing two moduli with one common prime factor, that supposed-to-be secret prime can be found by simply computing the gcd of the two moduli