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

Then she laide herself upon the blocke most quietlie, & stretching out her armes & legges cryed out In manus tuas domine three or foure times, & at the laste while one of the executioners held her slightlie with one of his handes, the other gave two strokes with an axe before he cutt of her head, & yet lefte a little gristle behinde at which time she made verie small noyse & stirred not any parte of herself from the place where she laye … Her lipps stirred up & downe almost a quarter of an hower after her head was cutt of. Then one of her executioners plucking of her garters espied her little dogge which was crept under her clothes which could not be gotten forth but with force & afterwardes could not depart from her dead corpse, but came and laye betweene her head & shoulders a thing dilligently noted.

Figure 10 The execution of Mary Queen of Scots.

Scottish National Portrait Gallery, Edinburgh.

2 Le Chiffre Indéchiffrable

For centuries, the simple monoalphabetic substitution cipher had been sufficient to ensure secrecy. The subsequent development of frequency analysis, first in the Arab world and then in Europe, destroyed its security. The tragic execution of Mary Queen of Scots was a dramatic illustration of the weaknesses of monoalphabetic substitution, and in the battle between cryptographers and cryptanalysts it was clear that the cryptanalysts had gained the upper hand. Anybody sending an encrypted message had to accept that an expert enemy codebreaker might intercept and decipher their most precious secrets.

The onus was clearly on the cryptographers to concoct a new, stronger cipher, something that could outwit the cryptanalysts. Although this cipher would not emerge until the end of the sixteenth century, its origins can be traced back to the fifteenth-century Florentine polymath Leon Battista Alberti. Born in 1404, Alberti was one of the leading figures of the Renaissance – a painter, composer, poet and philosopher, as well as the author of the first scientific analysis of perspective, a treatise on the housefly and a funeral oration for his dog. He is probably best known as an architect, having designed Rome’s first Trevi Fountain and having written De re aedificatoria, the first printed book on architecture, which acted as a catalyst for the transition from Gothic to Renaissance design.

Sometime in the 1460s, Alberti was wandering through the gardens of the Vatican when he bumped into his friend Leonardo Dato, the pontifical secretary, who began chatting to him about some of the finer points of cryptography. This casual conversation prompted Alberti to write an essay on the subject, outlining what he believed to be a new form of cipher. At the time, all substitution ciphers required a single cipher alphabet for encrypting each message. However, Alberti proposed using two or more cipher alphabets, switching between them during encipherment, thereby confusing potential cryptanalysts.

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 1 F Z B V K I X A Y M E P L S D H J O R G N Q C U T W

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

For example, here we have two possible cipher alphabets, and we could encrypt a message by alternating between them. To encrypt the message hello, we would encrypt the first letter according to the first cipher alphabet, so that h becomes A, but we would encrypt the second letter according to the second cipher alphabet, so that e becomes F. To encrypt the third letter we return to the first cipher alphabet, and to encrypt the fourth letter we return to the second alphabet. This means that the first I is enciphered as P, but the second I is enciphered as A. The final letter, o, is enciphered according to the first cipher alphabet and becomes D. The complete ciphertext reads AFPAD. The crucial advantage of Alberti’s system is that the same letter in the plaintext does not necessarily appear as the same letter in the ciphertext, so the repeated I in hello is enciphered differently in each case. Similarly, the repeated A in the ciphertext represents a different plaintext letter in each case, first h and then I.

Although he had hit upon the most significant breakthrough in encryption for over a thousand years, Alberti failed to develop his concept into a fully formed system of encryption. That task fell to a diverse group of intellectuals, who built on his initial idea. First came Johannes Trithemius, a German abbot born in 1462, then Giovanni Porta, an Italian scientist born in 1535, and finally Blaise de Vigenère, a French diplomat born in 1523. Vigenère became acquainted with the writings of Alberti, Trithemius and Porta when, at the age of twenty-six, he was sent to Rome on a two-year diplomatic mission. To start with, his interest in cryptography was purely practical and was linked to his diplomatic work. Then, at the age of thirty-nine, Vigenère decided that he had accumulated enough money for him to be able to abandon his career and concentrate on a life of study. It was only then that he examined in detail the ideas of Alberti, Trithemius and Porta, weaving them into a coherent and powerful new cipher.

Figure 11 Blaise de Vigenère.

Cliché Bibliothèque Nationale de France, Paris, France.

Table 3 A Vigenère square.

