Malicious Life Podcast: The Doomed Queen’s Secret Ciphers

February 8th, 1587. A doomed queen approaches a stage. From the Washington Post:

“Eyes straight ahead, back rigid and head high, she paused at the foot of the steps leading to the scaffold. Her once magnificent looks had faded with age and years of imprisonment, but she still radiated royal dignity. 

The man who for so long had been her jailer offered his hand to assist her ascent. “I thank you, sir,” she said, according to a historical account of the day. “This is the last trouble I shall ever give you.”

Reaching the platform, the 44-year-old queen was directed to sit in a chair. Looking about the Great Hall of Fotheringhay Castle, she saw the crowd gathered to witness her demise. More than 100 people were riveted by the unfolding spectacle. Her eyes met the hooded axeman dressed entirely in black, the instrument of his trade lying on the floor nearby.”

Kings and queens across Europe had been killed throughout history by various assassins, usurpers, and political nemeses. But not once before this cold February day had a royal been legally ordered to die. Quote:

“The executioner stepped forward and knelt before her. “Forgive me,” he said. “I forgive you and all the world with all my heart,” she answered with a smile, “for I hope this death will make an end to all my troubles.” [. . .]

[She] kissed her ivory crucifix and laid it beside her clothing, then added her prayer book. Taking out a gold-bordered handkerchief, she handed it to one of her ladies, whose hands were trembling so much that [she herself] had to help secure it as her blindfold.

Someone led the queen to the block and helped her to kneel on the cushion before it. She reached out, groping for the block and placed her neck on it.

“Into Thy hands, O Lord, I commend my spirit,” she whispered in Latin, as the executioner raised his ax and swung.”

After the doomed queen’s head was severed (and displayed on a velvet cushion in a castle window), all of her belongings were burned. The idea was to prevent any followers from seizing them as relics of a holy martyr, and, perhaps, to erase her imprint on history. 

George Lasry

Earlier in his career, two startups George Lasry was working for shut down due to a lack of funding. So, to keep himself busy in his off hours, he started cracking old, unsolved ciphers from the Cold War, World War II, and centuries earlier.

It took a decade of codebreaking before he came across the set of texts which would prove to be his greatest challenge, and his greatest contribution to history.

“[George] those texts have been, I would say, lying in plain sight, hiding in plain sight, in the French National Library for more than 400 years, they are kept in a collection which is cataloged as a collection related to Italian matters.”

The Da Vinci Code and Assassin’s Creed may have exaggerated it for dramatic effect, but encryption was thriving in 15th and 16th century Italy. Besides da Vinci, there were other pioneers–Leon Battista Alberti, Giovan Battista Bellaso, Federico II of Gonzaga–iterating and inventing new ways to conceal secret messages.

The text Lasry was looking at from the French National Library probably only could’ve come from a time like this.

“[George] all you have in front of you, you have dense lines of graphical symbols, so that could be around, that could be a square, that could be a slash.”

There was a hashtag, a triangle, a surprised face emoji, and two little stick figures. There were numbers, mathematical symbols, and more abstract combinations of shapes. Recognizable letters, like ‘T’, might be rightside up or upside down, and paired with a slash, a comma, or a dot underneath.

And it wasn’t just that the symbols were strange–there was no rhyme or reason to the outlay of the text. Picture hundreds of pages with line after line of symbols, with no unique formatting, spacing, breaks for paragraphs, or anything like that.

“[George] usually you have a header in which you have a date. You have the person it is addressed to, and then at the end you have a signature and a greeting. And usually you get an idea what they are about, and who wrote them. But in that specific case, all you had was the graphical symbols.”

To even have a chance at cracking it, Lasry, who once wrote a PhD thesis on computerized methods for breaking historical ciphers, began working on a program for organizing the symbols. The process was labor intensive, since his software wasn’t capable of recognizing hastily written symbols on old, scanned papers from hundreds of years ago.

“[George] so you have to either transcribe them manually, just giving a name to each symbol, and then type in those names and then line by line. It’s a very tedious process, and since in that specific collection, we had about something like 200,000 symbols to transcribe…so it’s a lot of work. So I decided to write a program in which I can just mark on an image all the symbols, and then I can classify them into groups of similar symbols.” 

To be clear, all he was doing at this stage was organizing the strange markings, not interpreting them.

“[George] So we have no idea what each symbol means. We don’t know if this letter, if it represents a word, or maybe multiple symbols represent a word, or multiple symbols represents something else.”

