# The Mathematical Guts of RSA Encryption

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

# 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