Cryptography for Dummies

I learnt the fascinating details of modern cryptography last night. For the 12th time. Every time it fascinates me. I'm starting to think I'm like the Alzheimer's sufferer who finds new delight in the same story, over and over. What I need is the gist - the mnemonic or pattern that holds the fundamental traits firmly in the branches of my tree of knowledge, so the juicy details have a hope of straying attached to the leaves. And I thought I'd share...

Why Encrypt?

Cryptography, far from being the domain of hackers and darkened rooms, is nearly as fundamental as communication itself. Every time we send a message to someone else, by email, chat, SMS or just by talking, we're encoding our thoughts in a language that we hope the recipient can understand. Say we pick English as the language - it's great because we can be pretty sure that our English speaking contact will understand. It's not so great if others can hear it and we'd prefer they didn't understand.

So what if we do care about who understands the message we want to send? Maybe we have something private to say, or we're asking our bank how many dollars of ours they have, sharing some trade secrets or plotting a war.

If we're sensitive about who hears our message, then we have two fundamental options:

1. We can communicate in private. For example, in a sound-proof room with no microphones and only the parties of interest present.
2. We can use something other than English, which only the parties of interest understand.

Option 1 is perfect - if you can get everyone in the same, secure room and you trust them. For everything else, there's option 2. On the Internet, where so much communication happens, there is no Option 1. The Internet's great success is derived from the fact that everyone uses the same room. Messages that you send over the Internet are bounced from public computer to public computer on the way to their recipient. Those computers are supposed to only read your message for the purpose of repeating it to the next computer in the route through the Internet. But your message has to be public for the Internet to work.

So cryptography is all about creating a public message with private content. It's the study of communicating so anyone could hear the message but only the sender and receiver can understand the content.

Encryption To The Rescue

Encryption is the process of applying cryptographic techniques to a message. Decryption is the opposite, - it unwraps the cryptography to reveal the original message.

Encryption takes a plain public message - in English, say - and changes it so it's no longer easily understandable.

The simplest method of encryption is to use a code that you and your contact agree on. Sometimes close friends have a certain way of speaking that others can't understand. Or family members might have a language or dialect that others don't know. Or you might agree with your contact to swap every second letter so your messages look scrambled. In any of these cases, you come up with a way of converting your message into a "code" that is harder for others to understand. That's encryption.

This method of encryption (sometimes called encipherment) has a fundamental flaw: if an eavesdropper is determined enough, eventually they could figure out your code. They'll recognise patterns, figure out the language or encoding method being used. As soon as they do, your messages are no longer private and you wouldn't even know. It's as if your grocer thinks they can have private conversations with their staff by speaking Spanish, but you happen to have learnt Spanish. The encryption method is now useless.

Encryption, Attempt Number 2

So how do we prevent our code being figured out, or broken? We make it harder of course! Instead of using Spanish, we use Andoa, a language from Peru with only 2 remaining speakers. Or instead of swapping every second letter, we swap every letter. The problem with these methods is that they're all susceptible to pattern matching - certain words or letter combinations are common, so if you start to notice recurring patterns you can eventually figure out the code.

We need something better - something that doesn't leave patterns. Enter rolling ciphers.

A rolling cipher is just like a simply code that swaps certain letters for other certain letters. Except the pattern of letter swapping changes over time! So patterns of common letters get smeared out. And even if someone were to figure out the letter swapping pattern, the very next message would use a different pattern.

So rolling ciphers are pretty good. They are an example of shared-secret encryption. As long as you and your contact agree on an encoding method, you can make it as awfully complicated as you like and stay one step ahead of the eavesdroppers. Your contact simply applies the reverse of the encoding method that you both agreed upon, and can continue to read your messages.

But did you spot the fundamental flaw? The problem with shared-secret encryption is that they have a shared-secret. How do you communicate that shared-secret in the first place?How can you be sure that the shared-secret is still secret? What if your contact told someone else, or wrote it down and left it visible for others to see?

Probably the most famous recent example of a shared-secret encryption scheme ever used is the Enigma machine. It was used by Nazi Germany during World War II to encrypt military communication, and it was hugely successful. It had a rolling cipher whose settings changed with each message, and whose configuration changed daily according to secret key lists distributed in advance. Germany was able to plan and coordinate complex military operations, and even if the messages were intercepted they could not be understood.