Eventually, when the hundreds of thousands of symbols were recorded and ordered in a program, Lasry could begin to apply an algorithmic approach which might draw out clues to their meanings.

“[George] The method is called hill climbing.”

In the process of hill climbing, first, you generate an essentially random key. So, pick a random symbol: let’s say, the circle. We’ll make that an R. Now repeat the same process for every other symbol.

At the end, you check if it makes any sense at all. It won’t.

“[George] So at the beginning, the key that I will have will be completely wrong, because I have no idea what what the symbol means. But then I’m going to do a few small changes. Let’s say that I’m replacing the meaning of…swapping the meaning of, let’s say the circle and the square. And then I’m going to look at the  decipher text and look for improvements. So I’m going to say a little bit what I mean by improvements. So if I have a better decryption, I will keep the change. If the decryption is worse, I will discard the change, and I will try more and more small changes like this, until the decryption looks better and better.”

Making this process work requires more than just a discerning eye–you need a method for measuring and recording the quality of each new key.

“[George] This is done by using what we call n grams. N grams. It’s basically a sequence of consecutive letters. 

If you’re deciphering an English language cipher, for example, you might look for common combinations of letters: like l-y, s-t, i-o-n, e-n-t.

“[George] and so on, those sequences are very prevalent, and I’m looking for them in the tentative decryption that I’m obtaining with that tentative key. And the more I see those sequences, then the higher the grade or the quality of the decryption, until I get to the top of the heel in which you have a large number of those sequences.”

In practice, hill climbing isn’t nearly as linear as it sounds. There will be thousands, possibly millions of individual hills you–or, more accurately, you plus your computer–have to climb, and some keys will disagree with one another in annoying ways. That’s doubly true for a cipher so complex as the one Lasry was working with this time.

Let’s say you’re looking at that little stick figure symbol. It could represent any one of 26 letters, of course. But who’s to say it couldn’t just as easily represent a number, or even a syllable? It could also very easily stand in for a word: “the,” or “castle,” or a whole phrase like “King of England.”

“[George] Based on your experience you have a list of candidate clear text elements that you have to map with the cipher text element. And that’s basically the key. The only way to do that is with trial and some experience.”

In this case, though, his experience wasn’t appearing to help.

“[George] My first hypothesis was that, because it’s with documents related to Italy, probably the language should be Italian. So I took a database of n grams from Italian, and I tried to match it with the hill climbing algorithm to the ciphertext. And I got garbage

He took his results to an Italian expert.

“[George] He told me, Geroge, I’m sorry, I can’t see anything that makes sense. Maybe a word here and there, but that’s not significant statistically.”

A complete dead end. With no particular idea for where to turn, he put the ciphers aside and worked on some other projects.

A year passed.

 “[George] And I say, Okay, why not try again with those ciphers? And usually it happens from time to time. If you sometimes, you are stuck, if you put them aside for a while, then you may have new ideas and new directions. And that’s what happened when I looked at them again. It was in the beginning of 2022, then I said – why not try French? I mean, that’s in the French national library. Why not French?”

He started over from the beginning, this time looking for common letter combinations in his native tongue, even though the documents had come from an Italian archive.

“[George] And then I started to see some fragments of significant French words or expressions, and that was a strong clue that the letter was in French.”

This was the first key breakthrough. By hill climbing with French, he was able to reveal around two-thirds of the text. He was on course to solve it when, for a second time, he got totally stuck.

“[George] There were some passages that I could not decipher, and that was very strange to me. So this is where I contacted my two great colleagues, Nobel Biermann and Satoshi Tomokio

[. . .]

I think what helps is having a fresh and different perspective. And one of the things that I really like working with Satoshi and Norbert is that we came from very diverse backgrounds. Satoshi is an astrophysicist, and he works in a patent company. So he’s very methodical, very precise. He has a site in which he has documented hundreds of historical ciphers. So he’s very knowledgeable, which types of cipher were used in each time period. Norbert is a very bright code breaker. He is a musician. Is a professor of music in the University of Berlin, and is very strong with ancient language, because he also teaches operas and that he has to teach and he has to understand the language.”

George, Satoshi, and Norbert put their heads together. Why, if a majority of the text was already revealed to them, was the remainder a total mystery?

