next up previous contents
Next: Cryptographic hash functions Up: RSA Previous: RSA

Description of the RSA algorithm

  1. Find P and Q, two large (e.g., 1024-bit) prime numbers.
  2. Choose E such that E and (P-1)(Q-1) are relatively prime, which means they have no prime factors in common.
  3. Compute D such that (DE - 1) is evenly divisible by (P-1)(Q-1). Mathematicians write this as tex2html_wrap_inline1203 , and they call D the multiplicative inverse of tex2html_wrap_inline1207 .
  4. The encryption function is tex2html_wrap_inline1209 , where T is the plain-text (a positive integer).
  5. The decryption function is tex2html_wrap_inline1213 , where C is the cipher-text (a positive integer).

The public key is the pair (PQ, E)gif. The private key is the number D (reveal it to no one). The product PQ is the modulus. E is the public exponent. D is the secret exponent.

The public key can be published freely, because there are no known easy methods of calculating D, P, or Q given only (PQ, E) (the public key). If P and Q are each 1024 bits long, the sun will burn out before the most powerful computers presently in existence can factor the modulus into P and Q.

Given all the popularity around RSA, it is worth it to keep the following in mind. It is not yet rigorously proven that no easy methods of factoring exist. Also, it is not yet rigorously proven that the only way to crack RSA is to factor the modulus.

Asgaut Eng
Wed Apr 10 14:07:30 MET DST 1996