Original: http://world.std.com/~franl/crypto/rsa-guts.html

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. It is most ironic that it is not illegal to transport this mathematical description out of the U.S. and Canada, but it is illegal to export an implementation of this cipher from the U.S. or Canada. Any competant programmer could use this knowledge to implement a strong crypto product beyond the borders of the U.S. and Canada.

Find P and Q, two large (e.g., 1024-bit) prime numbers.
Choose E such that E is less than PQ, and such that 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.
The encryption function is encrypt(T) = (T^E) mod PQ, where T is the plaintext (a positive integer) and '^' indicates exponentiation.
The decryption function is decrypt(C) = (C^D) mod PQ, where C is the ciphertext (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. 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

Caveats

Given all the hype that RSA is getting these days, it's worth it to keep the following caveats 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.

RSA in 2 Lines of Perl

Adam Back <[email protected]> has created an implementation of RSA in just 2 lines of Perl. It uses dc, an arbritrary 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`

Here's RSA in a few lines of perl without a system call:

#!/usr/local/bin/perl -s-- #export-a-crypto-system sig, RSA in 4 lines PERL:
$e-$d&(($k,$n)=@ARGV)==2||die"$0 -d|-e key mod out\n";$v=$w=1+length$n&
~1;$v-=$d*2;$w-=$e*2;$_=unpack('B*',pack('H*',1$k?"0$k":$k));s/^0+//;
s/1/0lM*ln%/g;s/0/d*ln%/g;while(read(STDIN,$m,$w/2)){$m=unpack("H$w",$m);$a=
`echo 16oOi\U$m SM$n\Esn1$_ p|dc`;print pack("H$v",'0'x($v+1-length$a).$a);}