The effectiveness of the Enigma machine was so great that the Allies directed a huge amount of attention to cracking it. First in Poland and France, and then in a massive operation at Bletchley Park in the United Kingdom. While the encryption scheme was good, ultimately due to the capture of some of the secret keys, and some mistakes in Germany's use of the scheme, the Allies eventually cracked the code. Many historians say this development shortened the war significantly and may even have altered its outcome.

Encryption, Fundamentally Broken?

The Enigma machine dramatically demonstrated that even a sophisticated shared-secret encryption scheme is susceptible to compromise, given enough motivation. You could continue to make the scheme more convoluted and take better care of your shared secrets, but eventually it will be broken too and all those efforts made in vain.

The situation seems hopeless - if we can't be sure we can exchange messages securely, how are we ever going to be able to exchange the shared secret securely?

Enter Whitfield Diffie and Martin Hellman.

Doing The Impossible

Diffie and Hellman are credited with devising the key exchange method that bears their names (though the method was originally conceptualised by Ralph Merkle). The implications of the method are quite extraordinary. It has been gradually improved since it was introduced in 1976, but fundamentally, all of modern encryption relies on this method. What was so mind-bendingly extraordinary about this method is that it allows two parties, who need have no prior knowledge of each other, to establish a shared secret without ever communicating that secret. Or even communicating anything that could be used by others to establish that secret.

The implications of the Diffie-Hellman key exchange seem to defy reality. How can two people come to each know a shared secret, without communicating anything that can be used to come to know that shared secret? The trick is to use asymmetric processes - processes that are very quick and easy to do one way, but very hard and slow to reverse.

Suppose our asymmetric process is mixing paint. If I take yellow paint and mix it with red paint, it will quickly turn into orange paint. If I wanted to undo the process and find out what colours went into making the orange paint, I would have to pull it apart molecule by molecule until the original colours become clear. In mathematics there are far better asymmetric processes, but mixing paint is a pretty good analogy.

Now here's how you pull off the impossible. Meet Alice and Bob. They have secrets to share. So Alice starts by telling Bob her public key is yellow. Everyone knows what the public key is. But then Alice and Bob both come up with a private key each, in secret. Suppose Alice picks red and Bob picks green. No one else knows their private keys. Now Alice and Bob both privately mix the public key with their own private key. Alice mixes yellow and red and gets orange. Bob mixes yellow and green and gets blue.

At this point Alice and Bob each have a secret (their private keys, red and green respectively) and they share a public key (yellow). They've also created a mixture each (orange and blue). Next, they publicly exchange the mixtures. That is, they tell each other what their mixtures are. Remember the mixing process is asymmetric, so even though the public key is public and the mixtures are now public, the private keys remain private. Alice and Bob now know each other's mixtures. There's one more step.

Alice takes Bob's mixture (blue) and mixes it with her private key (red) and gets brown. Bob takes Alice's mixture (orange) and mixes it with his private key (green) and gets... wait for it... brown as well! The result of mixing paint isn't affected by the order in which the paint is added. In mathematics this is called a commutative process. So Alice and Bob will always end up with the same colour as each other. They have managed to come up with a shared secret, without ever communicating enough information for anyone else to do the same.

Now that Alice and Bob have a shared secret, they are free to use it as the key to encrypt messages, knowing that only the recipient will be able to decrypt it, as long as the private keys stay private.

So Cryptography Is Based on Paint?

Mixing paint is useful analogy, but it's not very practical. Not only is it hard for computers to do, it's easy for someone to look up a colour mixing chart and see what two colours were used to make a mix. So in practice it fails the asymmetry requirement. In practice, arithmetic is used instead.

There happens to be a great candidate for an asymmetric arithmetic operation called modulo. The modulo (or mod for short) of two numbers is the remainder when one number is divided by another. For example, 12 mod 5 is 2. And 16 mod 4 is 0. The operation starts to become asymmetric when we add an exponential. For example,

10? mod 23 = 18

where 4 is the exponential, 10 is the base and 23 is the modulus. If you know the inputs (10, 4 and 23) a computer can easily calculate the output (18). But if you knew the output, as well as the 10 and the 23, a computer would have a much harder time calculating the 4. The 4 (exponential) is the private key and the 10 and 23 (base, modulus pair) are the public key.

Of course, these numbers are pretty small and computers are pretty damn quick. So it's still not very asymmetric. In practice, the numbers in the private and public keys are much, much larger. Instead of numbers like 4, 10 and 23, numbers bigger than a vigintillion (sixty three digits) are often considered a minimum. These days they often have more than six hundred digits.

