The Code Book: The Secret History of Codes and Code-breaking

However, the public’s growing demand for cryptography conflicts with the needs of law enforcement and national security. For decades, the police and the intelligence services have used wire-taps to gather evidence against terrorists and organised crime syndicates, but the recent development of ultra-strong codes threatens to undermine the value of wire-taps. As we enter the twenty-first century, civil libertarians are pressing for the widespread use of cryptography in order to protect the privacy of the individual. Arguing alongside them are businesses, who require strong cryptography in order to guarantee the security of transactions within the fast-growing world of Internet commerce. At the same time, the forces of law and order are lobbying governments to restrict the use of cryptography. The question is, which do we value more – our privacy or an effective police force? Or is there a compromise?

Although cryptography is now having a major impact on civilian activities, it should be noted that military cryptography remains an important subject. It has been said that the First World War was the chemists’ war, because mustard gas and chlorine were employed for the first time, and that the Second World War was the physicists’ war, because the atom bomb was detonated. Similarly, it has been argued that the Third World War would be the mathematicians’ war, because mathematicians will have control over the next great weapon of war – information. Mathematicians have been responsible for developing the codes that are currently used to protect military information. Not surprisingly, mathematicians are also at the forefront of the battle to break these codes.

While describing the evolution of codes and their impact on history, I have allowed myself a minor detour. Chapter 5 describes the decipherment of various ancient scripts, including Linear B and Egyptian hieroglyphics. Technically, cryptography concerns communications that are deliberately designed to keep secrets from an enemy, whereas the writings of ancient civilisations were not intended to be indecipherable: it is merely that we have lost the ability to interpret them. However, the skills required to uncover the meaning of archaeological texts are closely related to the art of codebreaking. Ever since reading The Decipherment of Linear B, John Chadwick’s description of how an ancient Mediterranean text was unravelled, I have been struck by the astounding intellectual achievements of those men and women who have been able to decipher the scripts of our ancestors, thereby allowing us to read about their civilisations, religions and everyday lives.

Turning to the purists, I should apologise for the title of this book. The Code Book is about more than just codes. The word ‘code’ refers to a very particular type of secret communication, one that has declined in use over the centuries. In a code, a word or phrase is replaced with a word, number or symbol. For example, secret agents have codenames, words that are used instead of their real names in order to mask their identities. Similarly, the phrase Attack at dawn could be replaced by the codeword Jupiter, and this word could be sent to a commander in the battlefield as a way of baffling the enemy. If headquarters and the commander have previously agreed on the code, then the meaning of Jupiter will be clear to the intended recipient, but it will mean nothing to an enemy who intercepts it. The alternative to a code is a cipher, a technique that acts at a more fundamental level, by replacing letters rather than whole words. For example, each letter in a phrase could be replaced by the next letter in the alphabet, so that A is replaced by B, B by C, and so on. Attack at dawn thus becomes Buubdl bu ebxo. Ciphers play an integral role in cryptography, and so this book should really have been called The Code and Cipher Book. I have, however, forsaken accuracy for snappiness.

As the need arises, I have defined the various technical terms used within cryptography. Although I have generally adhered to these definitions, there will be occasions when I use a term that is perhaps not technically accurate, but which I feel is more familiar to the nonspecialist. For example, when describing a person attempting to break a cipher, I have often used codebreaker rather than the more accurate cipherbreaker. I have done this only when the meaning of the word is obvious from the context. There is a glossary of terms at the end of the book. More often than not, though, crypto-jargon is quite transparent: for example, plaintext is the message before encryption, and ciphertext is the message after encryption.

Before concluding this introduction, I must mention a problem that faces any author who tackles the subject of cryptography: the science of secrecy is largely a secret science. Many of the heroes in this book never gained recognition for their work during their lifetimes because their contribution could not be publicly acknowledged while their invention was still of diplomatic or military value. While researching this book, I was able to talk to experts at Britain’s Government Communications Headquarters (GCHQ), who revealed details of extraordinary research done in the 1970s which has only just been declassified. As a result of this declassification, three of the world’s greatest cryptographers can now receive the credit they deserve. However, this recent revelation has merely served to remind me that there is a great deal more going on, of which neither I nor any other science writer is aware. Organisations such as GCHQ and America’s National Security Agency continue to conduct classified research into cryptography, which means that their breakthroughs remain secret and the individuals who make them remain anonymous.

