For $d = e^{-1} \mod \phi(n)$

$$d\cdot e \operatorname{mod} \phi(n)=1$$ $$d = (e^{-1} \operatorname{mod} \phi(n))$$

With having $e$ and $n$, we can calculate the value of $d$ , the private key for cracking. Why do people worry about factoring $d$ when this technique is available? I would like to know some real insight into this.

  • 3
    $\begingroup$ I've never seen anyone worry about factoring d. $\;$ $\endgroup$ – user991 Dec 6 '13 at 2:28
  • $\begingroup$ Haha, I know what you mean :) $\endgroup$ – Ali Gajani Dec 6 '13 at 2:32
  • 1
    $\begingroup$ I don't. Is "factoring the d" an euphemism? $\endgroup$ – rath Dec 6 '13 at 6:33
  • $\begingroup$ What does it mean, if you put the "mod $\phi(n)$" in the denominator? Usually "mod $x$" is meant for the entire statement (term, equation, etc.) $\endgroup$ – tylo Dec 6 '13 at 11:37
  • 1
    $\begingroup$ In your restated version of the question you appear to be asking: "Look: $A$ so $B$ so $A$, meaning $A$ is easy"? Given $(e,N)$ it is not easy to calculate $d$ $\endgroup$ – figlesquidge Dec 7 '13 at 12:13

You are correct in that knowing $\phi(n)$ it is trivial to get the private key back with a simple modular inversion.

However, we are only given $e$ and $n$, and it turns out that computing $\phi(n)$ from $n$ alone is computationally equivalent to finding the factors of $n$. Namely, if you know $\phi(n) = (p-1)(q-1) = (p-1)(n/p - 1)$, you can recover $p$ by solving the quadratic equation $p^2 + (\phi(n) - n - 1)p + n = 0$ for $p$.

  • $\begingroup$ How about solving for d when you know n and e as I explained in my question, using the inverse operation. I don't see how that is hard. I can't digest it, maybe I am imagining smaller numbers. $\endgroup$ – Ali Gajani Dec 6 '13 at 1:43
  • $\begingroup$ To solve for $d$, you must find out $\phi(n)$, since $d = e^{-1} \bmod \phi(n)$. That is the hard part. $\endgroup$ – Samuel Neves Dec 6 '13 at 1:48
  • $\begingroup$ You can solve for phi(n) by doing a quick computation in Wolfram Alpha and it tells you the totient or phi of n. How is that hard? $\endgroup$ – Ali Gajani Dec 6 '13 at 1:49
  • $\begingroup$ Like factoring, it becomes much harder as $n$ grows. If you try to do it for a $2048$-bit $n$, it will not be so easy. $\endgroup$ – Samuel Neves Dec 6 '13 at 1:52
  • 1
    $\begingroup$ It seems I misunderstood what you said earlier. You're correct. $\endgroup$ – Samuel Neves Dec 6 '13 at 2:24

The main misconception here is, what part of the RSA problem is actually hard to compute.

Your statement is like this:

  • We have $e$ and $n$.
  • We know $ed=1$ mod $\phi(n)$.
  • So we should be able to calculate $d$.

Your reasoning is exactly what is happening in the key generation algorithm. Division in modular arithmetic behaves just the same as with rationals, just that they are not fractions but integers with the "same property" (inverse element) - if the inverse exists (that's why gdc$(e,\phi(n))=1$).

So where is the computation problem hidden, and what error was made?

The problem is, that computing $\phi(n)$ is easy if and only if the prime factors of $n$ are known. In fact, from $n$ and $\phi(n)$ you can compute the factorization of $n$ directly. You asked in the comments:

You can solve for phi(n) by doing a quick computation in Wolfram Alpha and it tells you the totient or phi of n. How is that hard?

There is your problem. This "quick computation" is scaling super-polynomially or maybe even exponentially (if no efficient factoring algorithms are used). It might be "easy" for small integers, but factoring numbers between 10 and 100 is also easy and can even be done without a computer.

Btw, if you know $e$ and $d$ instead of $\phi(n)$, you can also calculate the prime factors of $n$ in polynomial time. This is described in Alexander May's paper "Computing the RSA Secret Key is Deterministic Polynomial Time Equivalent to Factoring" (2004). To explain what this result means: If you know $e$ and $d$, then we can also compute $e\cdot d$ in $\mathbb{Z}$. We don't know $\phi(n)$, but we know that $ed=1 + k\cdot\phi(n)$. And we know that $ed < n^2$. If $k$ is small, then this is really easy, but if $k$ close to $n$, it is harder.

edit: rephrasing the last sentence

Anyway, the hardness of the RSA problem is not based on calculating $d$ from $e$ and phi(n). It is hard because $n$ is hard to factorize, and (for RSA modulus) it is constant time equivalent to calculate the factorization from $ph(n)$ and $n$.

  • $\begingroup$ In your last sentence "RSA problem" could be misleading, since the RSA problem is: given an RSA public key $(e,n)$ and a randomly sampled ciphertext $c$ find $m$ s.t. $c\equiv m^e\pmod n$. $\endgroup$ – DrLecter Dec 6 '13 at 12:22
  • 1
    $\begingroup$ Your last sentence isn't just misleading, it's plain wrong. Calculating $\phi(n)$ and factoring $n$ are equivalent. The RSA problem is about solving $c=m^e \pmod n$ for $m$. While best known way is to factor $n$ and compute $\phi(n)$, it might be possible to solve this equation without learning $\phi(n)$ $\endgroup$ – CodesInChaos Dec 6 '13 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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