Feature: Cracking Codes

WEDNESDAY, 15 MAY 2013

Recently, a dead carrier pigeon with a secret message from World War II was found during renovation of the chimney of a house in Surrey. It is believed that the message was sent from Nazioccupied Normandy in June 1944. The encrypted message has been sent to the UK Government Communications Headquarters to be deciphered, so far without success. The amount of press surrounding this incident is uncommon for a subject that usually stays out of the limelight: cryptography. The purpose of cryptography is to alter a message in such a way that it makes no sense to anyone except for the intended recipient. In the past, it was only used by governments and the military, but nowadays everyone who surfs the internet uses it, whether they know it or not.

Cryptography started with simple methods: Caesar is known to have used an encryption in which each letter of the alphabet is shifted by a fixed distance (for example, ‘message’ turns into ‘nfttbhf ’ by replacing each letter by its successor). The distance by which the letters are shifted is called the key. If the recipient knows the key, then he can easily decipher the message. The idea is, that anyone who doesn’t have access to the key has no chance of understanding the coded text. However, Caesar’s code could be easily broken if his enemy knew the method of encryption. For this reason it was necessary to invent more complex codes to ensure the security of the message. This was the beginning of the battle between friends and enemies, governments and criminals, code makers and code breakers.

By World War II, the encryption techniques had developed significantly. The Germans enciphered their messages with a mechanical coding machine called Enigma, which they thought was unbreakable. But some machines and encryption keys fell into the hands of the British forces, and so British military intelligence, first and foremost Alan Turing, were able to decipher the code and thus change the course of the war. Their effort drove the development of the first programmable electronic computer, the Colossus.

There is a method of encoding messages that is provably unbreakable: it uses a random sequence of numbers (the key) to turn the message into a string of letters which looks entirely random. Decoding the message is easy for the recipient who has access to the key, but it is impossible for anyone who doesn’t know it. Each key can only be used once—hence the name: one-time pad.

However, the one-time pad isn’t widely used. The problem that this method shares with all other encryption techniques developed before the 1970s is the distribution of keys. It was thought that encryption and decryption is a symmetric process: that the same key is needed to encrypt a message and to reverse the encryption. For this to work, both the sender and the recipient of the message have to be in possession of the same key. But as the Germans experienced in World War II, this is a risky business; keys can be lost by accident, corruption, or blackmail.

A breakthrough came with the inception of public key cryptography. Before its invention, enciphering a text was essentially a mechanical procedure, designed to muddle up the letters. However, using mathematical techniques, it is possible to design codes that are asymmetric. Every person has a pair of keys, a private key and a public key. The private key is kept secret and the public key is made available to everyone. If two people, Alice and Bill, want to have a secure conversation, they don’t have to meet in order to agree on a key. Alice just sends a message to Bill by encrypting it with Bill’s public key, and Bill uses his private key to decrypt it. The asymmetry of the mathematics working in the background ensures that the message cannot be decoded except with Bill’s secret private key.

The asymmetry behind public key cryptography is obtained by mathematical operations whose

computation is easy in one direction, but very time-consuming in the other. For instance, the RSA algorithm, named after its inventers Ron Rivest, Adi Shamir and Leonard Adleman, is a method of encryption that relies on the (very likely but as yet unproven) assumption that it is easy for computers to multiply two numbers, but it is a hard task to find the prime factors of a given integer.

Since personal computers became popular, public key cryptography has become ubiquitous. It is used in many areas of every-day life: bank cards, emails, industry, and electronic commerce. It is so effective that a message encrypted in a second could take millions of years to break using the entire computing power of all computers on Earth. In fact, the algorithm is so powerful that many governments around the world restricted its use. The US government classified encryption software as a weapon, thus making its export illegal without a licence. These restrictions have been loosened since, but in China the use of cryptographic software is still strictly regulated.

The use of cryptography has recently become important not only for governments and business, but also for individuals who want to protect their own privacy. Checking communications between people used to be a laborious activity, because opening letters and tapping phone lines cannot be done by machines. For this reason, the police only monitored people who were suspected criminals. But since the rise of the internet it has become very easy for communications to be monitored on a large scale. Using modern software it is possible to check all emails passing through a server for certain key words. If a message contains several of these key words, it can be investigated more closely. This can be exploited by illegal businesses by sending targeted scam emails. What is worse, it allows totalitarian regimes to monitor emails of political dissidents or journalists, which could lead to personal danger to the individuals and their families. Cryptography can be used to prevent such unwanted access.

At the moment, code makers seem to be the winners in the battle against code breakers. However, the advent of quantum computers will have a profound effect on the science of cryptography. So far, no practical quantum computer has been built. But when they become a reality, it will be easy for them to break the conventional codes, giving the code breakers a strong advantage. Anticipating this development, code makers have started conducting research in the direction of quantum cryptography, which aims to exploit physical properties of light, instead of general mathematical principles, in order to make secure communication possible. And so, the battle between code makers and code breakers continues.

Philipp Kleppmann is a 1st year PhD student at the Department of Pure Mathematics and Mathematical Statistics