1
$\begingroup$

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.

$\endgroup$
10
  • 3
    $\begingroup$ I've never seen anyone worry about factoring d. $\;$ $\endgroup$
    – user991
    Dec 6, 2013 at 2:28
  • $\begingroup$ Haha, I know what you mean :) $\endgroup$
    – Ali Gajani
    Dec 6, 2013 at 2:32
  • 1
    $\begingroup$ I don't. Is "factoring the d" an euphemism? $\endgroup$
    – rath
    Dec 6, 2013 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, 2013 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$ Dec 7, 2013 at 12:13

2 Answers 2

6
$\begingroup$

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$.

$\endgroup$
9
  • $\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, 2013 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$ Dec 6, 2013 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, 2013 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$ Dec 6, 2013 at 1:52
  • 1
    $\begingroup$ It seems I misunderstood what you said earlier. You're correct. $\endgroup$ Dec 6, 2013 at 2:24
4
$\begingroup$

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$.

$\endgroup$
2
  • $\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, 2013 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$ Dec 6, 2013 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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