RSA Key generation: How is multiplicative inverse computed?

Question

As per Wikipedia, RSA keygen goes like this:

• Choose two distinct prime numbers p and q.
• Compute $n = pq$.
• Compute $\varphi(n) = (p − 1)(q − 1)$.
• Choose an integer e such that $1 < e < \varphi(n)$ and $e$ and $\varphi(n)$ are coprime. $e$ is released as the public key exponent.
• Determine $d$ as $d \equiv e^{−1} \bmod \varphi(n)$; i.e., $d$ is the multiplicative inverse of $e$ (modulo $\varphi(n)$). $d$ is kept as the private key exponent.

Thus the public key is $(e, n)$ and the private key is $(d, n)$.

According to this description, $d$ is determined directly from $e$ and $n$ (i.e. the private key is derived from the public key). I understand that finding the multiplicative inverse in that way is computationally difficult. If this weren't the case, then any attacker could determine the private key from the public key. What am I misunderstanding here? What does the key generator know that an attacker doesn't, and how is that used to determine the private key?

Answer 1

Modular inverse can be computed with Extended Euclidian Algorithm, as other answers suggest.

I will answer your second question - why an attacker can't get private key? The problem here is that the private exponent is the modular inverse of the public one, but modulo $\phi(n)$, not $n$:

$d \equiv e^{-1} \pmod{\phi(n)}$

Attacker does not know $\phi(n) = (p-1)(q-1)$ here and there's no known way to compute it without factorizing $n=pq$.

You can notice that these numbers differ only by $p + q - 1$ but this fact itself does not help much because $p+q=O(\sqrt{n})$ and the simplest trial division algorithm for factorization works with the same complexity (it is far from feasible). Of course there are much more advanced factorization methods but they are also far from factorizing large RSA modulus.

Answer 2

To find multiplicative inverse (d) mod φ(n) you may use Extended Eculdian Algoritm "EEA"(or any other algorithm but EEA is usually used to best of my knowledge).

• The algorithm is explained here http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
• this online tool computes the inverse using EEA http://www.cs.princeton.edu/~dsri/modular-inversion.html

Answer 3

(Realised my mistake as I finished typing the question)

Finding the multiplicative inverse is in fact computationally feasible.

The prime numbers p and q are not public (although n = pq is). An attacker cannot therefore know φ(n), which is required to derive d from e. The strength of the algorithm rests on the difficulty of factoring n (i.e. of finding p and q, and thence φ(n) and thence d).