The Mathematical Guts of RSA Encryption

The RSA algorithm was invented in 1978 by Ron Rivest, Adi Shamir, and Leonard Adleman.

Here's the relatively easy to understand math behind RSA public key encryption.

1. Find P and Q, two large (e.g., 1024-bit) prime numbers.
    
2. Choose E such that E is greater than 1, E is less than PQ, and E and (P-1)(Q-1) are relatively prime, which means they have no prime factors in common. E does not have to be prime, but it must be odd. (P-1)(Q-1) can't be prime because it's an even number.
    
3. Compute D such that (DE - 1) is evenly divisible by (P-1)(Q-1). Mathematicians write this as DE = 1 (mod (P-1)(Q-1)), and they call D the multiplicative inverse of E. This is easy to do -- simply find an integer X which causes D = (X(P-1)(Q-1) + 1)/E to be an integer, then use that value of D.
    
4. The encryption function is C = (T^E) mod PQ, where C is the ciphertext (a positive integer), T is the plaintext (a positive integer), and ^ indicates exponentiation. The message being encrypted, T, must be less than the modulus, PQ.
    
5. The decryption function is T = (C^D) mod PQ, where C is the ciphertext (a positive integer), T is the plaintext (a positive integer), and ^ indicates exponentiation.

Your public key is the pair (PQ, E). Your private key is the number D (reveal it to no one). The product PQ is the modulus (often called N in the literature). E is the public exponent. D is the secret exponent.

You can publish your public key freely, because there are no known easy methods of calculating D, P, or Q given only (PQ, E) (your 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 your modulus into P and Q.

Here is an example of RSA encryption.

Caveats

Though it is widely suspected to be true, it is not yet proven that no easy methods of factoring exist. It is not yet proven that the only way to crack RSA is to factor the modulus.

RSA in 2 Lines of Perl

Adam Back has created an implementation of RSA in just 2 lines of Perl. It uses dc, an arbitrary precision arithmetic package that ships with most UNIX systems. Here's the Perl code:

print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`