News: Understanding Modern Cryptography: Public Keys

Last time, we looked at archaic cryptography, so you should have a basic understanding of some of the concepts and terminology you'll need. Now, we'll discuss one of the most important advances in computer security in the 20th century—public key cryptography.

What Is Public Key Cryptography?

Public key cryptography is a clever way of exchanging information securely (my math teacher told me about it back in 9th grade, and I've been fascinated ever since!). Rather than giving you a technical definition, let's look at the following (more concrete) problem.

Problem

Suppose you have a message that you want to send to your friend Alice, but you don't want anyone else to be able to read it. You could put in a box with a really strong lock on it, but then she wouldn't be able to open it, because she doesn't have the key. Sending the key is too risky because someone could easily duplicate it. Can you think of a way that we can send our message securely?

Solution?

If it were me sending the message, I would need to send it using my lock, then Alice would send it back with her lock also on it. When I receive it back, I would then take my lock off and send it back to her again. Finally, she takes off her lock and voilà, she (and only she) is able to read the message!

This method is often referred to as an asymmetric key system. The symmetric key system would have entailed us sending a locked message to Alice under the assumption that she already has a key to our lock. There are two main advantages to asymmetric key systems:

1. No keys are ever exchanged, thus preventing a malicious 3rd party from duplicating them.
2. Each person has their own "lock", so if one person's key is compromised, it does not negatively affect both person's security.

Real-Life Application

In real life, we don't really want to send our mail in locked boxes, and this cannot be done with emails, since they only exist in the virtual world.

What happens is each party (or person) generates a public and private cryptographic key. The public keys are then uploaded to a database on a public server that is readily accessible by anyone. Depending on which system we use (let's assume a symmetric one, since it's simplest) and the chosen key exchange scheme (let's assume Diffie-Hellman), when we want to send a message to Alice, we look up her private key and combine it in a certain way with our private key.

Now we have  a "shared secret" that can be used as a mutual key for a symmetric system, as discussed above.

Key Generation

One method of generating private and public keys is by integer factorization. Essentially, every non-prime (composite) number can be factored into two smaller prime factors so that when multiplied they equal the original number. Take, for example, the composite number 864 and factor it:

We now have the two factors: 2^5 and 3^3. We can use our original number as a public key and the two factors as private keys. Relatively speaking, 864 is easy to factor, while larger numbers are increasingly more difficult due to the shear amount of possibilities that must be tested to find the two unique prime factors for a given composite number.

According to Wikipedia, in 2009 the largest number (232 digits long) was factored using hundreds of computers over two years! Until quantum computers or some other type of computer with immense processing power are developed, this cryptosystem is secure to use, so long as your private key is never revealed.

Want to help humanity find new Mersenne Primes? Check out: GIMPS! 

• Questions? Ideas for new articles? Visit our forum!
• Follow us on Google+ or Facebook!

Photos: Cover, Key_Exchange, Factorization