The RSA algorithm for public-key encryption was originated by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT in 1977. Several similar methods had been proposed by earlier workers. The algorithm is based on the fact that it is far more difficult to factor a product of two primes than it is to multiply the two primes. Even the most powerful modern supercomputers would require more time than the age of the universe to factor a 400-digit number. (This might change if quantum computers ever become operational.)
In this Demonstration, the RSA algorithm is simulated using much smaller randomly chosen prime numbers,
and
both less than 100. The public key, which is made freely available to Alice and all other users, consists of the two numbers
and an exponent
, which is an odd integer relatively prime to
between 1 and
. (Here
is Euler's totient function, the number of positive integers less than
and relatively prime to
.) For simplicity, take
and also limit messages to three letters, such as XYZ. This constitutes the plaintext and is converted into an integer
using, for example, ASCII codes. The corresponding ciphertext
is computed using
.
Only the recipient Bob has access to the private key, which is an integer exponent
, a modular inverse to
such that
. To determine
, a codebreaker would need to find the prime factors of
, which, as noted earlier, is hopefully impossible. The plaintext is recovered using
. The method works since
(mod
), with application of Fermat's little theorem. The public and private keys can periodically be changed according to some prearranged schedule.
By inputting the public key
and the three-part ciphertext
, Bob can recover the plaintext message.
Browse all topics
