0

What is the function that returns the private key d if I know:

  1. The Two primes numbers (q, p)
  2. a selected public key e.

In an RSA algorithm?

hmakholm left over Monica
  • 286,031
TSR
  • 507
  • If you don't want the explicit algorithm, but rather a function to call, then this question belongs on stackoverflow. It's also a good idea to decide what language you want this to work for. – Arthur Oct 18 '16 at 12:55
  • Do you want an algorithm or the name of a function in some software package? I'm not sure there's an explicit function implemented for precisely this, but modular inverses are implemented in various packages for various languages, and that's just what you need, the modular inverse of $e$ with respect to $(p-1)(q-1)$. – Daniel Fischer Oct 18 '16 at 13:09
  • @Arthur Please explain the mathematical algorithm. I really need it – TSR Oct 18 '16 at 13:09
  • @DanielFischer Please explain the mathematical algorithm. Question edited. – TSR Oct 18 '16 at 13:10
  • You could see my answer from yesterday here, which, while not specifically tailored to RSA, will tell you most of what you need. Or the links in the answer below. – Arthur Oct 18 '16 at 13:23

1 Answers1

2

In RSA, $d$ must be the inverse of $e$ modulo $(p-1)(q-1)$. Various algorithms to compute modular inverses exist; the most common one is a simple extension of Euclid's algorithm for computing the greatest common divisor of $e$ and $(p-1)(q-1)$.

There are code examples to be found here.

hmakholm left over Monica
  • 286,031