RSA - Proof for dummies

Question

I'm understanding the basic idea behind why RSA is secure, but I'm having a hard time understanding its proof with only basic knowledge of numbers theory. so I'm hoping that somebody can help me answering a few questions:

By generating two random primes and building the product $n = p\cdot q$, we can easily get eulers totient function $\phi(n) = (p-1)\cdot(q-1) $ without having to check all relatively prime between $[1;pq]$

Question 1) Is the only reason why $p$ and $q$ have to be prime numbers that we can easily compute $\phi(n)$? Or is there another consequence of $n$ being the product of two primes? As $n$ is not necessarily a prime, I don't see any other implication.

Next we choose an $e$ so that $1 < e < \phi(n)$ and $gcd(e, \phi(n)) = 1$

Question 2) Could I also say that we just randomly choose an element of the multiplicative group $Z_{\phi(n)}^*$? I mean, all elements of this group are relatively prime to $\phi(n)$ right?

Question 3) Does the length of $e$ have an influence on the security?

Next we choose the inverse element $d$ of $e$, in other words, $e\cdot d \equiv 1 \mod \phi(n)$. So, now we can encrypt some $c = m^e \mod n$ and decrypt by $m=c^d \mod n$

Now, by substituting $c$ in the decryption we get $m = (m^e)^d \mod n$ which is the same as $m=m^{ed} \mod n$

Now I'm not getting anywhere further because I'm seeing very different ways how people proof it (chinese remainders? We never learnt them so there should be another way). Would somebody be so kind to explain the proof with eulers theorem or fermats theorem in a way that even a dummy like me can follow it? :)

Answer 1

1. The correctness of the cryptosystem (in the sense that decryption is inverse to encryption) depends on $$m^{k\phi(n)+1}\equiv m\pmod n$$ for all $m$. Euler's theorem says that this is the case when $m$ and $n$ are coprime -- which is not enough here -- but if $n$ is known to be square-free it is actually the case for all $m$.

   Constructing $n$ as the product of two different primes is an easy way to make sure it is square-free. It also seems to be a straightforward way to maximize the difficulty of computing $\phi(n)$ among other $n$s of a similar size.

2. Yes, you could just choose a random coprime $e$. In practice people pick smallish $e$ such as 65537 because it slightly reduces the work one needs to do to apply the public key.

3. $e=1$ obviously won't do. Anything larger than that is thought to be okay, as long as proper padding is used for the messages (such that you avoid having $m^e < n$).

   On the other hand, $d$ (which is the the only secret essential part of the secret key) should be large. Choosing a small $e$ will automatically prevent $d$ from being so small that known key-recovery attacks for small $d$ will work.

Answer 2

Is the only reason why $p$ and $q$ have to be prime numbers that we can easily compute $\phi(n)$?

The reason is to make it hard to find $p$ and $q$ (secret) from $n$ (public info).