Despite the problems of government secrecy and classified research, I have spent the final chapter of this book speculating about the future of codes and ciphers. Ultimately, this chapter is an attempt to see if we can predict who will win the evolutionary struggle between codemaker and codebreaker. Will codemakers ever design a truly unbreakable code and succeed in their quest for absolute secrecy? Or will codebreakers build a machine that can decipher any message? Bearing in mind that some of the greatest minds work in classified laboratories, and that they receive the bulk of research funds, it is clear that some of the statements in my final chapter may be inaccurate. For example, I state that quantum computers – machines potentially capable of breaking all today’s ciphers – are at a very primitive stage, but it is possible that somebody has already built one. The only people who are in a position to point out my errors are also those who are not at liberty to reveal them.

1 The Cipher of Mary Queen of Scots

On the morning of Saturday 15 October 1586, Queen Mary entered the crowded courtroom at Fotheringhay Castle. Years of imprisonment and the onset of rheumatism had taken their toll, yet she remained dignified, composed and indisputably regal. Assisted by her physician, she made her way past the judges, officials and spectators, and approached the throne that stood halfway along the long, narrow chamber. Mary had assumed that the throne was a gesture of respect towards her, but she was mistaken. The throne symbolised the absent Queen Elizabeth, Mary’s enemy and prosecutor. Mary was gently guided away from the throne and towards the opposite side of the room, to the defendant’s seat, a crimson velvet chair.

Mary Queen of Scots was on trial for treason. She had been accused of plotting to assassinate Queen Elizabeth in order to take the English crown for herself. Sir Francis Walsingham, Elizabeth’s Principal Secretary, had already arrested the other conspirators, extracted confessions, and executed them. Now he planned to prove that Mary was at the heart of the plot, and was therefore equally culpable and equally deserving of death.

Figure 1 Mary Queen of Scots.

Scottish National Portrait Gallery, Edinburgh;

Walsingham knew that before he could have Mary executed, he would have to convince Queen Elizabeth of her guilt. Although Elizabeth despised Mary, she had several reasons for being reluctant to see her put to death. First, Mary was a Scottish queen, and many questioned whether an English court had the authority to execute a foreign head of state. Second, executing Mary might establish an awkward precedent – if the state is allowed to kill one queen, then perhaps rebels might have fewer reservations about killing another, namely Elizabeth. Third, Elizabeth and Mary were cousins, and their blood tie made Elizabeth all the more squeamish about ordering her execution. In short, Elizabeth would sanction Mary’s execution only if Walsingham could prove beyond any hint of doubt that she had been part of the assassination plot.

The conspirators were a group of young English Catholic noblemen intent on removing Elizabeth, a Protestant, and replacing her with Mary, a fellow Catholic. It was apparent to the court that Mary was a figurehead for the conspirators, but it was not clear that she had actually given her blessing to the conspiracy. In fact, Mary had authorised the plot. The challenge for Walsingham was to demonstrate a palpable link between Mary and the plotters.

On the morning of her trial, Mary sat alone in the dock, dressed in sorrowful black velvet. In cases of treason, the accused was forbidden counsel and was not permitted to call witnesses. Mary was not even allowed secretaries to help her prepare her case. However, her plight was not hopeless because she had been careful to ensure that all her correspondence with the conspirators had been written in cipher. The cipher turned her words into a meaningless series of symbols, and Mary believed that even if Walsingham had captured the letters, then he could have no idea of the meaning of the words within them. If their contents were a mystery, then the letters could not be used as evidence against her. However, this all depended on the assumption that her cipher had not been broken.

Unfortunately for Mary, Walsingham was not merely Principal Secretary, he was also England’s spymaster. He had intercepted Mary’s letters to the plotters, and he knew exactly who might be capable of deciphering them. Thomas Phelippes was the nation’s foremost expert on breaking codes, and for years he had been deciphering the messages of those who plotted against Queen Elizabeth, thereby providing the evidence needed to condemn them. If he could decipher the incriminating letters between Mary and the conspirators, then her death would be inevitable. On the other hand, if Mary’s cipher was strong enough to conceal her secrets, then there was a chance that she might survive. Not for the first time, a life hung on the strength of a cipher.

