# Finding d given everything else in RSA [duplicate]

I've got everything else (e, p, q, phi(n), n), but cannot see a way to figure out what d should be. P and q are both 300 digits, so phi(n) and n are about 600 digits, but e is only 5 digits. I do already understand that ed is congruent to 1 mod phi(n). Thanks for any suggestions.

Well, $d$ is just the inverse of $d$ modulo $\phi(n)$, as you state. So (if you don't want to write a program) go to a site like Wolfram and type the query (with the correct numbers, not 3 and 35 as I did as an example).

Some googling will give you simple python programs that will do it (python has built-in bignums so it's easy to do in that language).

• Thanks for the reply! I actually wrote some C# stuff to create and calculate all the other variables. I have this function to work with, but I'm not sure exactly what goes where in finding d. onedrive.live.com/… – Jamie Mar 20 '16 at 7:27
• @Jamie take exponent equal to $-1$, modulus to $\phi(n)$. – Henno Brandsma Mar 20 '16 at 9:23
• @henno-bandsma I did try that before, but I thought it was wrong because I seem to be getting this error. Any idea what could be wrong? onedrive.live.com/… – Jamie Mar 20 '16 at 14:09
• @jamie the API might not accept negative numbers, in which case you might need the extended Euclidean algorithm instead – Henno Brandsma Mar 20 '16 at 16:10
• @henno-bandsma Thank you so much! Using the EEA worked perfect. Everything's working fine. – Jamie Mar 21 '16 at 0:24

Usually you can calculate D with

$D = (phi(N)*K + 1) / e$

Where

$K =$ Any small value, try 2

• @HennoBrandsma: $K<e$, thus $K$ is small when $e$ is. In particular $e=3\implies K=2$. That does not harm security in any known way, when proper RSA padding is used. – fgrieu Mar 20 '16 at 8:51