Public Key Cryptography for Everyone
Imagine you want to send a letter to a complete stranger in a way that no one else can understand it. If you could meet with this person privately, even just once, this would be easy. The two of you could agree on a random ordering of the 26 letters in the English language, and swap the letters you’re writing accordingly. For example, if you agree on
paxgqbrhjitzokcsdmywvefuln
Then the sentence ‘This is really secret’ would become ‘Whjy jh mqpzzl yqxmqw’. This simple cipher technique, which incidentally appears in the kama-sutra as a way for women to write secretly to their lovers, wouldn’t be secure enough for the military, but it would keep the postman from reading your letter.
What if you can’t meet the person beforehand, though? If you can’t meet them, then you can’t agree on a secret key. If you can’t agree on a secret key, then anything you send will either be easy for anyone to read, or just as hard for the recipient to read as it is for anyone else.
Your position might appear impossible, but you do this every day. When you log on to your online bank account, you send a ‘stranger’ vital information: your account name and password. Anyone who intercepts this data could access all your assets. Yet you send this data off without giving it a second thought. You can do this because clever mathematicians came up with a system called public key cryptography.
Public key cryptography can be thought of as a locked mailbox.
Remember, you want to send a letter to a complete stranger in a way that no one else can read it. If the stranger has a locked mailbox, and anyone can deposit a letter but only the owner has the key, then this is easy. By making the location of the mailbox public, anyone in the world deliver a letter with complete privacy. Let’s take this remarkably simple task and see if we can turn it into a sort of algorithm that your bank could use to keep your information safe:
Step 1. Have a mailbox. Your bank needs an equivalent of a locked mailbox, which only they can open.
Step 2. Put a letter in the mailbox. In this case the ‘letter’, is your account information, and all you need is a way to put that letter in your bank’s ‘mailbox’.
Step 3. Take the letter out of the mailbox. This step is crucial — your bank has to be able to open the mailbox and read your letter. The bank needs a sort of ‘key’.
These three steps suggest an elegant approach to the problem: Your bank publishes an encryption algorithm, but they keep the key to decrypting the answer secret. Anyone can encrypt information and send it to your bank using the public algorithm, but only the bank can decrypt what they receive. This set-up is what constitutes public key cryptography. The bank’s published algorithm functions as a “public key”, but in order to keep the information safe the bank has another, “private key”, which they don’t share.
Such encryption schemes are called “asymmetric”. See the asymmetry? Our first example of a simple cipher was symmetric — if you knew how to encrypt a message, then you also knew how to decrypt it. The same key was used for both processes. The beauty of asymmetric encryption is that even with sufficient information to encrypt a message, it is still not possible to decrypt one.
This all sounds good, but can you actually construct such a scheme? Since computers think in 0s and 1s, what we need is a process of modifying (encrypting) numbers which is easy to do, but extremely hard to undo. Further, we need decryption to be easy if we have some additional secret information. Finally, we need the secret key to be nearly impossible to attain, even for someone who knows how to encrypt a message.
All of this seems daunting, but it isn’t. There are beautiful and simple solutions in the world of number theory. If you want to get your hands dirty with the mathematics, then go read about RSA. Also, stay tuned for my planned follow-up article where I’ll go through the details in an approachable way.