The Evolution of Secret Writing

Some of the earliest accounts of secret writing date back to Herodotus, ‘the father of history’ according to the Roman philosopher and statesman Cicero. In The Histories, Herodotus chronicled the conflicts between Greece and Persia in the fifth century BC, which he viewed as a confrontation between freedom and slavery, between the independent Greek states and the oppressive Persians. According to Herodotus, it was the art of secret writing that saved Greece from being conquered by Xerxes, King of Kings, the despotic leader of the Persians.

The long-running feud between Greece and Persia reached a crisis soon after Xerxes began constructing a city at Persepolis, the new capital for his kingdom. Tributes and gifts arrived from all over the empire and neighbouring states, with the notable exceptions of Athens and Sparta. Determined to avenge this insolence, Xerxes began mobilising a force, declaring that ‘we shall extend the empire of Persia such that its boundaries will be God’s own sky, so the sun will not look down upon any land beyond the boundaries of what is our own’. He spent the next five years secretly assembling the greatest fighting force in history, and then, in 480 BC, he was ready to launch a surprise attack.

However, the Persian military build-up had been witnessed by Demaratus, a Greek who had been expelled from his homeland and who lived in the Persian city of Susa. Despite being exiled he still felt some loyalty to Greece, so he decided to send a message to warn the Spartans of Xerxes’ invasion plan. The challenge was how to dispatch the message without it being intercepted by the Persian guards. Herodotus wrote:

As the danger of discovery was great, there was only one way in which he could contrive to get the message through: this was by scraping the wax off a pair of wooden folding tablets, writing on the wood underneath what Xerxes intended to do, and then covering the message over with wax again. In this way the tablets, being apparently blank, would cause no trouble with the guards along the road. When the message reached its destination, no one was able to guess the secret, until, as I understand, Cleomenes’ daughter Gorgo, who was the wife of Leonidas, divined and told the others that if they scraped the wax off, they would find something written on the wood underneath. This was done; the message was revealed and read, and afterwards passed on to the other Greeks.

As a result of this warning, the hitherto defenceless Greeks began to arm themselves. Profits from the state-owned silver mines, which were usually shared among the citizens, were instead diverted to the navy for the construction of two hundred warships.

Xerxes had lost the vital element of surprise and, on 23 September 480 BC, when the Persian fleet approached the Bay of Salamis near Athens, the Greeks were prepared. Although Xerxes believed he had trapped the Greek navy, the Greeks were deliberately enticing the Persian ships to enter the bay. The Greeks knew that their ships, smaller and fewer in number, would have been destroyed in the open sea, but they realised that within the confines of the bay they might outmanoeuvre the Persians. As the wind changed direction the Persians found themselves being blown into the bay, forced into an engagement on Greek terms. The Persian princess Artemisia became surrounded on three sides and attempted to head back out to sea, only to ram one of her own ships. Panic ensued, more Persian ships collided and the Greeks launched a full-blooded onslaught. Within a day, the formidable forces of Persia had been humbled.

Demaratus’ strategy for secret communication relied on simply hiding the message. Herodotus also recounted another incident in which concealment was sufficient to secure the safe passage of a message. He chronicled the story of Histaiaeus, who wanted to encourage Aristagoras of Miletus to revolt against the Persian king. To convey his instructions securely, Histaiaeus shaved the head of his messenger, wrote the message on his scalp, and then waited for the hair to regrow. This was clearly a period of history that tolerated a certain lack of urgency. The messenger, apparently carrying nothing contentious, could travel without being harassed. Upon arriving at his destination he then shaved his head and pointed it at the intended recipient.

Secret communication achieved by hiding the existence of a message is known as steganography, derived from the Greek words steganos, meaning ‘covered’, and graphein, meaning ‘to write’. In the two thousand years since Herodotus, various forms of steganography have been used throughout the world. For example, the ancient Chinese wrote messages on fine silk, which was then scrunched into a tiny ball and covered in wax. The messenger would then swallow the ball of wax. In the sixteenth century, the Italian scientist Giovanni Porta described how to conceal a message within a hard-boiled egg by making an ink from a mixture of one ounce of alum and a pint of vinegar, and then using it to write on the shell. The solution penetrates the porous shell, and leaves a message on the surface of the hardened egg albumen, which can be read only when the shell is removed. Steganography also includes the practice of writing in invisible ink. As far back as the first century AD, Pliny the Elder explained how the ‘milk’ of the thithymalus plant could be used as an invisible ink. Although transparent after drying, gentle heating chars the ink and turns it brown. Many organic fluids behave in a similar way, because they are rich in carbon and therefore char easily. Indeed, it is not unknown for modern spies who have run out of standard-issue invisible ink to improvise by using their own urine.

