I'm trying to learn how RSA works. From what I found online, I'm supposed to generate private key using Extended Euclidean algorithm.

I've managed to generate the public key, but don't know how to use EEA to generate the private key. How should I exactly input into EEA, and how to process the output?

  • 1
    $\begingroup$ $d = e^{-1} \bmod lcm(p-1, q-1)$, or alternatively, $d = e^{-1} \bmod (p-1)(q-1)$ $\endgroup$ – poncho Dec 14 '15 at 13:46
  • $\begingroup$ @poncho Is $e^{-1}=\frac{1}{e}$ or does it have some other meaning? $\endgroup$ – Mirac7 Dec 14 '15 at 14:08
  • $\begingroup$ $e^{-1}$ is that value such that $e \times e^{-1} \equiv 1 \bmod lcm(p-1, q-1)$. EEA is an algorithm that can be used to find such values $\endgroup$ – poncho Dec 14 '15 at 14:11

Browse other questions tagged or ask your own question.