Understanding math behind RSA key derivation [duplicate]

Question

I was reading through the key derivation for RSA. Here are the steps per wiki -

1. Select strong primes $p$ and $q$ such that $pq = n$
2. $\phi(n)$ = $(p-1)(q-1)$
3. select $e$ such that $e$ and $\phi(n)$ are coprime.
4. Select $d$ such that $ed mod(\phi(n)) = 1$

I do not understand why the $\phi(n)$ is even needed. Why can't we just skip the step and say -- select $e$ such that $e$ and $n$ are coprime.

Would it not work? Is the math somehow dependent on that? If so what is it?

Also why should $e$ be coprime to $\phi(n)$?

To clarify my main question was about why e needs to be relatively prime to phi(n). Would it not work if its relatively prime to n?

After following poncho's answer -- Lets say I want to pick e relatively prime to n. In his example N = 77. Lets say e = 4 then d = 19. So $edmod(N) = 1$. Of course e is not a prime number here, but the spec does not say e should be prime.

It would appear that the $\phi(n)$ is chosen so that its smaller than N giving an opportunity to find the $e$ and $d$. So why choose $(p-1)(q-1)$? Why can't it be some other operation to make the result smaller than n?

I know I am missing something here and its not clicking. Hope some one explains it.

Answer 1

Well, if $e$ is not relatively prime to $\phi(N)$, then there won't be any such $d$; in fact, there generally won't be a unique decryption.

For example, let us consider the toy example $N = 77$ and $e=3$. Note, that $\phi(N) = 6 \times 10 = 60$ is not relatively prime to $e$.

Then, let us assume that we receive a ciphertext $41$, and we need to find the plaintext $P^3 \equiv 41 \pmod{77}$. The problem is that there are three; we have $P=13$; as $13^3 \bmod 77 = 41$. However, we also have $P=24$; as $24^3 \bmod 77 = 41$ as well. pick a plaintext $P=13$ and compute the corresponding ciphertext $C=13^3 \bmod 77 = 41$. $P=68$ also works. So, which is the right one? The decryptor has no way of knowing.

We avoid this problem if $e$ and $\phi(N)$ are relatively prime.

Answer 2

At the basic level it is Euler's theorem that makes RSA work. Take a look at how RSA en-/decryption works and what Euler's theorem grants and you can see, why $\varphi(n)$ is needed and why it is $(p-1)(q-1)$.

It ensures that $(M^e)^d \equiv M \mod n$, i.e. that decrypting with $d$ actually yields the original plain text message encrypted with $e$.

Since $e$ and $d$ are co-prime to $\varphi(n)$ one can find a $k \in \mathbb N$ such that $e \cdot d + k \cdot \varphi(N) = 1$. Hence you can deduce:

$(M^e)^d \equiv M^{ed} \equiv M^{ed} \cdot 1 \equiv^* M^{ed} \cdot (M^{\varphi(n)})^k \equiv M^{ed + k\varphi(n)} \equiv M^1 \equiv M \mod n$.

At the $\equiv^*$ step you need Euler's theorem.