The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography

by Simon Singh

  Gifford was still a youth, even younger than Babington, and yet he conducted his deliveries with confidence and guile. His aliases, such as Mr. Colerdin, Pietro and Cornelys, enabled him to travel the country without suspicion, and his contacts within the Catholic community provided him with a series of safe houses between London and Chartley Hall. However, each time Gifford traveled to or from Chartley Hall, he would make a detour. Although Gifford was apparently acting as an agent for Mary, he was actually a double agent. Back in 1585, before his return to England, Gifford had written to Sir Francis Walsingham, Principal Secretary to Queen Elizabeth, offering his services. Gifford realized that his Catholic background would act as a perfect mask for infiltrating plots against Queen Elizabeth. In the letter to Walsingham, he wrote, “I have heard of the work you do and I want to serve you. I have no scruples and no fear of danger. Whatever you order me to do I will accomplish.”

  Figure 8 The nomenclator of Mary Queen of Scots, consisting of a cipher alphabet and codewords.

  Walsingham was Elizabeth’s most ruthless minister. He was a Machiavellian figure, a spymaster who was responsible for the security of the monarch. He had inherited a small network of spies, which he rapidly expanded into the Continent, where many of the plots against Elizabeth were being hatched. After his death it was discovered that he had been receiving regular reports from twelve locations in France, nine in Germany, four in Italy, four in Spain and three in the Low Countries, as well as having informants in Constantinople, Algiers and Tripoli.

  Walsingham recruited Gifford as a spy, and in fact it was Walsingham who ordered Gifford to approach the French Embassy and offer himself as a courier. Each time Gifford collected a message to or from Mary, he would first take it to Walsingham. The vigilant spymaster would then pass it to his counterfeiters, who would break the seal on each letter, make a copy, and then reseal the original letter with an identical stamp before handing it back to Gifford. The apparently untouched letter could then be delivered to Mary or her correspondents, who remained oblivious to what was going on.

  When Gifford handed Walsingham a letter from Babington to Mary, the first objective was to decipher it. Walsingham had originally encountered codes and ciphers while reading a book written by the Italian mathematician and cryptographer Girolamo Cardano (who, incidentally, proposed a form of writing for the blind based on touch, a precursor of Braille). Cardano’s book aroused Walsingham’s interest, but it was a decipherment by the Flemish cryptanalyst Philip van Marnix that really convinced him of the power of having a codebreaker at his disposal. In 1577, Philip of Spain was using ciphers to correspond with his half-brother and fellow Catholic, Don John of Austria, who was in control of much of the Netherlands. Philip’s letter described a plan to invade England, but it was intercepted by William of Orange, who passed it to Marnix, his cipher secretary. Marnix deciphered the plan, and William passed the information to Daniel Rogers, an English agent working on the Continent, who in turn warned Walsingham of the invasion. The English reinforced their defenses, which was enough to deter the invasion attempt.

  Now fully aware of the value of cryptanalysis, Walsingham established a cipher school in London and employed Thomas Phelippes as his cipher secretary, a man “of low stature, slender every way, dark yellow haired on the head, and clear yellow bearded, eaten in the face with smallpox, of short sight, thirty years of age by appearance.” Phelippes was a linguist who could speak French, Italian, Spanish, Latin and German, and, more importantly, he was one of Europe’s finest cryptanalysts.

  Upon receiving any message to or from Mary, Phelippes devoured it. He was a master of frequency analysis, and it would be merely a matter of time before he found a solution. He established the frequency of each character, and tentatively proposed values for those that appeared most often. When a particular approach hinted at absurdity, he would backtrack and try alternative substitutions. Gradually he would identify the nulls, the cryptographic red herrings, and put them to one side. Eventually all that remained were the handful of codewords, whose meaning could be guessed from the context.

  When Phelippes deciphered Babington’s message to Mary, which clearly proposed the assassination of Elizabeth, he immediately forwarded the damning text to his master. At this point Walsingham could have pounced on Babington, but he wanted more than the execution of a handful of rebels. He bided his time in the hope that Mary would reply and authorize the plot, thereby incriminating herself. Walsingham had long wished for the death of Mary Queen of Scots, but he was aware of Elizabeth’s reluctance to execute her cousin. However, if he could prove that Mary was endorsing an attempt on the life of Elizabeth, then surely his queen would permit the execution of her Catholic rival. Walsingham’s hopes were soon fulfilled.

  On July 17, Mary replied to Babington, effectively signing her own death warrant. She explicitly wrote about the “design,” showing particular concern that she should be released simultaneously with, or before, Elizabeth’s assassination, otherwise news might reach her jailer, who might then murder her. Before reaching Babington, the letter made the usual detour to Phelippes. Having cryptanalyzed the earlier message, he deciphered this one with ease, read its contents, and marked it with a “”-the sign of the gallows.

  Walsingham had all the evidence he needed to arrest Mary and Babington, but still he was not satisfied. In order to destroy the conspiracy completely, he needed the names of all those involved. He asked Phelippes to forge a postscript to Mary’s letter, which would entice Babington to name names. One of Phelippes’s additional talents was as a forger, and it was said that he had the ability “to write any man’s hand, if he had once seen it, as if the man himself had writ it.” Figure 9 shows the postscript that was added at the end of Mary’s letter to Babington. It can be deciphered using Mary’s nomenclator, as shown in Figure 8, to reveal the following plaintext:

  I would be glad to know the names and qualities of the six gentlemen which are to accomplish the designment; for it may be that I shall be able, upon knowledge of the parties, to give you some further advice necessary to be followed therein, as also from time to time particularly how you proceed: and as soon as you may, for the same purpose, who be already, and how far everyone is privy hereunto.

  The cipher of Mary Queen of Scots clearly demonstrates that a weak encryption can be worse than no encryption at all. Both Mary and Babington wrote explicitly about their intentions because they believed that their communications were secure, whereas if they had been communicating openly they would have referred to their plan in a more discreet manner. Furthermore, their faith in their cipher made them particularly vulnerable to accepting Phelippes’s forgery. Sender and receiver often have such confidence in the strength of their cipher that they consider it impossible for the enemy to mimic the cipher and insert forged text. The correct use of a strong cipher is a clear boon to sender and receiver, but the misuse of a weak cipher can generate a very false sense of security.

  Figure 9 The forged postscript added by Thomas Phelippes to Mary’s message. It can be deciphered by referring to Mary’s nomenclator (Figure 8). (photo credit 1.3)

  Soon after receiving the message and its postscript, Babington needed to go abroad to organize the invasion, and had to register at Walsingham’s department in order to acquire a passport. This would have been an ideal time to capture the traitor, but the bureaucrat who was manning the office, John Scudamore, was not expecting the most wanted traitor in England to turn up at his door. Scudamore, with no support to hand, took the unsuspecting Babington to a nearby tavern, stalling for time while his assistant organized a group of soldiers. A short while later a note arrived at the tavern, informing Scudamore that it was time for the arrest. Babington, however, caught sight of it. He casually said that he would pay for the beer and meal and rose to his feet, leaving his sword and coat at the table, implying that he would return in an instant. Instead, he slipped out of the back door and escaped, first to St. John’s Wood and then on to Harrow. He attempted