Although Alberti, Trithemius and Porta all made vital contributions, the cipher is known as the Vigenère cipher in honour of the man who developed it into its final form. The strength of the Vigenère cipher lies in its using not one, but 26 distinct cipher alphabets to encrypt a message. The first step in encipherment is to draw up a so-called Vigenère square, as shown in Table 3, a plaintext alphabet followed by 26 cipher alphabets, each shifted by one letter with respect to the previous alphabet. Hence, row 1 represents a cipher alphabet with a Caesar shift of 1, which means that it could be used to implement a Caesar shift cipher in which every letter of the plaintext is replaced by the letter one place further on in the alphabet. Similarly, row 2 represents a cipher alphabet with a Caesar shift of 2, and so on. The top row of the square, in lower case, represents the plaintext letters. You could encipher each plaintext letter according to any one of the 26 cipher alphabets. For example, if cipher alphabet number 2 is used, then the letter a is enciphered as C, but if cipher alphabet number 12 is used, then a is enciphered as M.

If the sender were to use just one of the cipher alphabets to encipher an entire message, this would effectively be a simple Caesar cipher, which would be a very weak form of encryption, easily deciphered by an enemy interceptor. However, in the Vigenère cipher a different row of the Vigenère square (a different cipher alphabet) is used to encrypt different letters of the message. In other words, the sender might encrypt the first letter according to row 5, the second according to row 14, the third according to row 21, and so on.

To unscramble the message, the intended receiver needs to know which row of the Vigenère square has been used to encipher each letter, so there must be an agreed system of switching between rows. This is achieved by using a keyword. To illustrate how a keyword is used with the Vigenère square to encrypt a short message, let us encipher divert troops to east ridge, using the keyword WHITE. First of all, the keyword is spelt out above the message, and repeated over and over again so that each letter in the message is associated with a letter from the keyword. The ciphertext is then generated as follows. To encrypt the first letter, d, begin by identifying the key letter above it, W, which in turn defines a particular row in the Vigenère square. The row beginning with W, row 22, is the cipher alphabet that will be used to find the substitute letter for the plaintext d. We look to see where the column headed by d intersects the row beginning with W, which turns out to be at the letter Z. Consequently, the letter d in the plaintext is represented by Z in the ciphertext.

Keyword W H I T E W H I T E W H I T E W H I T E W H I

Plaintext d i v e r t t r o o p s t o e a s t r i d g e

Ciphertext Z P D X V P A Z H S L Z B H I W Z B K M Z N M

Table 4 A Vigenère square with the rows defined by the keyword WHITE highlighted. Encryption is achieved by switching between the five highlighted cipher alphabets, defined by W, H, I, T and E.

To encipher the second letter of the message, i, the process is repeated. The key letter above i is H, so it is encrypted via a different row in the Vigenère square: the H row (row 7) which is a new cipher alphabet. To encrypt i, we look to see where the column headed by i intersects the row beginning with H, which turns out to be at the letter P. Consequently, the letter i in the plaintext is represented by P in the ciphertext. Each letter of the keyword indicates a particular cipher alphabet within the Vigenère square, and because the keyword contains five letters, the sender encrypts the message by cycling through five rows of the Vigenère square. The fifth letter of the message is enciphered according to the fifth letter of the keyword, E, but to encipher the sixth letter of the message we have to return to the first letter of the keyword. A longer keyword, or perhaps a keyphrase, would bring more rows into the encryption process and increase the complexity of the cipher. Table 4 shows a Vigenère square, highlighting the five rows (i.e. the five cipher alphabets) defined by the keyword WHITE.

The great advantage of the Vigenère cipher is that it is impregnable to the frequency analysis described in Chapter 1. For example, a cryptanalyst applying frequency analysis to a piece of ciphertext would usually begin by identifying the most common letter in the ciphertext, which in this case is Z, and then assume that this represents the most common letter in English, e. In fact, the letter Z represents three different letters, d, r and s, but not e. This is clearly a problem for the cryptanalyst. The fact that a letter which appears several times in the ciphertext can represent a different plaintext letter on each occasion generates tremendous ambiguity for the cryptanalyst. Equally confusing is the fact that a letter which appears several times in the plaintext can be represented by different letters in the ciphertext. For example, the letter o is repeated in troops, but it is substituted by two different letters – the oo is enciphered as HS.

