# Finding Private Key $d$ using RSA [duplicate]

I'm a RSA n00b when it comes to the mathematics for RSA. After spending some time reading, watching lectures, etc. I pretty much have everything down, except for how to figure out the equation for determining the private key $d$.

Reading this very Q/A forum, a person said, "There are better ways to find $d$ from $e$ if you know $\varphi(n)$. But if you don't, you're in trouble, because you need to factorize $n$ to do that."

Taking that comment to heart, what is the "better way" to find "$d$" if you know $\varphi(n)$?

$m=42$ Message to be encrypted

$p=61$ Prime 1

$q=53$ Prime 2

$e=17$ Random Exponent greater than 2

--

$n=3233$

$\varphi(n)= 3120$

I know that $m^e = c \mod n$ is to encrypt and you get $2557$. To decrypt the equation is $c^d = m \mod n$, but my hangup is figuring out $d$. Can somebody spell out the equation, process, etc on figuring out $d$?

• you're looking for the modular inverse of $e \mod{\varphi(n)}$. Google for an algorithm to do it. It is easy and with your numbers you can do easily with pencil and paper (I suggest to do it, to truly understand). Jan 5, 2016 at 14:27
• Crap.. Sorry.. I did just realize that ϕ(n) is (p-1)*(q-1) so that ϕ(n)=3120. I think I found the algo for the inverse. --- math.stackexchange.com/questions/114140/…
– Alby
Jan 5, 2016 at 14:31
• Yes, you found the right algorithm. It is quite easy to implement (in python it takes only few lines) Jan 5, 2016 at 14:55