to disguise himself, cutting his hair short and staining his skin with walnut juice to mask his aristocratic background. He managed to elude capture for ten days, but by August 15, Babington and his six colleagues were captured and brought to London. Church bells across the city rang out in triumph. Their executions were horrid in the extreme. In the words of the Elizabethan historian William Camden, “they were all cut down, their privities were cut off, bowelled alive and seeing, and quartered.”

  Meanwhile, on August 11, Mary Queen of Scots and her entourage had been allowed the exceptional privilege of riding in the grounds of Chartley Hall. As Mary crossed the moors she spied some horsemen approaching, and immediately thought that these must be Babington’s men coming to rescue her. It soon became clear that these men had come to arrest her, not release her. Mary had been implicated in the Babington Plot, and was charged under the Act of Association, an Act of Parliament passed in 1584 specifically designed to convict anybody involved in a conspiracy against Elizabeth.

  The trial was held in Fotheringhay Castle, a bleak, miserable place in the middle of the featureless fens of East Anglia. It began on Wednesday, October 15, in front of two chief justices, four other judges, the Lord Chancellor, the Lord Treasurer, Walsingham, and various earls, knights and barons. At the back of the courtroom there was space for spectators, such as local villagers and the servants of the commissioners, all eager to see the humiliated Scottish queen beg forgiveness and plead for her life. However, Mary remained dignified and composed throughout the trial. Mary’s main defense was to deny any connection with Babington. “Can I be responsible for the criminal projects of a few desperate men,” she proclaimed, “which they planned without my knowledge or participation?” Her statement had little impact in the face of the evidence against her.

  Mary and Babington had relied on a cipher to keep their plans secret, but they lived during a period when cryptography was being weakened by advances in cryptanalysis. Although their cipher would have been sufficient protection against the prying eyes of an amateur, it stood no chance against an expert in frequency analysis. In the spectators’ gallery sat Phelippes, quietly watching the presentation of the evidence that he had conjured from the enciphered letters.

  The trial went into a second day, and Mary continued to deny any knowledge of the Babington Plot. When the trial finished, she left the judges to decide her fate, pardoning them in advance for the inevitable decision. Ten days later, the Star Chamber met in Westminster and concluded that Mary had been guilty of “compassing and imagining since June 1st matters tending to the death and destruction of the Queen of England.” They recommended the death penalty, and Elizabeth signed the death warrant.

  On February 8, 1587, in the Great Hall of Fotheringhay Castle, an audience of three hundred gathered to watch the beheading. Walsingham was determined to minimize Mary’s influence as a martyr, and he ordered that the block, Mary’s clothing, and everything else relating to the execution be burned in order to avoid the creation of any holy relics. He also planned a lavish funeral procession for his son-in-law, Sir Philip Sidney, to take place the following week. Sidney, a popular and heroic figure, had died fighting Catholics in the Netherlands, and Walsingham believed that a magnificent parade in his honor would dampen sympathy for Mary. However, Mary was equally determined that her final appearance should be a defiant gesture, an opportunity to reaffirm her Catholic faith and inspire her followers.

  While the Dean of Peterborough led the prayers, Mary spoke aloud her own prayers for the salvation of the English Catholic Church, for her son and for Elizabeth. With her family motto, “In my end is my beginning,” in her mind, she composed herself and approached the block. The executioners requested her forgiveness, and she replied, “I forgive you with all my heart, for now I hope you shall make an end of all my troubles.” Richard Wingfield, in his Narration of the Last Days of the Queen of Scots, describes her final moments:

  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. (photo credit 1.4)

  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.

  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 l is enciphered as P, but the second l 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 l 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 l.

  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 writin
gs 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. (photo credit 2.1)

  Although Alberti, Trithemius and Porta all made vital contributions, the cipher is known as the Vigenère cipher in honor 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.