As well as being invulnerable to frequency analysis, the Vigenère cipher has an enormous number of keys. The sender and receiver can agree on any word in the dictionary, any combination of words, or even fabricate words. A cryptanalyst would be unable to crack the message by searching all possible keys because the number of options is simply too great.

Vigenère’s work culminated in his Traicté des Chiffres (‘A Treatise on Secret Writing’), published in 1586. Ironically, this was the same year that Thomas Phelippes was breaking the cipher of Mary Queen of Scots. If only Mary’s secretary had read this treatise, he would have known about the Vigenère cipher, Mary’s messages to Babington would have baffled Phelippes, and her life might have been spared.

Because of its strength and its guarantee of security, it would seem natural that the Vigenère cipher would be rapidly adopted by cipher secretaries around Europe. Surely they would be relieved to have access, once again, to a secure form of encryption? On the contrary, cipher secretaries seem to have spurned the Vigenère cipher. This apparently flawless system would remain largely neglected for the next two centuries.

From Shunning Vigenère to the Man in the Iron Mask

The traditional forms of substitution cipher, those that existed before the Vigenère cipher, were called monoalphabetic substitution ciphers because they used only one cipher alphabet per message. In contrast, the Vigenère cipher belongs to a class known as polyalphabetic, because it employs several cipher alphabets per message. The polyalphabetic nature of the Vigenère cipher is what gives it its strength, but it also makes it much more complicated to use. The additional effort required in order to implement the Vigenère cipher discouraged many people from employing it.

For many seventeenth-century purposes, the monoalphabetic substitution cipher was perfectly adequate. If you wanted to ensure that your servant was unable to read your private correspondence, or if you wanted to protect your diary from the prying eyes of your spouse, then the old-fashioned type of cipher was ideal. Monoalphabetic substitution was quick, easy to use, and secure against people unschooled in cryptanalysis. In fact, the simple monoalphabetic substitution cipher endured in various forms for many centuries (see Appendix D). For more serious applications, such as military and government communications, where security was paramount, the straightforward monoalphabetic cipher was clearly inadequate. Professional cryptographers in combat with professional cryptanalysts needed something better, yet they were still reluctant to adopt the polyalphabetic cipher because of its complexity. Military communications, in particular, required speed and simplicity, and a diplomatic office might be sending and receiving hundreds of messages each day, so time was of the essence. Consequently, cryptographers searched for an intermediate cipher, one that was harder to crack than a straightforward monoalphabetic cipher, but one that was simpler to implement than a polyalphabetic cipher.

The various candidates included the remarkably effective homophonic substitution cipher. Here, each letter is replaced with a variety of substitutes, the number of potential substitutes being proportional to the frequency of the letter. For example, the letter a accounts for roughly 8 per cent of all letters in written English, and so we would assign eight symbols to represent it. Each time a appears in the plaintext it would be replaced in the ciphertext by one of the eight symbols chosen at random, so that by the end of the encipherment each symbol would constitute roughly 1 per cent of the enciphered text. By comparison, the letter b accounts for only 2 per cent of all letters, and so we would assign only two symbols to represent it. Each time b appears in the plaintext either of the two symbols could be chosen, and by the end of the encipherment each symbol would also constitute roughly 1 per cent of the enciphered text. This process of allotting varying numbers of symbols to act as substitutes for each letter continues throughout the alphabet, until we get to z, which is so rare that it has only one symbol to act as a substitute. In the example given in Table 5, the substitutes in the cipher alphabet happen to be two-digit numbers, and there are between one and twelve substitutes for each letter in the plain alphabet, depending on each letter’s relative abundance.

Table 5 An example of a homophonic substitution cipher. The top row represents the plain alphabet, while the numbers below represent the cipher alphabet, with several options for frequently occurring letters.

We can think of all the two-digit numbers that correspond to the plaintext letter a as effectively representing the same sound in the ciphertext, namely the sound of the letter a. Hence the origin of the term homophonic substitution, homos meaning ‘same’ and phonos meaning ‘sound’ in Greek. The point of offering several substitution options for popular letters is to balance out the frequencies of symbols in the ciphertext. If we enciphered a message using the cipher alphabet in Table 5, then every number would constitute roughly 1 per cent of the entire text. If no symbol appears more frequently than any other, then this would appear to defy any potential attack via frequency analysis. Perfect security? Not quite.

