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

• Take a look at the extended Euclidean algorithm – DrLecter Dec 6 '13 at 3:21
• I figured it out and I'll answer my question soon – Ali Gajani Dec 6 '13 at 3:25
• This question appears to be off-topic because its scope is too local. It's unlikely that anyone else will need to calculate a key with these exact parameters. Maybe if you edited the question to make it more general... – rath Dec 6 '13 at 6:24
• I recommend you reading Conrado's post in here, it's easier to understand than that on the Wiki – T.B Dec 6 '13 at 10:42

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

I figured out the decent way of solving for $d$ (the private key).

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$. To calculate the private key, we need to use the formula:

$$d = e^{-1} \mod \phi(n)$$

This gives us $d = 23$, which happens to be the same as $e$, a coincidence.

• These are standard techniques you can find in all books.We say the same thing.In order to compute the inverse you can use the extended euclidean algorithm – curious Dec 7 '13 at 12:09
• Also, this isn't a much of a coincidence, because $e=23=-1\pmod{24}$ and so $e^2=(-1)^2=1\pmod {24}$. – Cryptographeur Dec 7 '13 at 15:42
• Can you elaborate more on what it is you're pointing out? If e=23 then $e^2$=$23^2$ and 529 mod 24 = 1 but why is it not a coincidence that d and e are both 23? In my very limited travels in cryptography, I usually don't see d and e being the same value. I'm not sure what I'm supposed to be realizing. – harperville Mar 8 at 0:17