RSA Key generation: How is multiplicative inverse computed? 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 &lt; e &lt; \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?
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.