The ciphertext still contains many subtle clues for the clever cryptanalyst. As we saw in Chapter 1, each letter in the English language has its own personality, defined according to its relationship with all the other letters, and these traits can still be discerned even if the encryption is by homophonic substitution. In English, the most extreme example of a letter with a distinct personality is the letter q, which is only followed by one letter, namely u. If we were attempting to decipher a ciphertext, we might begin by noting that q is a rare letter, and is therefore likely to be represented by just one symbol, and we know that u, which accounts for roughly 3 per cent of all letters, is probably represented by three symbols. So, if we find a symbol in the ciphertext that is only ever followed by three particular symbols, then it would be sensible to assume that the first symbol represents q and the other three symbols represent u. Other letters are harder to spot, but are also betrayed by their relationships to one another. Although the homophonic cipher is breakable, it is much more secure than a straightforward monoalphabetic cipher.

A homophonic cipher might seem similar to a polyalphabetic cipher inasmuch as each plaintext letter can be enciphered in many ways, but there is a crucial difference, and the homophonic cipher is in fact a type of monoalphabetic cipher. In the table of homophones shown above, the letter a can be represented by eight numbers. Significantly, these eight numbers represent only the letter a. In other words, a plaintext letter can be represented by several symbols, but each symbol can only represent one letter. In a polyalphabetic cipher, a plaintext letter will also be represented by different symbols, but, even more confusingly, these symbols will represent different letters during the course of an encipherment.

Perhaps the fundamental reason why the homophonic cipher is considered monoalphabetic is that once the cipher alphabet has been established, it remains constant throughout the process of encryption. The fact that the cipher alphabet contains several options for encrypting each letter is irrelevant. However, a cryptographer who is using a polyalphabetic cipher must continually switch between distinctly different cipher alphabets during the process of encryption.

By tweaking the basic monoalphabetic cipher in various ways, such as adding homophones, it became possible to encrypt messages securely, without having to resort to the complexities of the polyalphabetic cipher. One of the strongest examples of an enhanced monoalphabetic cipher was the Great Cipher of Louis XIV. The Great Cipher was used to encrypt the king’s most secret messages, protecting details of his plans, plots and political schemings. One of these messages mentioned one of the most enigmatic characters in French history, the Man in the Iron Mask, but the strength of the Great Cipher meant that the message and its remarkable contents would remain undeciphered and unread for two centuries.

The Great Cipher was invented by the father-and-son team of Antoine and Bonaventure Rossignol. Antoine had first come to prominence in 1626 when he was given a coded letter captured from a messenger leaving the besieged city of Réalmont. Before the end of the day he had deciphered the letter, revealing that the Huguenot army which held the city was on the verge of collapse. The French, who had previously been unaware of the Huguenots’ desperate plight, returned the letter accompanied by a decipherment. The Huguenots, who now knew that their enemy would not back down, promptly surrendered. The decipherment had resulted in a painless French victory.

The power of codebreaking became obvious, and the Rossignols were appointed to senior positions in the court. After serving Louis XIII, they then acted as cryptanalysts for Louis XIV, who was so impressed that he moved their offices next to his own apartments so that Rossignol père et fils could play a central role in shaping French diplomatic policy. One of the greatest tributes to their abilities is that the word rossignol became French slang for a device that picks locks, a reflection of their ability to unlock ciphers.

The Rossignols’ prowess at cracking ciphers gave them an insight into how to create a stronger form of encryption, and they invented the so-called Great Cipher. The Great Cipher was so secure that it defied the efforts of all enemy cryptanalysts attempting to steal French secrets. Unfortunately, after the death of both father and son, the Great Cipher fell into disuse and its exact details were rapidly lost, which meant that enciphered papers in the French archives could no longer be read. The Great Cipher was so strong that it even defied the efforts of subsequent generations of codebreakers.

Historians knew that the papers encrypted by the Great Cipher would offer a unique insight into the intrigues of seventeenth-century France, but even by the end of the nineteenth century they were still unable to decipher them. Then, in 1890, Victor Gendron, a military historian researching the campaigns of Louis XIV, unearthed a new series of letters enciphered with the Great Cipher. Unable to make sense of them, he passed them on to Commandant Étienne Bazeries, a distinguished expert in the French Army’s Cryptographic Department. Bazeries viewed the letters as the ultimate challenge, and he spent the next three years of his life attempting to decipher them.

The encrypted pages contained thousands of numbers, but only 587 different ones. It was clear that the Great Cipher was more complicated than a straightforward substitution cipher, because this would require just 26 different numbers, one for each letter. Initially, Bazeries thought that the surplus of numbers represented homophones, and that several numbers represented the same letter. Exploring this avenue took months of painstaking effort, all to no avail. The Great Cipher was not a homophonic cipher.

