2
$\begingroup$

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 :-)

$\endgroup$
2
  • 1
    $\begingroup$ I think that should be $(M^E)^D \operatorname{mod} N$ for decrypting. $\endgroup$
    – Paul
    Mar 7 '20 at 12:06
  • $\begingroup$ It's simple: the $D$'th power map is quick to compute $\!\bmod N$ but hard to invert, i.e. computing $D$'th roots $\!\bmod N$ is generally computationally intractable given the state of current knowledge. Thus it yields a nice simple one-way / trapdoor function suitable for crypography. $\endgroup$ Mar 8 '20 at 0:51
6
$\begingroup$

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 likening. 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 aloe 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 fineprint 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 supossed-to-be secret prime can be found by simply computing the gcd of the two moduli
$\endgroup$
2
  • $\begingroup$ Please note that $\lambda(N)$ Carmichael function produces the lowest $d$. $e$ is usually chosen as small integers, prefable Fermat numbers 3 and 65537 $\endgroup$
    – kelalaka
    Mar 7 '20 at 16:59
  • $\begingroup$ I do understand what you just said. But not the fact of why the number of co-primes is related to the product of 2 primes so much that RSA works this good. I hear that Lagrange's theorem has something to do with it. But Being a non mathematics student I don't understand orders of elements and groups. Will you please elaborate on that? :) Thanks $\endgroup$
    – C0DEV3IL
    Mar 8 '20 at 10:26

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.