Search code examples
encryptionrsa

How to find d, given p, q, and e in RSA?

I know I need to use the extended euclidean algorithm, but I'm not sure exactly what calculations I need to do. I have huge numbers. Thanks

Solution

  • Well, d is chosen such that d * e == 1 modulo (p-1)(q-1), so you could use the Euclidean algorithm for that (finding the modular multiplicative inverse).

    If you are not interested in understanding the algorithm, you can just call BigInteger#modInverse directly.

     d = e.modInverse(p_1.multiply(q_1))