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^EmodN

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

M=C^DmodN

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^EmodN = 2³mod10 = 8mod10 = 8

M=C^DmodN = 8³mod10 = 512mod10 = 2

for a message of 3

C=M^EmodN = 3³mod10 = 27mod10 = 7

M=C^DmodN = 7³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