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 <aba@dcs.exeter.ac.uk> 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);}

Copyright © Francis Litterio (Send me email)