Some numbers are no good - they break the commutation property so the shared secret can be generated. For example, it turns out the modulus needs to be prime. The numbers used generally have other properties too, such as being a safe prime, which all help to increase the asymmetry - very quick to calculate one way, utterly impractical to calculate back the other way.

How Impractical?

Cryptography is responsible for the security of everything from online banking to espionage to posting on Facebook. It's staggering to think that it relies not on private communications channels or guns or vaults or secret algorithms, but on well known maths being easy one way and hard the other way. So it's natural to ask - how easy, and more worryingly, how hard?

It would seem that dealing with exponentials involving numbers with hundreds of digits would be horribly intractable. 10? is already a 5 digit number and things get crazy from there. 100? is a 9 digit number and 100?? is an 81 digit number. And we're still only using 2 and 3 digit numbers as inputs. Imagine how many digits we'd have to calculate using hundred digit numbers. It would literally take thousands of years. But it turns out the maths of whole numbers gives us some amazing shortcuts. Even when doing calculations with thousand digits numbers, modular exponentiation (as it's known) is fast. On a simple Raspberry Pi with no great effort, the operation on 300 digit numbers can be done hundreds of times a second.

The reverse operation, on the other hand, is currently hard. Finding the exponent when you know the base, modulus and output takes a lot of calculating. Using the best computers we have today, again using 300 digit numbers, it would take somewhere north of 1000 million years to calculate.

Curiously, the bottleneck turns out to be factorisation. The brute-force approach to tackling the reverse operation is so infeasible, that vulnerability really only lies in indirect methods - generally methods that look at the inputs and outputs and try to find two inputs that map to the same output. If such a collision is found, then the security can theoretically be defeated indirectly.

In practice, the modulus picked in modern cryptography (the RSA algorithm) is not prime, but semiprime. That is, it is the product of two prime numbers. Doing so prevents a potential security weakness by providing what's called second-preimage resistance. That helps make collisions harder to find.

So if anyone is going to break modern cryptography, it's probably going to be by breaking down this semiprime into its two prime factors. Turns out that's really hard. It's even hard to describe correctly, as Bill Gates famously discovered when he described it like so in his 1995 book, The Road Ahead:

The obvious mathematical breakthrough would be development of an easy way to factor large prime numbers.

As I sure became painfully obvious in hindsight, this was a silly thing to say. Factoring prime numbers, large or small, is trivial. The factors of a prime number are 1 and the prime number itself, by definition. So there's already a rather easy way.

What Mr Gates probably meant to say is that it would be a breakthrough to develop an easy way to factor large semiprime numbers. And that would be a huge understatement. At the moment this is very hard - far too hard to make it practical on any computer we have today. If it were to become easy, the two prime numbers that make up the semiprime used in the public keys used in all modern cryptography could be easily found and digital security would collapse overnight.

Reattaching Branches to the Tree of Knowledge

What this all boils down to is that cryptography has always been a race to ensure that two parties can communicate private messages, as the race to eavesdrop on those communications plays catch-up. Forty years ago the good-guy race took a massive leap ahead with the discovery of a stunningly plain method that allows two parties to deduce a shared secret without ever having to communicate the shared secret, or even its ingredients.

The method ultimately relies on asymmetric processes that are nonetheless commutative - that is, processes that are much harder to do in one direction than in the opposite, but still give you the same result when you do them out of order.

While the fundamental implementation happens to be modular exponentiation, in practice the reverse process is so hard that the weakness is actually doing the forward process and discovering two inputs that create the same output. This would indirectly allow the security to be compromised. The RSA algorithm makes this very hard by requiring a semiprime public key. Again, this works because calculating a semiprime as the multiplication of two primes is a highly asymmetrical process. If it weren't, and we could deduce the two primes that make up the semiprime in some practical amount of time, then the fundamental premise of all modern cryptography would cease to exist.

Thus, modern cryptography relies on the fact that multiplication is easy but factorisation (the reverse process) is hard.

Epilogue

There's no proof that factorisation is hard. It's just that in 2500 years of research into the matter, we haven't found an easy way. So it'll probably take a fairly significant development to come up with one.

Turns out that such a significant development is already known. If quantum computers were to become practical, then an easy factorisation algorithm could be implemented. In fact, it has already been written. It's called Shor's algorithm. That means the day a quantum computer becomes practical is the day modern cryptography as we know it collapses. And so the race goes on...