Bob & Alice & Carol & … Julius Caesar

How our modern online communications are secured

When computer networking first came along in the 1960s and 1970s it opened up wondrous new avenues and opportunities but it also created new headaches that demanded our attention. Many of them were solved in turn — like how make the network robust (via topology), reliable (via error detection and correction), and heterogeneous (thanks to protocols).

But another problem that emerged was security. Before networking became a major feature of computing, computer security was hardly the hottest topic around. As long as a computer was a standalone system, the responsibility for keeping data secure belonged to the user. That usually meant locking tapes and punched cards away in a cabinet. Passwords had been used, but when networking really landed, it thrust security to the forefront.

As soon as we started to share information between computers via networks, the information was open to interception by third parties. That might not be a problem if you’re sending a recipe for chocolate brownies, but it’s a very big problem if you’re sharing sensitive or confidential data. The first generation of network users were mostly governments and corporations, and they shared more secret stuff than they did recipes. They were understandably uncomfortable with beaming confidential data across a network via multiple intermediary parties. Hence, computer security got a whole lot hotter as a topic.

By analogy, beaming sensitive data through a network without security measures is like dispatching your cargo in an unlocked box through the mail. The package goes by way of many places and passes through lots of hands. Someone with nefarious intent could intercept it, or it may even be delivered to the wrong address. You might trust that no-one will open it along the way, but it’s simple enough for anyone who wants to. An obvious precaution would be to secure the box with a padlock. Then, even if the package does fall into the wrong hands, your enemy can’t get at the data because they don’t have a key to unlock it.

Beaming sensitive data through a network without security measures is like dispatching your cargo in an unlocked box through the mail.

How would this analogy translate to the realm of computing; specifically, what’s the equivalent of a padlock? There’s already a precedent for data security that enjoys a long history, namely encryption. We know this technique dates back at least as far as Roman times. Julius Caesar used it to protect the information in his written orders and dispatches in case they fell into enemy hands. A more recent example is the Lorenz, the German encryption machine described in an earlier article. The idea behind both techniques is the same. First, transform a readable plaintext message into unreadable gibberish called ciphertext. Second, send the message. Third, the recipient reverses the process and turns the ciphertext back into the original plaintext. The important thing is that only the sender and the recipient know the transformation procedure.

Caesar’s method became known as the Caesar Cipher and was quite simple. Every letter in a message was “shifted” a fixed number of places along the alphabet. For example, a 3-shift cipher would encrypt A into D, B into E, C into F and so on. The letters X, Y, and Z would wrap around to the beginning of the alphabet (A, B, and C respectively). Should Caesar wish to send his general, Gluteus Maximus, this message:

“I came, I saw, then I left.”

It would encrypt to:

“L fdph, L vdz, wkhq L ohiw.”

When he receives the gibberish, General Maximus — aware that the message comes from Caesar — would then know to apply the same technique in reverse to work out Caesar’s message. The critical idea here is that Caesar and Maximus know two things:

• The algorithm applied to the data (i.e., the 3-shift procedure), which is called the cipher and
• The parameter needed to make the cipher work (in this case 3), which is called the key,

In our package sending analogy, a cipher is equivalent to the padlock and a key is…well, the key.

But the Caesar Cipher approach suffers from one major flaw: it’s crap. There are several simple techniques for spotting whether the Caesar Cipher has been used to encrypt a message. For example, it’s easy to spot that each plaintext letter always encrypts to the same ciphertext letter. In addition, we know that the most commonly used letter in English is E. Therefore, the most commonly occurring letter in the ciphertext is likely to represent E. You can do the same for other letters, because each letter in English tends to occur with a reliable frequency. The second most used letter is T, which you swap for the next most common character in the ciphertext. This approach is called frequency analysis and plays out like a game of Hangman. You don’t necessarily need to decrypt every letter, because before long you’ll probably get the gist of the message.

Fast-forward two thousand years to the Second World War and encryption becomes much more sophisticated. To address the inadequacies of a Caesar Cipher, more modern ciphers like the Lorenz used a variable key. In other words, the number of positions by which each character was shifted varied throughout the message. The first character might be shifted by 3 positions, but then the second character by 9, the third character by 4 and so on. As long as an ally knows the procedure and sequence, then it’s still easy to decode. However, it makes things immensely more difficult for an enemy. Caesar’s same message might be rendered by a Lorenz like so:

“l ldol, k yia, ujfq r opgz”

The traditional techniques of code-breaking, like frequency analysis, are thus rendered useless. For instance, in the message above, the letter E has been encrypted to L, F and G all in the same message. Decrypting a Lorenz-enciphered message without the key was a massively more complex endeavour. In fact, it was so labour-intensive, the Allies needed to build computers to help them with the decryption…but then, you’ve already read about that.

When computer security became a hot topic, computer scientists gravitated towards encryption…but they inherited a field that was insufficient for their needs. Computers, the tools they were using to build their amazing networks, were the very same things that had rendered so many encryption techniques useless, thanks to their super-human processing capabilities. Whichever way they were going to improve encryption, they had to make damned sure that it was safe from the brute force of a computer attack.

