# Understanding math behind RSA key derivation [duplicate]

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.

• I put in the close vote because, with your edit, you are essentially asking crypto.stackexchange.com/questions/12710/… Commented May 23, 2014 at 3:21
• Yep. You are right. Commented May 23, 2014 at 5:27
• I found this which is even better Commented May 23, 2014 at 5:53
• @user220201 Lets hypothetically say you ignore ϕ$\phi(n)$ and assume it works for e when just taking n for all computations instead - as in your example (this means you do not need to know the factorization of $N$ anymore to compute the private key). Would it be hard to figure out the private key from only the public then? Would that scheme make sense? Commented May 23, 2014 at 7:03

## 2 Answers

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.

• Understood. But why should e be relatively prime to phi(n)? Would it not work if e is relatively prime to n? Commented May 23, 2014 at 2:19
• e should "be relatively prime to phi(n)" so that the key generator can find a multiplicative inverse of e mod phi(n). $\:$ e being "relatively prime to n" is not a problem, it's just not sufficient. $\;\;\;\;$
– user991
Commented May 23, 2014 at 2:43
• @user220201: Actually, e being "relatively prime to n" is neither sufficient nor necessary. For example $N=77$ and $e=7$ works just fine; in this case, we have $d=13$; for example, if $P=13$; $C=13^7 = 62$ and $P=62^{13} = 13$. Now, of course, for security purposes, you probably don't want to deliberately make $e$ having a nontrivial factor for your modulus; however there's no reason why RSA encryption and decryption wouldn't work. Commented May 23, 2014 at 3:11

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.