Next, he hit upon the idea that each number might represent a pair of letters, or a digraph. There are only 26 individual letters, but there are 676 possible pairs of letters, and this is roughly equal to the variety of numbers in the ciphertexts. Bazeries attempted a decipherment by looking for the most frequent numbers in the ciphertexts (22, 42, 124, 125 and 341), assuming that these probably stood for the commonest French digraphs (es, en, ou, de, nt). In effect, he was applying frequency analysis at the level of pairs of letters. Unfortunately, again after months of work, this theory also failed to yield any meaningful decipherments.

Bazeries must have been on the point of abandoning his obsession, when a new line of attack occurred to him. Perhaps the digraph idea was not so far from the truth. He began to consider the possibility that each number represented not a pair of letters, but rather a whole syllable. He attempted to match each number to a syllable, the most frequently occurring numbers presumably representing the commonest French syllables. He tried various tentative permutations, but they all resulted in gibberish – until he succeeded in identifying one particular word. A cluster of numbers (124-22-125-46-345) appeared several times on each page, and Bazeries postulated that they represented les-en-ne-mi-s, that is, ‘les ennemis’. This proved to be a crucial breakthrough.

Bazeries was then able to continue by examining other parts of the ciphertexts where these numbers appeared within different words. He then inserted the syllabic values derived from ‘les enemis’, which revealed parts of other words. As crossword addicts know, when a word is partly completed it is often possible to guess the remainder of the word. As Bazeries completed new words, he also identified further syllables, which in turn led to other words, and so on. Frequently he would be stumped, partly because the syllabic values were never obvious, partly because some of the numbers represented single letters rather than syllables, and partly because the Rossignols had laid traps within the cipher. For example, one number represented neither a syllable nor a letter, but instead deviously deleted the previous number.

When the decipherment was eventually completed, Bazeries became the first person for two hundred years to witness the secrets of Louis XIV. The newly deciphered material fascinated historians, who focused on one tantalising letter in particular. It seemed to solve one of the great mysteries of the seventeenth century: the true identity of the Man in the Iron Mask.

The Man in the Iron Mask has been the subject of much speculation ever since he was first imprisoned at the French fortress of Pignerole in Savoy. When he was transferred to the Bastille in 1698, peasants tried to catch a glimpse of him, and variously reported him as being short or tall, fair or dark, young or old. Some even claimed that he was a she. With so few facts, everyone from Voltaire to Benjamin Franklin concocted their own theory to explain the case of the Man in the Iron Mask. The most popular conspiracy theory relating to the Mask (as he is sometimes called) suggests that he was the twin of Louis XIV, condemned to imprisonment in order to avoid any controversy over who was the rightful heir to the throne. One version of this theory argues that there existed descendants of the Mask and an associated hidden royal bloodline. A pamphlet published in 1801 said that Napoleon himself was a descendant of the Mask, a rumour which, since it enhanced his position, the emperor did not deny.

The myth of the Mask even inspired poetry, prose and drama. In 1848 Victor Hugo had begun writing a play entitled Twins, but when he found that Alexandre Dumas had already plumped for the same plot, he abandoned the two acts he had written. Ever since, it has been Dumas’s name that we associate with the story of the Man in the Iron Mask. The success of his novel reinforced the idea that the Mask was related to the king, and this theory has persisted despite the evidence revealed in one of Bazeries’s decipherments.

Bazeries had deciphered a letter written by François de Louvois, Louis XIV’s Minister of War, which began by recounting the crimes of Vivien de Bulonde, the commander responsible for leading an attack on the town of Cuneo, on the French-Italian border. Although he was ordered to stand his ground, Bulonde became concerned about the arrival of enemy troops from Austria and fled, leaving behind his munitions and abandoning many of his wounded soldiers. According to the Minister of War, these actions jeopardised the whole Piedmont campaign, and the letter made it clear that the king viewed Bulonde’s actions as an act of extreme cowardice:

His Majesty knows better than any other person the consequences of this act, and he is also aware of how deeply our failure to take the place will prejudice our cause, a failure which must be repaired during the winter. His Majesty desires that you immediately arrest General Bulonde and cause him to be conducted to the fortress of Pignerole, where he will be locked in a cell under guard at night, and permitted to walk the battlements during the day with a mask.