The Cracking Code Book

The birth of cryptography, the substitution cipher and the invention of codebreaking by frequency analysis

On the morning of Saturday, October 15, 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 symbolized 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 to blame and equally deserving of death.

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. Firstly, Mary was a Scottish queen, and many questioned whether an English court had the authority to execute a foreign head of state. Secondly, 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. Finally, Elizabeth and Mary were cousins, and their blood tie made Elizabeth all the more squeamish about ordering the 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 given her blessing to the conspiracy. In fact, Mary had authorized the plot. The challenge for Walsingham was to demonstrate a clear 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, 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, but 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 nations 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, 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 mobilizing 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 September 23, 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 realized 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 not an urgent message. 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 scrunched into a tiny ball and covered in wax. The messenger would then swallow the ball of wax. 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 tithymalus plant could be used as an invisible ink. Although the ink is transparent after drying, gentle heating chars it 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 some degree 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, shaving people’s heads, and so on, and inevitably there will be occasions when a message is uncovered.

Hence, along with the development of steganography, there was the evolution of cryptography (the word is derived from the Greek 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, the message is unreadable. Without knowing the scrambling protocol, the enemy should find it difficult, if not impossible, to re-create the original message from the encrypted text.

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 thirty-five 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 for 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, it is possible to send messages using the “rail fence” transposition, in which the message is written with alternating 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:

THY SECRET IS THY PRISONER; IF THOU LET IT GO, THOU ART A PRISONER TO IT

↓

↓

TYERTSHPIOEITOLTTOHURARSNROTHSCEITYRSNRFHUEIGTOATPIOETI

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 (#litres_trial_promo). 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.

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.

In 404 BC Lysander of Sparta was confronted by a messenger, bloody and battered, the only one of five to have survived the difficult 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 successfully resisted 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 sixty-four arts, such as cooking, dressing, massage and the preparation of perfumes. The list also includes some less obvious arts, including conjuring, chess, bookbinding and carpentry. Number forty-five on the list is mlecchita-vikalpā the art of secret writing, recommended 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 English 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 (the message before encryption) is substituted for a different letter to produce the ciphertext (the message after encryption), 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 Caesars 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, making 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.

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 (#litres_trial_promo), 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. Cipher is the name given to any form of cryptographic substitution in which each letter is replaced by another letter or symbol.

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.

Although Suetonius mentions only a Caesar shift of three places, it is clear that by using any shift between one and twenty-five places, it is possible to generate twenty-five distinct ciphers. In fact, if we do not restrict ourselves to shifting the alphabet and permit the cipher alphabet to be any rearrangement of the plain alphabet, then we can generate an even greater number of distinct ciphers. There are over 400,000,000,000,000,000,000,000,000 such rearrangements, and therefore the same number of distinct ciphers.

Each distinct cipher can be considered in terms of a general encrypting method, known as the algorithm, and a key, which specifies the exact details of a particular encryption. In this case, the algorithm involves substituting each letter in the plain alphabet with a letter from a cipher alphabet, and the cipher alphabet is allowed to consist of any rearrangement of the plain alphabet. The key defines the exact cipher alphabet to be used for a particular encryption. The relationship between the algorithm and the key is illustrated in Figure 4 (#litres_trial_promo).

Figure 4 To encrypt a plaintext message, the sender passes it through an encryption algorithm. The algorithm is a general system for encryption, and needs to be specified exactly by selecting a key. Applying the key and algorithm together to a plaintext generates the encrypted message, or ciphertext. The ciphertext may be intercepted by an enemy while it is being transmitted to the receiver, but the enemy should not be able to decipher the message. However, the receiver, who knows both the key and the algorithm used by the sender, is able to turn the ciphertext back into the plaintext message.

An enemy studying an intercepted scrambled message may have a strong suspicion of the algorithm but would not know the exact key. For example, they may well suspect that each letter in the plaintext has been replaced by a different letter according to a particular cipher alphabet, but they are unlikely to know which cipher alphabet has been used. If the cipher alphabet, the key, is kept a closely guarded secret between the sender and the receiver, then the enemy cannot decipher the intercepted message. The significance of the key, as opposed to the algorithm, is an enduring principle of cryptography. It was definitively stated in 1883 by the Dutch linguist Auguste Kerckhoffs von Nieuwenhof in his book La Cryptographie Militaire: “Kerckhoffs’ Principle: the security of a cryptosystem must not depend on keeping secret the crypto-algorithm. The security depends only on keeping secret the key.”

In addition to keeping the key secret, a secure cipher system must also have a wide range of potential keys. For example, if the sender uses the Caesar shift cipher to encrypt a message, then encryption is relatively weak because there are only twenty-five potential keys. From the enemy’s point of view, if they intercept the message and suspect that the algorithm being used is the Caesar shift, then they merely have to check the twenty-five possible keys. However, if the sender uses the more general substitution algorithm, which permits the cipher alphabet to be any rearrangement of the plain alphabet, then there are 400,000,000,000,000,000,000,000,000 possible keys from which to choose. One such is shown in Figure 5 (#ulink_e5c03f66-a7bb-553a-ab2d-ba5266469a7f). From the enemy’s point of view, even if the message is intercepted and the algorithm is known, there is still the horrendous task of checking all possible keys. If an enemy agent were able to check one of the 400,000,000,000,000,000,000,000,000 possible keys every second, it would take roughly a billion times the lifetime of the universe to check all of them and decipher the message.

Figure 5 An example of the general substitution algorithm, in which each letter in the plaintext is substituted with another letter according to a key. The key is defined by the cipher alphabet, which can be any rearrangement of the plain alphabet.

The beauty of this type of cipher is that it is easy to implement but provides a high level of security. It is easy for the sender to define the key, which consists merely of stating the order of the twenty-six letters in the rearranged cipher alphabet, and yet it is effectively impossible for the enemy to check all possible keys by the so-called brute-force attack. The simplicity of the key is important, because the sender and receiver have to share knowledge of the key, and the simpler the key, the less the chance of a misunderstanding.

In fact, an even simpler key is possible if the sender is prepared to accept a slight reduction in the number of potential keys. Instead of randomly rearranging the plain alphabet to achieve the cipher alphabet, the sender chooses a keyword or keyphrase. For example, to use JULIUS CAESAR as a keyphrase, begin by removing any spaces and repeated letters (JULISCAER), and then use this as the beginning of the jumbled cipher alphabet. The remainder of the cipher alphabet is merely the remaining letters of the alphabet, in their correct order, starting where the keyphrase ends. Hence, the cipher alphabet would read as follows:

The advantage of building a cipher alphabet in this way is that it is easy to memorize the keyword or keyphrase, and hence the cipher alphabet. This is important, because if the sender has to keep the cipher alphabet on a piece of paper, the enemy can capture the paper, discover the key and read any communications that have been encrypted with it. However, if the key can be committed to memory, it is less likely to fall into enemy hands.

This simplicity and strength meant that the substitution cipher dominated the art of secret writing throughout the first millennium AD. Codemakers had evolved a system for guaranteeing secure communication, so there was no need for further development – without necessity, there was no need for invention. The onus had fallen upon the codebreakers, those who were attempting to crack the substitution cipher. Was there any way for an enemy interceptor to unravel an encrypted message? Many ancient scholars considered that the substitution cipher was unbreakable, thanks to the gigantic number of possible keys, and for centuries this seemed to be true. However, codebreakers would eventually find a shortcut to the process of exhaustively searching through all the keys. Instead of taking billions of years to crack a cipher, the shortcut could reveal the message in a matter of minutes. The breakthrough occurred in the East and required a brilliant combination of linguistics, statistics and religious devotion.

THE ARAB CRYPTANALYSTS

At the age of about forty, Muhammad began regularly visiting an isolated cave on Mount Hira just outside Mecca. This was a retreat, a place for prayer, meditation and contemplation. It was during a period of deep reflection, around AD 610, that he was visited by the archangel Gabriel, who proclaimed that Muhammad was to be the messenger of God. This was the first of a series of revelations that continued until Muhammad died some twenty years later. The revelations were recorded by various scribes during the Prophet’s life, but only as fragments, and it was left to Abū Bakr, the first caliph of Islam, to gather them together into a single text. The work was continued by Umar, the second caliph, and his daughter Hafsa, and was eventually completed by Uthmān, the third caliph. Each revelation became one of the 114 chapters of the Koran.

The ruling caliph was responsible for carrying on the work of the Prophet, upholding his teachings and spreading his word. Between the appointment of Abū Bakr in 632 and the death of the fourth caliph, Alī, in 661, Islam spread until half of the known world was under Muslim rule. Then, in 750, after a century of consolidation, the start of the Abbasid caliphate (or dynasty) heralded the golden age of Islamic civilization. The arts and sciences flourished in equal measure. Islamic craftsmen bequeathed us magnificent paintings, ornate carvings and the most elaborate textiles in history, while the legacy of Islamic scientists is evident from the number of Arabic words that pepper the language of modern science, such as algebra, alkali and zenith.

The richness of Islamic culture was in large part the result of a wealthy and peaceful society. The Abbasid caliphs were less interested than their predecessors in conquest, and instead concentrated on establishing an organized and affluent society. Lower taxes encouraged businesses to grow and gave rise to greater commerce and industry, while strict laws reduced corruption and protected the citizens. All of this relied on an effective system of administration, and in turn the administrators relied on secure communication achieved through the use of encryption. As well as encrypting sensitive affairs of state, it is documented that officials protected tax records, demonstrating a widespread and routine use of cryptography. Further evidence comes from the many administrative manuals, such as the tenth-century Adab al-Kuttāb (The Secretaries’ Manual), that include sections devoted to cryptography.

The administrators usually employed a cipher alphabet that was simply a rearrangement of the plain alphabet, as described earlier, but they also used cipher alphabets that contained other types of symbols. For example, a in the plain alphabet might be replaced by # in the cipher alphabet, b might be replaced by +, and so on. The monoalphabetic substitution cipher is the general name given to any substitution cipher in which the cipher alphabet consists of letters, symbols or a mix of both. All the substitution ciphers that we have met so far come within this general category.

Had the Arabs merely been familiar with the use of the monoalphabetic substitution cipher, they would not warrant a significant mention in any history of cryptography. However, in addition to employing ciphers, the Arab scholars were also capable of destroying ciphers. They in fact invented cryptanalysis, the science of unscrambling a message without knowledge of the key. While the cryptographer develops new methods of secret writing, it is the cryptanalyst who struggles to find weaknesses in these methods in order to break into secret messages. Arabian cryptanalysis succeeded in finding a method for breaking the monoalphabetic substitution cipher, a cipher that had remained unbreakable for several centuries.

Cryptanalysis could not be invented until a civilization had reached a sufficiently sophisticated level of education in several disciplines, including mathematics, statistics and linguistics. The Muslim civilization provided an ideal birthplace for cryptanalysis, because Islam demands justice in all spheres of human activity, and achieving this requires knowledge, or ilm. Every Muslim is obliged to pursue knowledge in all its forms, and the economic success of the Abbasid caliphate meant that scholars had the time, money and materials required to fulfill their duty. They endeavoured to acquire the knowledge of previous civilizations by obtaining Egyptian, Babylonian, Indian, Chinese, Farsi, Syriac, Armenian, Hebrew and Roman texts and translating them into Arabic. In 815, the Caliph al-Ma‘mūn established in Baghdad the Bait al-Hikmah (House of Wisdom), a library and centre for translation.