Computers were the very things that had rendered so many encryption techniques useless, thanks to their super-human processing capabilities.

There was also another problem, one of a more practical nature: the distribution of keys. Using a key is fine in theory, but at some point comes the practical step of handing the key over to your friend. Sending it to your friend means the key is vulnerable to interception by an enemy. Exchanging it face-to-face might not be practical or even possible, and still risks the key being discovered. Whichever way an enemy discovers your key, it provides them with unfettered access to your encrypted messages. But in the 1970s, mathematicians and computer scientists got their hands on this long-standing problem and carried out a wonderfully elegant inversion of the problem in order to solve it.

Let’s say we have two people, Alice and Bob, sending each other messages. For whatever reason (I don’t like to pry into other people’s affairs), Alice and Bob don’t want anyone else to know what they’re saying to each other. But a third person, Carol, is intent on finding out what’s being sent between them. (Come to your own conclusions as to why this is so.) As we know, if Alice were to send a copy of her key to Bob, Carol might intercept it. Now here comes the inversion: Alice instead asks Bob to send her his open padlock. When Alice receives the padlock, she uses it to secure her package, which she then returns to Bob. Bob can unlock it with his own private key when he gets the package. In this arrangement, no keys were ever exchanged. As long as Bob keeps his key secure, the packages remain safe. When Bob wants to send a reply, he too can ask Alice for her padlock and use it to secure his package to her.

That’s the nice, neat analogy. There just remains the trifling matter of implementing it on computers, which are limited to sending electrical signals rather than packages and padlocks. The method that was developed in the seventies, and subsequently became one of the most widespread encryption methods for networks, is public-key cryptography. Under this scheme, Alice has two keys: a public key and a private key. The public key (equivalent to a padlock) can be used to encrypt a message, but only the private key can decrypt it. If Bob wishes to send Alice a message, he would ask her to send him a copy of her public key so he can encrypt a message for her eyes only. It wouldn’t matter if Carol intercepted the public key, because it would be like intercepting a padlock. It couldn’t be used to decrypt the message and only Alice has the private key that is capable of decrypting it. Alice can therefore send out copies of her public key as promiscuously as she likes. In so doing, Alice gives other people the power to create messages that only she can decrypt.

The critical idea behind public-key cryptography is to make deduction of the private key as difficult as possible.

To make this work in practice, the public and private keys have to be different but still share some underlying link, just as a key and a padlock do. But since both keys are related, there’s a risk that crafty Carol can deduce the private key from an analysis of the public key. Unfortunately, there’s no way around this. Therefore, the critical idea behind public-key cryptography is to make such deduction as difficult as possible.

To do this, the technique relies on a fundamental principle of computer science. Complexity theory tells us that problems fall into a variety of categories depending on how much time or memory space their solution requires. Some problems are computationally easy and take little or no time to solve. Others are computationally hard and no known algorithm can solve them in a feasible amount of time.

For their problem, the developers of public-key cryptography required the production of the two keys to be computationally easy, but the deduction of the private key from analysis of the public key to be computationally hard. It just so happens that prime factorisation fits this requirement nicely. A prime number, as you no doubt remember, is a number that is cleanly divisible only by itself and one. When you multiply together two large prime numbers, you get one very large non-prime number. Prime factorisation is a process whereby you work out all the possible prime numbers that could be multiplied together to make a given non-prime.

When Bob decides to communicate via public-key encryption, he needs to do a few things. First, he needs to create a key-pair. To do this, two large prime numbers are randomly chosen and together make up the private key. Then, those two numbers are multiplied together to produce one very large non-prime. This becomes the public key. Finally, of course, everyone agrees on the actual encryption algorithm to be used.

Later, when Alice wishes to send Bob a message, she can use Bob’s readily available public key in the encryption algorithm to generate the ciphertext. When Bob receives the ciphertext, he obviously needs to run the “reverse” of the encryption algorithm. However, for the algorithm to function in decrypt-mode it requires two inputs: the two original prime numbers contained in the private key. As long as Bob has been looking after his private key properly, he is the only person who knows both original primes.

Even if Carol had a supercomputer it would still take on the order of 10,000,000,000,000,000,000 years to find the key.

So why is this bad news for Carol? If she intercepted Alice’s message to Bob, she would also need to run the algorithm in decrypt-mode. However, because she doesn’t know the original prime numbers, Carol would have to deduce which two prime numbers were used to generate that very large non-prime contained in Bob’s public key. Unfortunately for Carol, doing this is a computationally hard process. When a non-prime number is very large (literally dozens of digits long), there can be millions, billions or even trillions of possible combinations of primes that could have been used. There is no known process for working out the prime factors of a very large number other than trying out all the primes one at a time.

If Carol decides to do this, then how long might it take her? A typical encryption algorithm that uses a 128-bit public key (that’s a number somewhere between 0 and about 10^38) has roughly 10^36 prime factors for Carol to test. Even if Carol had a supercomputer, checking billions of candidates every second, it would still take on the order of 10,000,000,000,000,000,000 years to try them all.

Alice and Bob’s secrets are probably safe…from Carol, at least.