The longevity of steganography illustrates that it certainly offers a modicum of security, but it suffers from a fundamental weakness. If the messenger is searched and the message is discovered, then the contents of the secret communication are revealed at once. Interception of the message immediately compromises all security. A thorough guard might routinely search any person crossing a border, scraping any wax tablets, heating blank sheets of paper, shelling boiled eggs, shaving people’s heads, and so on, and inevitably there will be occasions when the message is uncovered.

Hence, in parallel with the development of steganography, there was the evolution of cryptography, derived from the Greek word kryptos, meaning ‘hidden’. The aim of cryptography is not to hide the existence of a message, but rather to hide its meaning, a process known as encryption. To render a message unintelligible, it is scrambled according to a particular protocol which is agreed beforehand between the sender and the intended recipient. Thus the recipient can reverse the scrambling protocol and make the message comprehensible. The advantage of cryptography is that if the enemy intercepts an encrypted message, then the message is unreadable. Without knowing the scrambling protocol, the enemy should find it difficult, if not impossible, to recreate the original message from the encrypted text.

Although cryptography and steganography are independent, it is possible to both scramble and hide a message to maximise security. For example, the microdot is a form of steganography that became popular during the Second World War. German agents in Latin America would photographically shrink a page of text down to a dot less than 1 millimetre in diameter, and then hide this microdot on top of a full stop in an apparently innocuous letter. The first microdot to be spotted by the FBI was in 1941, following a tip-off that the Americans should look for a tiny gleam from the surface of a letter, indicative of smooth film. Thereafter, the Americans could read the contents of most intercepted microdots, except when the German agents had taken the extra precaution of scrambling their message before reducing it. In such cases of cryptography combined with steganography, the Americans were sometimes able to intercept and block communications, but they were prevented from gaining any new information about German spying activity. Of the two branches of secret communication, cryptography is the more powerful because of this ability to prevent information from falling into enemy hands.

In turn, cryptography itself can be divided into two branches, known as transposition and substitution. In transposition, the letters of the message are simply rearranged, effectively generating an anagram. For very short messages, such as a single word, this method is relatively insecure because there are only a limited number of ways of rearranging a handful of letters. For example, three letters can be arranged in only six different ways, e.g. cow, cwo, ocw, owc, wco, woc. However, as the number of letters gradually increases, the number of possible arrangements rapidly explodes, making it impossible to get back to the original message unless the exact scrambling process is known. For example, consider this short sentence. It contains just 35 letters, and yet there are more than 50,000,000,000,000,000,000,000,000,000,000 distinct arrangements of them. If one person could check one arrangement per second, and if all the people in the world worked night and day, it would still take more than a thousand times the lifetime of the universe to check all the arrangements.

A random transposition of letters seems to offer a very high level of security, because it would be impractical for an enemy interceptor to unscramble even a short sentence. But there is a drawback. Transposition effectively generates an incredibly difficult anagram, and if the letters are randomly jumbled, with neither rhyme nor reason, then unscrambling the anagram is impossible for the intended recipient, as well as an enemy interceptor. In order for transposition to be effective, the rearrangement of letters needs to follow a straightforward system, one that has been previously agreed by sender and receiver, but kept secret from the enemy. For example, schoolchildren sometimes send messages using the ‘rail fence’ transposition, in which the message is written with alternate letters on separate upper and lower lines. The sequence of letters on the lower line is then tagged on at the end of the sequence on the upper line to create the final encrypted message. For example:

The receiver can recover the message by simply reversing the process. There are various other forms of systematic transposition, including the three-line rail fence cipher, in which the message is first written on three separate lines instead of two. Alternatively, one could swap each pair of letters, so that the first and second letters switch places, the third and fourth letters switch places, and so on.

