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 , and they call D the multiplicative inverse of .
4. The encryption function is , where T is the plain-text (a positive integer).
5. The decryption function is , where C is the cipher-text (a positive integer).

The public key is the pair (PQ, E). 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.