Paul Dundon’s Weblog

Icon

A little cheese and a little whine

The Mathematics of RSA

A few years ago, I spent a few months with way too much time on my hands. One result of this was a paper on the mathematics underpinning the RSA encryption system written for people with an interest in maths but not much knowledge of it beyond high school. Yesterday, an old friend asked for a copy; so here it is (apologies for the PDF; let me know if you’d like it in another format). The first 11 pages review the basic mathematical concepts needed, so if you’re already familiar with prime numbers and modular arithmetic, you can skip them.

A very quick summary: Imagine a clock face with millions of numbers, instead of just 12. Suppose that all the numbers 1 to n appear on the clock face, in random order. Now suppose you have two numbers, p and q, so that p+q=n. Point the minute hand of the “clock” to the number that corresponds to the message you want to send. Now, advance it p places clockwise. The number it now points to is your encrypted message. You send the message. The recipient makes their own clock with the numbers in the same order, and points the minute hand at the number you’ve sent them. Then, they advance the minute hand by q places clockwise. The minute hand is now pointing at your message. So, p and q form an asymmetric key pair – one key is used for encryption, and one for decryption. The actual algorithm is more sophisticated (for example, p and q don’t add up to n, since this would make it easy to work out one given the other) but the basic principle is the same.

Advertisements

Filed under: Maths

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Join 13 other followers

My Bookshelf

The Golden Bough
The Value of Nothing
The Fire
A Wolf at the Table
Devil Bones

My del.icio.us links

%d bloggers like this: