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.

  • 1
    $\begingroup$ I put in the close vote because, with your edit, you are essentially asking crypto.stackexchange.com/questions/12710/… $\endgroup$ – poncho May 23 '14 at 3:21
  • 1
    $\begingroup$ Yep. You are right. $\endgroup$ – user220201 May 23 '14 at 5:27
  • 1
    $\begingroup$ I found this which is even better $\endgroup$ – user220201 May 23 '14 at 5:53
  • $\begingroup$ @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? $\endgroup$ – DrLecter May 23 '14 at 7:03

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.

| improve this answer | |
  • $\begingroup$ Understood. But why should e be relatively prime to phi(n)? Would it not work if e is relatively prime to n? $\endgroup$ – user220201 May 23 '14 at 2:19
  • 2
    $\begingroup$ 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. $\;\;\;\;$ $\endgroup$ – user991 May 23 '14 at 2:43
  • $\begingroup$ @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. $\endgroup$ – poncho May 23 '14 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.

| improve this answer | |

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