Secret codes

The simplest ciphers swap each letter for a stand-in, always the same one, and leave every letter where it was. This is a substitution cipher. One of the oldest on record belonged to Julius Caesar. The Roman historian Suetonius tells us that when Caesar wrote something confidential, he replaced each letter with the one three places further along the alphabet.

Written in our alphabet, A becomes D, B becomes E, and the alphabet wraps round at the end, so X becomes A and Z becomes C. The plaintext HELLO comes out as KHOOR. The reader undoes it by moving every letter three places back. To anyone who intercepts it, KHOOR is nonsense, but only until they work out the shift.

Every cipher has two parts. The method is how it works in general, such as shifting each letter along the alphabet. The key is the secret setting that picks out one particular cipher from that method: for Caesar, the number three. Sender and receiver must both hold the key, and anyone else who gets it can read everything.

Caesar's cipher has very few keys. In a twenty-six-letter alphabet a shift of twenty-six brings every letter back to itself, so only twenty-five shifts hide anything. An enemy who suspects the method can simply try each shift until the message makes sense. Trying every possible key in turn is called brute force, and against twenty-five keys it takes a few minutes with a pencil. A cipher with so few keys has no defence against it.

Suppose the cipher alphabet is not a shift but a full scramble, where any letter may stand for any other. Now the key is the whole scrambled alphabet, and counting the possible keys is a matter of multiplying. A can be given any of 26 stand-ins, B any of the 25 left, C any of 24, and so on down to 1. That product is written 26 factorial, and it comes to about 4 followed by 26 zeros.

The set of every key a cipher could use is its keyspace, and this one holds far too many keys to try. A computer testing a billion keys every second would need nearly thirteen billion years to get through them all, close to the age of the universe. Brute force is hopeless here. Yet a scholar in ninth-century Baghdad showed how to break this cipher by hand.

The scholar al-Kindī, who worked in ninth-century Baghdad, wrote a treatise On Deciphering Cryptographic Messages, the earliest known account of breaking a cipher without its key. His insight was that a substitution cipher changes what each letter looks like, but not how often each letter appears.

His method, now called frequency analysis, runs like this. Take a long plaintext in the same language, count how often each letter occurs, and rank the letters from most to least common. Then count and rank the symbols in the secret message. The most common symbol probably stands for the language's most common letter, the next for the next, and so on down the list. A few pairings come out wrong, but enough fall into place for words to appear, and the words fix the rest. The size of the keyspace never comes into it.

Frequency analysis works because every language uses its letters unevenly, and in much the same uneven way from one long text to the next. In English, E makes up about 13 per cent of ordinary writing, roughly one letter in eight, with T at about 9 per cent and A at about 8. Z turns up less than once in a thousand letters. These letter frequencies work like a fingerprint.

Al-Kindī counted Arabic, from a sample of 3,667 letters. Alif came first by a clear margin, then lām, then mīm. Together they spell al-, the definite article, which is part of why they lead.

A fingerprint needs a long enough text to show. A message of a few words can rank its letters in almost any order, and in the thirteenth century Ibn ʿAdlān set a minimum length for a message worth attacking this way.

Once letters could be counted, any cipher that gave each letter one fixed stand-in could be broken. The way out was to give each letter many. Around 1467 the Italian scholar Leon Battista Alberti described a cipher disk: two rings of letters, one turning inside the other. Set the inner ring one way and every plaintext letter lines up with one cipher letter; turn it, and every pairing changes.

Alberti turned his disk every three or four words, so the same plaintext letter was written differently in different parts of the message. A cipher that switches between several alphabets like this is a polyalphabetic cipher. It flattens the letter frequencies: the common E is shared out among several cipher letters, so no single symbol towers over the rest the way E does in English.

In 1553 the Italian Giovan Battista Bellaso published a tidier way to switch alphabets. Sender and receiver agree on a secret keyword, and each of its letters sets how far one letter of the message shifts. With the keyword LEMON, counting A as zero, the first letter moves eleven places for L, the second four for E, and so on to the end of the word, when the keyword starts again from the top.

It was later credited to the Frenchman Blaise de Vigenère and still carries his name, and for three centuries it had a reputation as the indecipherable cipher. Its flaw was that the keyword keeps repeating: with five letters in the keyword, every fifth letter of the message uses the same shift. In 1863 Friedrich Kasiski published how to find the keyword's length. Split the message into that many strands, and each strand falls to letter counting.

If a repeating key is the weakness, the cure is a key that never repeats. A one-time pad uses a key as long as the message itself, made of truly random letters, and uses it only once. Each plaintext letter gets its own random shift, so every letter of the ciphertext is equally likely to be any letter of the alphabet, one chance in twenty-six. However long the message, no pattern is left to count.

In the 1940s the mathematician Claude Shannon proved that a cipher like this cannot be broken, even with unlimited time and computing power. Every plaintext of the right length is equally possible. That guarantee holds only while the rules are kept: the key must be truly random, as long as the message, secret, and never used twice.

The one-time pad has a heavy price. Both sides need pads as long as all their messages put together, carried to them in secret beforehand, and every page must be destroyed after one use.

Reuse brings the pattern back. Take two messages sent with the same page, subtract one from the other letter by letter, and the random key cancels out, leaving the two plaintexts tangled together, and ordinary language is predictable enough to pull them apart. This is exactly what happened to the Soviet Union during the Second World War. Pressed by the German advance on Moscow, the factory making its pads printed tens of thousands of pages twice. American codebreakers on the Venona project, which began in 1943, spotted the repeats and read about three thousand messages, in whole or in part.

In 1883 the Dutch linguist Auguste Kerckhoffs, writing about ciphers for armies, set down a rule that designers still follow. A cipher should not depend on keeping its method secret. It must stay safe even if the method falls into enemy hands, so that only the key needs hiding. This is Kerckhoffs's principle.

The reasoning is practical. A method lives in machines, manuals and people's training, so sooner or later it leaks, through a captured device or a traitor, and replacing it is slow. A key is small, and easily changed in a day. So a cipher should be judged as if the enemy already knows exactly how it works. Modern ciphers are published openly for exactly this reason, so that anyone can try to break them.

Every cipher so far shares one weakness at the start: sender and receiver must already hold the same secret key. Armies and embassies sent keys by trusted courier, but on the internet millions of strangers need to talk safely without ever meeting. This is the key-exchange problem.

In 1976 Whitfield Diffie and Martin Hellman published a way round it, and in 1977 Ron Rivest, Adi Shamir and Leonard Adleman built a full system, now called RSA. In public-key cryptography each person has two keys. The public key locks messages and can be handed to anyone. The private key unlocks them and never leaves its owner. It works like handing out open padlocks: anyone can snap one shut on a box for you, but only you hold the key that opens it.

A public key can go to everyone only if nobody can work backwards from it to the private key. RSA gets that from a one-way function, a calculation that is quick to do and very hard to undo.

Its one-way function is multiplying primes, the whole numbers that only 1 and themselves divide exactly. Multiplying 61 by 53 to get 3,233 takes a minute by hand. Going back, from 3,233 to the two primes that made it, means trying one divisor after another. Real keys use primes hundreds of digits long, whose product runs to over six hundred digits. The public key contains that product, and the private key is built from its two prime factors. A computer multiplies them in a blink, but no known method on today's computers can find them again in any useful time.