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

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

## 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 (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`

Copyright 1999-2001 Francis Litterio (Send me email)