“[George] Satoshi identified that one of the symbols, in fact, is not a letter or a word or something like that. Its function is to delete the previous symbol. [. . .] And then Norbert had some interesting ideas that maybe the slash is not a symbol by itself, but maybe it’s, it’s what we call a diacritic, which is a kind of mark, a special mark.” 

A symbol for repeating the previous letter. So that instead of writing, say, two S symbols in a row, you’d have an S and then a “repeat.”

“[George] Double letters actually reveal a lot [. . .]  So they wanted to add to avoid any pattern that could be discernible from the cipher text itself.”

Having identified these computer-like functions encoded into symbols, entire swaths of the text which didn’t make sense before suddenly revealed themselves for the first time.

“[George] And after a few, a few days of working together, then we were able to decipher pretty much 99-95% of the text.”

With more than 90% of the text translated, a picture began to emerge from the puzzle. A story of a person, told through 57 letters, 50,000 words.

“[George] first was mentioned in French, “mon fis”, which means my son.”

just [received] the news of my son’s abduction by the partisans of the Earl of Angus (…) I am severly restrained, not even allowed to send letters

“[George] Okay, so that person has a son, and then we saw the word ‘ma liberte’, which is ‘my liberty.’ So there is no reason to talk about your liberty if you are free.”

I am stuck in bed so troubled that I don’t know what to say or do, seeing my son in the hands of our most cruel enemies (…) without being able to help or get support (…)

“[George] So probably that person was in captivity. And then there was the word occupy with two Es in French, occupied. And two Es means that it’s a feminine form. So Okay, interesting. We have a woman in captivity writing in French, and she has a son.” 

George and his colleagues furiously pursued historical research to whittle down who this woman might have been.

“[George] When we decipher the second letter, we saw the word Walsingham. And Walsingham, Francis Walsingham [. . .] So that was really the bingo moment.”

Technically, Francis Walsingham was Queen Elizabeth the First’s “principal secretary”–her secretary of state.

In history, however, he’s better known as her spymaster.

The threats to Elizabeth’s throne simply required it of him. Catholics across Europe wanted to take out the Protestant English queen. Tensions were rising with the Vatican–which excommunicated her–and the Spanish–who would soon send an armada to outright invade England. She had no heir to the throne, either, worrying her allies and weakening her standing.

But the single most threatening individual to Queen Elizabeth’s reign was her loving cousin, Mary Stuart, better known as Mary, Queen of Scots.

To Mary, Elizabeth’s problems would’ve seemed quaint. Anointed Queen of Scotland at just six days old, she was sent away to France for the entirety of her childhood, and came back widowed by age 18. Her second husband stabbed her secretary to death 56 times, thinking they were having an affair, and then when that husband was conspicuously murdered not long thereafter, she became suspect number one. Her third husband seems to have kidnapped and raped her, in order to force her hand in marriage (yes, this was a thing back then). In the political fallout Mary was imprisoned, abdicated the throne to her infant son, attempted to win her throne back, failed, and, with her life in danger, fled to seek protection with her cousin Elizabeth, who responded in turn by imprisoning her.

Historical accounts suggest Mary Stuart’s intentions in fleeing to Elizabeth were pure. But as a Catholic with an heir, a reasonable claim to the English throne through her Tudor grandmother, and, not to mention, a reputation for uprisings and murder, she was a walking threat. The year 1569 would mark the first of nearly twenty years–nearly half of her life–as her cousin’s prisoner.

The imprisonment, however, was not the kind meted to commoners. From her confines in castles, Mary was afforded a staff of 30–including a secretary, maids, and cooks–as well as luxuries like fine silverware and tapestries, and occasional supervised trips outside. It was enough flexibility, perhaps, to utilize in conspiring an escape, or a coup.

 “[George] She was extremely intelligent. She was very bright, and it’s mentioned by all of the sources. And at a very, very early age, she was taught how to use ciphers. But she didn’t write the cipher by herself. She dictated the letters in French, and some and the Secretary actually did the encipherment and the decipherment.”

To correspond with her supporters on the outside, Mary, Queen of Scots, through her secretary, used what’s called “homophonic” ciphers. 

The name is a bit of a misnomer, as it’s not really about sounds. A homophonic cipher is one where multiple symbols can have the same meaning. And typically, to prevent decoders from inferring patterns in letter frequencies, more common letters get lots of symbols.

This also explains why Mary’s texts looked so complicated: because when you need more than one symbol per letter, you need more symbols than there are letters, so you start using numbers, or letters of other alphabets, or other kinds of markings.

