Public Key Cryptography

For many years, in fact for all of history except the last half-century, it was thought that the best way to make a message secret was to share a "secret key" that would "unlock" the message. For example, let's say I were to write the message: jr;;p - you might have no idea what I meant until I let you in on the secret that I had typed the message one key to the right of where I meant on the keyboard. If you look at a computer keyboard, you'd see that, shifted left one key, the message reads hello. Without this secret, it might be difficult to discern what the message was. It could have just as easy been jello or kiddo or anything else at all. If you have a very mathematically complicated key, this is actually a very secure way of sending messages, as long as you can make sure that only trusted parties have the key. People who think about these mathematical transformations that make information secret are called cryptographers, and the whole field is called cryptography. Since with this kind of cryptography, the recipient just reverses what the sender did, it's called symmetric key cryptography.

The problem with this model is that if the secret key is compromised, you'd have to sneak a new secret key out to everyone you're communicating with. And if that wouldn't be too difficult, why not just send your messages that way?

But the whole field of cryptography was rather abruptly turned on its head with the discovery of public key cryptography (PK). PK works by using a pair of keys: a public key and a corresponding private key. Data encrypted with a public key cannot be decrypted with a public key; it can only be decrypted with the corresponding private key. Likewise, data encrypted with a private key can only be decrypted with the corresponding public key. Moreover, knowing someone's public key doesn't tell you anything about their private key, even though only one private key maps to that singular public key.

An individual, Alice let's say, will create a pair of public and private keys and distribute the public keys to absolutely everyone, even her enemies; it doesn't matter because the public key doesn't reveal any information that she isn't comfortable with everyone knowing. She keeps the private key very, very secret however and doesn't share it with anyone, even her friends. Nobody needs to know her private key. If people want to send her a secret message, they encrypt their message with her public key. Even though everyone else knows her public key, she's the only one with the private key and thus the only one who can actually read the contents of the document. If she wants to send a secure message to somebody else, she just retrieves their public key and encrypts the message with that key; nobody listening in will be able to decode the message.

A second use exists for PK; Alice can produce a unique mathematical fingerprint, called a hash, for a message that she's sending to Bob. She can then encrypt this fingerprint with her private key: this is called a signature. Now it seems a little strange at first glance to encrypt something with her private key, since anyone could decrypt it; but that's the idea. When Bob decrypts the message, he runs the hash on the decrypted text. He also decrypts Alice's signature. If the signature is the same as the hash value, then he's guaranteed that the message hasn't been altered since it left Alice; he can prove that Alice sent it.

These sorts of digital signatures are rapidly becoming legally binding as courts around the world acknowledge their security. A digital signature is much, much harder to forge than a physical signature, but in many countries (including the U.S.) documents still require a physical signature and don't yet acknowledge digital signatures.

While the algorithms involved go beyond the scope of this website, the basic concept involved is that it is difficult to factor the product of two primes. That is to say, if I pick two very large prime numbers (very large meaning hundreds of digits each) and multiply them together, it's extremely difficult, just given the product, to discover what two numbers were multiplied to produce the number that you have.