Figure 2 When it is unwound from the sender’s scytale (wooden staff), the leather strip appears to carry a list of random letters; S, T, S, F, …. Only by rewinding the strip around another scytale of the correct diameter will the message reappear.

Another form of transposition is embodied in the first ever military cryptographic device, the Spartan scytale, dating back to the fifth century BC. The scytale is a wooden staff around which a strip of leather or parchment is wound, as shown in Figure 2. The sender writes the message along the length of the scytale, and then unwinds the strip, which now appears to carry a list of meaningless letters. The message has been scrambled. The messenger would take the leather strip, and, as a steganographic twist, he would sometimes disguise it as a belt with the letters hidden on the inside. To recover the message, the receiver simply wraps the leather strip around a scytale of the same diameter as the one used by the sender. In 404 BC Lysander of Sparta was confronted by a messenger, bloody and battered, one of only five to have survived the arduous journey from Persia. The messenger handed his belt to Lysander, who wound it around his scytale to learn that Pharnabazus of Persia was planning to attack him. Thanks to the scytale, Lysander was prepared for the attack and repulsed it.

The alternative to transposition is substitution. One of the earliest descriptions of encryption by substitution appears in the K

ma-s

tra, a text written in the fourth century AD by the Brahmin scholar V

tsy

yana, but based on manuscripts dating back to the fourth century BC. The K

ma-s

tra recommends that women should study 64 arts, such as cooking, dressing, massage and the preparation of perfumes. The list also includes some less obvious arts, namely conjuring, chess, bookbinding and carpentry. Number 45 on the list is mlecchita-vikalp

, the art of secret writing, advocated in order to help women conceal the details of their liaisons. One of the recommended techniques is to pair letters of the alphabet at random, and then substitute each letter in the original message with its partner. If we apply the principle to the Roman alphabet, we could pair letters as follows:

Then, instead of meet at midnight, the sender would write CUUZ VZ CGXSGIBZ. This form of secret writing is called a substitution cipher because each letter in the plaintext is substituted for a different letter, thus acting in a complementary way to the transposition cipher. In transposition each letter retains its identity but changes its position, whereas in substitution each letter changes its identity but retains its position.

The first documented use of a substitution cipher for military purposes appears in Julius Caesar’s Gallic Wars. Caesar describes how he sent a message to Cicero, who was besieged and on the verge of surrendering. The substitution replaced Roman letters with Greek letters, rendering the message unintelligible to the enemy. Caesar described the dramatic delivery of the message:

The messenger was instructed, if he could not approach, to hurl a spear, with the letter fastened to the thong, inside the entrenchment of the camp. Fearing danger, the Gaul discharged the spear, as he had been instructed. By chance it stuck fast in the tower, and for two days was not sighted by our troops; on the third day it was sighted by a soldier, taken down, and delivered to Cicero. He read it through and then recited it at a parade of the troops, bringing the greatest rejoicing to all.

Plain alphabet a b c d e f g h i j k l m n o p q r s t u v w x y z

Cipher alphabet D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

Plaintext v e n i, v i d i, v i c i

Ciphertext Y H Q L, Y L G L, Y L F L

Figure 3 The Caesar cipher applied to a short message. The Caesar cipher is based on a cipher alphabet that is shifted a certain number of places (in this case three), relative to the plain alphabet. The convention in cryptography is to write the plain alphabet in lower-case letters, and the cipher alphabet in capitals. Similarly, the original message, the plaintext, is written in lower case, and the encrypted message, the ciphertext, is written in capitals.

Caesar used secret writing so frequently that Valerius Probus wrote an entire treatise on his ciphers, which unfortunately has not survived. However, thanks to Suetonius’ Lives of the Caesars LVI, written in the second century AD, we do have a detailed description of one of the types of substitution cipher used by Julius Caesar. He simply replaced each letter in the message with the letter that is three places further down the alphabet. Cryptographers often think in terms of the plain alphabet, the alphabet used to write the original message, and the cipher alphabet, the letters that are substituted in place of the plain letters. When the plain alphabet is placed above the cipher alphabet, as shown in Figure 3, it is clear that the cipher alphabet has been shifted by three places, and hence this form of substitution is often called the Caesar shift cipher, or simply the Caesar cipher. A cipher is the name given to any form of cryptographic substitution in which each letter is replaced by another letter or symbol.