How to calculate $d$ if $q,p$ are known?

Question

Consider two prime numbers, $p,q$ and $N=pq$. Also, consider $e$ which is co-prime to $(p-1)(q-1)$ and $ed \equiv 1 \mod (p-1)(q-1)$.

Given $(N,e)$ (the public key) and $p,q$ (which suppose to be private but you happened to know their values), how can you find out what $d$ is?

I'm aware of the Chinese remainder theorem but I'm not sure how to apply it here.

Answer 1

You answer your own question: $e$ and $d$ are multiplicative inverses modulo $\phi(n) = (p-1)(q-1)$, which you an compute if you know $p$ and $q$.

Then apply the extended Euclidean algorithm to $e$ and $\phi(n)$ to find integers $x,y$ such that

$$xe + y\phi(n) = 1$$

which is possible as $\gcd(e, \phi(n))=1$ is enforced in RSA.

Then $d \equiv x\pmod{\phi(n)}$ taking the above equation modulo $\phi(n)$, which cancels the second term.