Your numbers are a bit large to work with spontaniously, do you mind if I use 3 and 17 instead? And I’m only going to discuss the RSA public key algorithm here, which is the most popular.

Okay, to quickly summarize http://www.faqs.org/faqs/cryptography-faq/part06/ …

A public key cryptosystem is defined by four major components:

A public key. (aka the encryption key)

A private key. (aka the decryption key)

An encryption function, which takes the public key and a plaintext message and gives back an encrypted message.

A decryption function, which takes the private key and an encrypted message, and gives back a plaintext.

The encryption function has a special property - it’s something that’s fairly easy to compute, but very hard to guess what the inputs were if you only know the answer. The modulo (remainder) operation explained below is an example of one such function.

But back to RSA. RSA’s two keys are based on two (very large!) prime numbers. These two numbers are known as P and Q. These numbers are not the keys, but the keys are made from them.

There are also two other numbers involved, called e and d. These are essentially arbitrary and are picked because we need them to do the math in the encryption and decryption functions. They have certain mathematical qualities relative to p and q - see the link if you care. Basically, (d*e - 1) must be divisible by (p-1)*(q-1). I believe this is so that the modulo math in the encryption and decryption functions will work correctly, though my understanding is sketchy.

Speaking of modulo math, let’s cover that quickly. Modulo math is when you divide one number by another and then find the remainder. Remember this from 5th grade? Like, 7 divided by 3 is 2, with a remainder of 1? Because 3 * 2 = 6, plus 1 = 7.

Another way to think of modulo math is adding times together. If it’s been 14 hours since 11 o’clock, what time is it? Well, the clock wraps around at 12 hours, so 14 - 12 = 2. 11+2 = 13, but it wraps around at 12 again so 13 - 12 = 1. So 14 hours past 11 o’clock is 1 o’clock.

Notice that if you only know the answer, 1, it’s very hard to know what the two input numbers were. It could be 2 and 3, 6 and 13, or possibly even something like 25 and 76.

Now maybe you can see the beginnings of the encryption already. If you and some friends wanted to share secret messages. You could assign A=1, b=2, c=3, etc and write each other long strings of numbers, but that might be figured out pretty fast. A slightly (only slightly, it’s still easy to break) more clever method might be to pick a random number, and then tell your friends the random number. Then when they want to encrypt a message, they take the number of each letter, and modulo the random number with it. Now A=17 or something crazy like that.

Okay, here’s the encrypter and decrypter functions for RSA. Remember, p and q and prime numbers, e and d are more or less arbitrary numbers picked so they have the above mentioned properties with regard to p and q. We will turn our message to be sent into a number as well, perhaps by changing the letters into numbers ala A=1, B=2, C=3, etc, and then lumping them together. So “ABC” becomes “123”. (In RSA, the number representing the plaintext of a message can be any number up to 2^512, which is roughly 4.2 billion ^ 16, so you have plenty of message size to play with…

The encrypter function is:

Encrypted = (Decrypted ^ e) modulo (p*q)

The decrypter function is:

Decrypted = (Encrypted ^ d) modulo (p*q)

The information you need to encrypt a message is p * q and e. So the public key in RSA systems is the pair of numbers: (e, p*q).

Similiarly, the information you need to decrypt a message is (d, p*q). This is the private key.

Besides the modulo problem, the security of the system rests on the fact that it’s hard to deduce p and q from p times q. Especially when p is 256 bits long, and q is 258 bits long, as they are in RSA. You can safely publish (p*q, e) in every newspaper in the world and it’s going to be very, very, VERY difficult for someone to deduce the individual p and q from that. And since e was chosen more or less at random, you’re not giving away much there either. As the link I gave earlier says, nobody has figured out any good way to get p and q from (p*q, e). The only ways we know are brute-force methods that are very slow - they take the fastest computers we can make right now several days to break even a really short message.

Now, a quick runthrough of the math. Before we encrypt or decrypt we need to generate p and q. We’ll just pick 3 and 17 since they make the math easy.

Now we need to find e and d. (e*d - 1) has to be divisible by (p-1)*(q-1). So (e*d - 1) has to be divisible by (2 * 16) or 32. Now, we have a fair bit of lattitude here, because e and d can be very large if we want them to be, and they don’t have to be prime either. They can be just about anything as long as they satisfy the equation. To keep the math decently simple, I will choose 63 (32 * 2 - 1) as what e*d - 1 will equal. Now, since e*d - 1 = 63, e*d = 64. Again, I will more or less randomly choose e as 4 and d as 16, since 4 * 16 = 64.

Okay, so we have p and q and e and d. Next, we choose our message. How about “A” = 1? (Yeah, yeah, I know - if we use only a single digit for each letter, we can only do up to J before we run out of numbers. I’m trying to keep the math easy, alright?)

Now we do the math:

Encrypted = (Decrypted ^ e) mod (p*q)

Encrypted = (1 ^ 4) mod (51)

This is easy enough I can do it in my head: 1 to the anything = 1, and 1 mod anything = 1. So:

1^ 4 mod 51 = 1

This is not so good - our cyphertext really ought to be different than our plaintext. This happened because I chose “1” as the plaintext. In reality I think RSA pads any message that’s too short (too small a number) so this kind of thing doesn’t happen.

Well, let’s work the decryption:

Decrypted = (Encrypted ^ d) mod (p*q)

Decrypted = (1 ^ 16) mod (51)

Again, we’ve lucked out - 1 to the or mod anything is 1, so:

1^ 16 = 1, and 1 mod 51 = 1

Thus we have our “A” again. Actually, this example is a cheat. As mentioned before, the math doesn’t work out right unless short messages are padded to be longer than (p*q) or (e*d - 1) or something. But hopefully this will give you an idea how things work.

-Ben