How do I calculate the private key in RSA? Given $n=pq$ for $p,q$ known, I can calculate $\phi(n)$.

$e$ is selected such that $\gcd (e,\phi(n)) = 1$.

Using this, how do I calculate the RSA private key?



Example:


  I have $n = 35$, with $(p,q)=(5,7)$.
  I have also computed $\phi(n)=24$, and selected $e$ such that $\gcd (e,\phi(n)) = 1$ by taking $e=23$.
  
  Calculate the private key.
The private key $d$ of RSA algorithm with public parameters $(N,e)$ is such that:

$ed \equiv 1\mod{\phi(N)}$. Since by definition $e$ and $\phi(N)$ are coprime then with extended euclidean algorithm you can find such $d$: $ed +k\phi(N)=1$

Consider that to compute $\phi(N)$ you should know how to factor $N$ since $\phi(N)=\phi(p)\phi(q)=(p-1)(q-1)$

To see why this is correct imagine an encryption of the message $m$ to be $c=m^e\mod{N}$.
Then to decrypt you compute $c^d=m^{ed}\mod{N}=m \mod{N}$