A Simple Explanation of RSA
Encryption

If you are interested in math you might
enjoy knowing about RSA, an incredibly powerful, but fairly easy to understand
mathematical system.

RSA is the encryption algorithm that keeps your credit card
information safe when you enter it into a website and it goes there through
many insecure computers.

It was invented by 3 guys who, at the time, were grad
students at MIT.

At the time only government agencies (NSA, CIA) could do
encryption that was any good and RSA was far better: both easier to use and
harder to crack.

It's easier to use because both the algorithm and the
encryption keys can be publicly known, without sacrificing security..

Other encryption schemes required a secret key to be securely
passed between the people who wanted to communicate
securely,

Despite it's complexity for an outsider to decrypt it, the
algorithm is rather elegant and easy to describe.

The only new concept you might need is the mod function (mod
is short for modulus).

The mod function just gives the remainder when you do integer
division.

So for 5mod3, divide 5 by 3 and the answer is 1 with a
remainder of 2 and therefore 5mod3 = 2.
7mod3 = 1. 25mod3 = 1.

In cryptography
circles, Alice and Bob are used as the people secretly communicating.

Alice want to send Bob a secure
message.

Alice gets the encryption key, E, and the
modulo, N, from Bob or a public data base.

Alice divides her message into pieces and converts them to
numbers; A=1, B=2 etc.

She creates C, the cypher text, by raising
M, the number that represents this piece of her message, to the power of E and
gets the answer mod N.

C=M^{E}modN

Bob also has the decryption key, D, and decrypts the message,
C, in a similar way

M=C^{D}modN

This T shirt explains how to get E, N, and D.

I'm not sure why the third line is in the order it is.

I would have expected EDmod((P-1)(Q-1)) = 1
(Pick E and D so that EDmod((P-1)(Q-1)) = 1 )

You can work through the math with an easy example (not
secure, but easy to go through).

Pick prime numbers for P and Q. Let's use 2 and 5.

N = PQ =5*2 = 10 (That makes it easy to do the mod function)

(P-1)(Q-1) = (5-1)(2-1) = 4

If E=3 and D=3, then ED=9 and 9mod4 = 1 (9/4 is 2 with a
remainder 1)

for
a message of 2

C=M^{E}modN = 2^{3}mod10 = 8mod10 = 8

M=C^{D}modN = 8^{3}mod10
= 512mod10 = 2

for
a message of 3

C=M^{E}modN = 3^{3}mod10 = 27mod10 = 7

M=C^{D}modN = 7^{3}mod10
= 343mod10 = 3

It's too bad that both D and E are the same in this
example.

3 and 7 would work as would 5 and 9, but that's too much
math for this easy example.

In real world use, the numbers are 1,000 digits long and
the math gets tedious, but it's the same idea.

If you want to see another example look here:

http://sergematovic.tripod.com/rsa1.html