PKE: The RSA Algorithm

The RSA algorithm, named for its creators Ron Rivest, Adi Shamir, and Leonard Adleman (RSA) 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 Pi be the block of (plain) text to be encrypted. Actually Pi 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.

P.S.Since , then for some integer m. Thus, applying Euler's theorem we have




I think I'm not making ya' troubleunderstood...