-1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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/… $\endgroup$ – Jamie Mar 20 '16 at 7:27
  • $\begingroup$ @Jamie take exponent equal to $-1$, modulus to $\phi(n)$. $\endgroup$ – Henno Brandsma Mar 20 '16 at 9:23
  • $\begingroup$ @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/… $\endgroup$ – Jamie Mar 20 '16 at 14:09
  • $\begingroup$ @jamie the API might not accept negative numbers, in which case you might need the extended Euclidean algorithm instead $\endgroup$ – Henno Brandsma Mar 20 '16 at 16:10
  • $\begingroup$ @henno-bandsma Thank you so much! Using the EEA worked perfect. Everything's working fine. $\endgroup$ – Jamie Mar 21 '16 at 0:24
2
$\begingroup$

Usually you can calculate D with

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

Where

$K =$ Any small value, try 2

This video will help you, a lot: https://www.youtube.com/watch?v=e_auEoqetec

| improve this answer | |
$\endgroup$
  • $\begingroup$ How so? I am confused on how important K is in RSA $\endgroup$ – AppIns Mar 20 '16 at 7:10
  • $\begingroup$ @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. $\endgroup$ – fgrieu Mar 20 '16 at 8:51
  • $\begingroup$ @fgrieu True. I'll delete the comment. $\endgroup$ – Henno Brandsma Mar 20 '16 at 9:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.