So, altogether, if we take a word like “we” and homophonically encrypt it, we might represented it as “QU” or “Q%” or Q plus a little stick figure next to it, because the letter W isn’t necessarily so common, but you need a lot of different ways to conceal an E.

Besides its homophonic nature, Mary’s ciphers implemented what we might refer to today as “layered” security, beyond the base encoding system, including those special function characters.

“[George] In addition to that, we had what we call a nomenclature, which is basically a list of symbols that are used not to encipher individual letters of the alphabet, but to encipher common words, part of words, a preposition, and names and titles.”

The symbol for Francis Walsingham, for instance, was a zero with a strikethrough, and a dot to its side. For Queen Elizabeth: a 4 on top of a small circle, with a dot to its right.

“I know that you took care, on behalf of the King [of France], to mitigate the queen’s bursts of anger against me who only wishes her well despite all the evil I have received from her.”

Nate Nelson, reading from the letters deciphered by George, Satoshi, and Norbert.

“[upon receiving my letters] she suddenly feels offended and gets angry, openly cursing me, but after giving the matter some more thought, she calms down.”

It was a remarkably thorough encipherment system that kept these messages under wraps. And while most of the letters didn’t concern grand plots at escape and power, they paint a picture of a capable, motivated woman.

“[George] So before [. . .] She was viewed as someone very impulsive that was in captivity for a long time, and was quite passive and not really making rational decisions, and kind of a victim of circumstances and so on. And that was the perception so far. And from the letter, we see someone very astute, very active. She knows how to manipulate all the Private Council of Isabel I, and even sometimes that she tries to bribe them, and she tries to recruit spies.

“Wilson (…) I am convinced can be bought over time with money, but this must be done in secret. I have instructed my ambassador in France to promptly deliver to you [a gift of] 500 écus to give to Wilson (…), with my promise to give more in the future if he continues with his good offices.”

“[George] So she’s very astute, very well for a lot of statesmanship and and strategic thinking and plotting.”

 Unfortunately for Mary, she had one, fatal oversight.

“[George]  The sense she over relied on ciphers for secrecy and she paid the price for that.”

Beginning in January of 1586, a local brewer would periodically deliver beer barrels to Mary Stuart’s castle prison. They were packed with a hollowed out cork, inside of which would be an enciphered letter from one of her allies.

On July 7, 1586, one such secret letter was delivered from a young Jesuit priest named Anthony Babington. The letter outlined a plot to have a small team of men assassinate and replace Queen Elizabeth with Mary.

Ten days later, the former Scottish queen forwarded her encoded reply. “Set the six gentlemen to work.” She packed it back into a cork, and sent it out in a barrel, in seemingly direct affront to the advice she knew to be true:

Beware of Walsingham, as he is a cunning man, hiding his true intentions under the pretense of a (false) friendship. He has been concealing his bad intentions toward me (…) when we tried to accomodate him, he strived even more tried to harm the King [of France] and myself, wishing my death.

As de facto spymaster, Francis Walsingham headed a crack team of intelligence analysts and expert cryptologists. It was a kind of proto-GCHQ, developing novel methods for secret communication, based out of his home in Seething Lane, just a few hundred yards from the Tower of London.

Outside of this core team was Walsingham’s wide network of informants across the European continent. According to Military Heritage magazine, some years after being appointed, he’d amassed teams of secret agents in 12 cities in France, nine in Germany, four in Italy, four in Spain, three in the Netherlands, and more across the Ottoman Empire, in cities like Algiers, Constantinople, and Tripoli. He employed customs agents and merchants as informants. His double agents were embedded deep in Catholic centers of power, and they even included celebrities, like the great playwright who lived in Shakespeare’s shadow, Christopher Marlowe.

Also among their numbers were allies of Mary Stuart, like the Catholic priest Gilbert Gifford, who arranged the beer barrel transmissions–Walsingham’s idea–alongside the local brewer, also on the payroll. Gifford had also facilitated the correspondence with Babington, all while passing it through Walsingham’s decoder, ensuring that the spymaster knew every message’s contents before the intended recipient did.

So Mary had used a remarkably complex encipherment system, but failed to equally secure its line of transmission. Thanks to that mistake, she was brought in front of a crowd at the Fotheringhay Castle on February 8th, 1587. She knelt down, kissed the cross hanging from her neck, and an executioner named “Bull” dutifully removed her head from her body.