Archived from http://world.std.com/~franl/crypto/rsa-guts.html, which is sadly no longer available.

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.

- Find
*P*and*Q*, two large (e.g., 1024-bit) prime numbers.

- 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.

- 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*.

- 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*.

- 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.

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.

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`

Copyright © 1999-2001 Francis Litterio