The RSA algorithm, named for its creators Ron Rivest, Adi Shamir, and Leonard Adleman, is currently one of the favorite public key encryption methods. Here is the algorithm:
The pair of values (n,E) act as the public key.
Note that .
Then we may calculate
This step is based on the following result:
where Show
that this result is true.
By Euler's theorem
provided E and are relatively prime, which is
true by the choice of E. So we obtain
Therefore, we have an equation that can be used to find the "key" exponent
D. The central result of the RSA algorithm is that this equation
is computationally solvable in polynomial time (actually using the Euclidean
Algorithm) whereas solving by factoring n requires exponential
computational time. [Note however that this last statement has never actually
been proven but only demonstrated given today's algorithms. Should someone
discover an algorithm that factors integers in polynomial time, the RSA and
similar algorithms could be rendered useless for secure communications.] Central
to these calculations is knowing the factorization of n, since we
will need to calculate both and
.
Charlie Fletcher