Is there an easy way to calculate "d" in the RSA algorithm?

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?

Replay

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.

Category: encryption Time: 2016-07-30 Views: 2

Related post

iOS development

Android development

Python development

JAVA development

Development language

PHP development

Ruby development

search

Front-end development

Database

development tools

Open Platform

Javascript development

.NET development

cloud computing

server

Copyright (C) avrocks.com, All Rights Reserved.

processed in 2.431 (s). 13 q(s)