0
$\begingroup$

Quite frankly, it is a pain to use the Extended Euclidean Algorithm to calculate d (the private exponent) in RSA. The equation used to find d is:

$$ e d \equiv1~(\mathrm{mod}~ \varphi(n)).$$

Does anyone have a way to solve for d using basic algebra or something simpler? If not, can someone explain how to use the Extended Euclidean Algorithm to find d?

|improve this question
$\endgroup$
  • 1
    $\begingroup$ if $\frac{1+k\cdot \varphi}{e}, k\in\mathbb N$ is an integral number, you have found $d$. This doesn't scale as nicely as the EEA does though. $\endgroup$ – SEJPM♦ Jul 30 '16 at 20:14
  • $\begingroup$ On the other hand, $0 < k < e$, and so there are only $e-1$ possible values of $k$ to try; if $e$ is small, this would be practical (if less efficient than EE) $\endgroup$ – poncho Jul 30 '16 at 20:20
  • $\begingroup$ @SEJPM That's an answer, right? Or should I brush up on my RSA wrt "doesn't scale as nicely"? Connor C, $d$ is the private exponent. Together with the modulus it is the private key (although Chinese Remainder Theorem parameters could also be used). $\endgroup$ – Maarten Bodewes♦ Jul 30 '16 at 20:32
  • $\begingroup$ Possible duplicate of “Calculating RSA private exponent when given public exponent and the modulus factors using extended euclid” $\endgroup$ – e-sushi Jul 31 '16 at 10:43
3
$\begingroup$

The easiest way which is widely known to calculate a modular inverse is finding the smallest $k\in\mathbb N$ such that the following expression is an integral integer:

$$\frac{1+k\cdot \varphi}{e}$$

If this is an integral integer, it is the inverse of $e$ modulo $\varphi$ and thus $d$ and you'll find it with at most $e$ tries.

The issue obviously know is that the run-time of this will grow linearly with the size of $e$, as opposed to the extended euclidean algorithm (EEA) which will run in time proportional to (a power of) the logarithm of $e$, which will especially be much faster than the above method when $e$ is chosen as large as the modulus. If you want to see examples and how-tos on the algorithm, Wikipedia is your friend as usual.

|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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