PKE: The RSA Algorithm

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:

1. Choose two (in practice, large 100 digit) prime numbers p and q and let n = pq.
2. Let P_i be the block of (plain) text to be encrypted. Actually P_i is the numerical equivalent of the text which may either be single letters or blocks of letters, just as long as .
3. Choose a random value E (usually small) such that E is relatively prime to . Then the encrypted text is calculated from

   

   The pair of values (n,E) act as the public key.

4. To decode the ciphertext, we need to find an exponent D, which is known only to the person decoding the message, such that

   

   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 .

• Example