1
$\begingroup$

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

| improve this question | |
$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – ddddavidee Jan 5 '16 at 14:27
  • 1
    $\begingroup$ 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/… $\endgroup$ – Alby Jan 5 '16 at 14:31
  • 1
    $\begingroup$ Yes, you found the right algorithm. It is quite easy to implement (in python it takes only few lines) $\endgroup$ – ddddavidee Jan 5 '16 at 14:55

Browse other questions tagged or ask your own question.