I was reading through the key derivation for RSA. Here are the steps per wiki -
- Select strong primes $p$ and $q$ such that $pq = n$
- $\phi(n)$ = $(p-1)(q-1)$
- select $e$ such that $e$ and $\phi(n)$ are coprime.
- 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.