The cipher bureau

The last chapter ended with the thought that hardness is not only a nuisance: a lock can be built on it, since a problem nobody knows how to solve quickly can protect something. But people were building locks long before complexity theory, for thousands of years, and those locks relied on cunning and on the hope that the enemy wouldn’t guess. Before we build a lock on hardness, we’ll pick a few old ones with our own hands.

Welcome to the cipher bureau. You are an intern, and today is your first day. The bureau has four rooms. In each lies an intercepted message, and the door to the next room is locked. Read the message and the door opens. You have Python with you, the strings of Chapter 7 and the dictionaries of Chapter 8, and you won’t need anything else.

First, a few words you can’t do without in the bureau. A cipher is a rule for turning a message into gibberish and back. The original message is called the plaintext, the result the ciphertext. A cipher has one rule but many possible transformations, and which of them is in use today is decided by the key. The sender and the receiver know the key; the enemy doesn’t. The art of reading a ciphertext without the key is called cryptanalysis, and that is what you’ll be doing.

The rule over the door

Over the door of the bureau hangs a rule. It was formulated in 1883 by Auguste Kerckhoffs, a Dutchman who was a professor of German in Paris, in an article called La Cryptographie militaire, where he listed six requirements for military ciphers. The second reads: “Il faut qu’il n’exige pas le secret, et qu’il puisse sans inconvénient tomber entre les mains de l’ennemi”; that is, the system must not require secrecy, and it must be able to fall into the hands of the enemy without harm.

The strictness makes sense, because the design of a cipher doesn’t stay secret for long. Cipher machines are captured on the battlefield, programs are taken apart, employees quit and talk. A key can be changed tomorrow morning, but a new cipher takes years to devise. Claude Shannon, of whom more later, put it more briefly: “the enemy knows the system being used.” So it will be in the rooms of the bureau. You know how each cipher works; only the key is unknown, and each time the question is whether you can find it or do without it.

Room 1. Caesar’s wheel

The oldest cipher in the bureau was described almost two thousand years ago. The historian Suetonius tells us that in his secret letters Julius Caesar replaced every letter with the one three places after it in the alphabet. We’ll build this cipher for the English alphabet. Number the letters from zero and ignore capitals, as when we counted letters in Chapter 8: that leaves 26 letters. To encrypt a letter, add the key to its number. If the number runs past the end of the alphabet, keep counting from the beginning: after z comes a again. This is the remainder of division by 26, the same clock arithmetic to which a chapter of “Mathematics, the Queen of the Sciences” is devoted.

The method index finds a letter in the string and returns its number. Decryption is the same shift in the other direction, so no separate function is needed: caesar(secret, -3). And here is the first message. It lies on the desk in the first room, encrypted the same way but with an unknown key. It is easiest to break with a wheel, as people did for centuries: two rings with the alphabet, the outer one fixed and the inner one free to turn.

A few turns of the wheel, and the message reads. The door is open, but how easily that went is instructive. Caesar’s cipher has only 26 keys, and a shift of zero hides nothing. Trying them all takes a person with a wheel a minute and a program no time at all. An attack that tries every key in turn is called brute force. Here it is, applied to the note that lay under the first message.

Twenty-five lines are gibberish, one reads. The eye finds it at once, but a program needs some sign by which English text differs from gibberish. Chapter 8 supplied one: English letters have very different frequencies. E makes up 12.4% of the letters in War and Peace, while z and q get less than a tenth of a percent each. Meaningful text is full of frequent letters; gibberish has no more of them than of rare ones. Add up the frequencies of all the letters of a candidate: the bigger the sum, the more the text looks like English.

The winner is more than a hundred points ahead of second place. The note itself hints at what awaits in the second room. And from the first room we carry away a lesson: a cipher with a small number of keys has no protection, however much cunning went into it. There must be so many keys that the search never ends.

Room 2. Substitution

In the second room the letters are scrambled every which way. The key here is the whole alphabet, shuffled like a deck of cards: a is replaced by the first card of the deck, b by the second, and so on to z. This is a simple substitution cipher. Caesar’s cipher is a special case of it, in which the deck isn’t shuffled, only cut. The substitution table is conveniently kept in a dictionary, and dict(zip(…)) builds a dictionary from two strings, like the pairs in Chapter 8.

There are as many shuffled alphabets as there are permutations of 26 letters: $26!$, a number with twenty-seven digits. The lesson of the first room has been learned: brute force is hopeless here.

Trying a billion keys a second would take $1.3 \cdot 10^{10}$ years. What does that compare with?

a few centuries the age of the Earth almost the age of the universe

The universe is about 13.8 billion years old, $1.38 \cdot 10^{10}$, and the search would take nearly as long. Even if every one of the eight billion people on Earth tried a billion keys a second, it would still take about a year and a half.

Here at last, it would seem, is a reliable cipher. And it was used for centuries, by diplomats, conspirators and lovers. It was broken not by brute force but by observation, and a very long time ago.

We already have the count: the table FREQ from Chapter 8. We’ll take three thousand characters of War and Peace, starting from the words “At the edge of the road stood an oak,” encrypt them with a random substitution, and try al-Kindi’s method head-on: the most frequent letter of the ciphertext is e, the second is t, and so on.

The result: 55% of the letters are right, and still the words don’t read. E fell into place, since it is far more frequent than any other letter, and with it t, a, n, r, d, l and a few rare letters. Further down the frequencies are too close: in the language o, n, i, h and s lie within little more than one percentage point of each other, and in a passage of three thousand characters their order is easily shuffled. Here s overtook o, n, i and h. Frequencies give only a first approximation. The rest is up to a human mind: short words, doubled letters, familiar endings. Try it yourself: the message of the second room is encrypted the same way.

For a thousand years cryptanalysts worked this way: count the frequencies, then guess and correct. But the hunch “this looks like a word” can be handed over to a program too. We’ll score a decryption by pairs of adjacent letters: in English text the pair “th” turns up all the time, and “qz” never does. Start from the guess by frequency and swap the letters of the key two at a time. If the text becomes more plausible, keep the swap; if not, undo it. This is how you climb a hill in fog: step wherever the ground is higher.

The weight of a pair is the logarithm of its frequency. The probability of a whole text is the product of the probabilities of its pairs, and the logarithm of a product is the sum of the logarithms. Adding is more convenient than multiplying thousands of tiny numbers, which would otherwise collapse into zero: the floating-point numbers of Chapter 28 can only get so small. The program reads the whole message in under a second, and most of that time goes on counting pairs across the novel. The twenty-seven digits in the number of keys didn’t help at all.

Room 3. The indecipherable cipher

Beating frequency analysis takes a stronger weapon, and in 1553 the Italian Giovan Battista Bellaso published one in a small book on ciphers. Let every letter be shifted in its own way: the first by the number of the first letter of a keyword, the second by the number of the second, and so on around and around. If the key is “twig”, the first letter is shifted by 19 (t), the second by 22 (w), the third by 8 (i), the fourth by 6 (g), and the fifth by 19 again. The same e turns now into x, now into a, now into m or k, and the most frequent letter of the language dissolves among the others.

The cipher was named after the Frenchman Blaise de Vigenère, although in 1586 he described a different and stronger variant; this one was pinned on him by a mistake of nineteenth-century historians. The mistake was never put right, and the Vigenère cipher goes by that name to this day. Over three centuries it earned the nickname “the indecipherable cipher.” The function vigenere in the course module is caesar with a shift that changes from letter to letter. The third room holds a longer message, Tolstoy again, and the oak again. Here is what has become of the frequencies.

We threw out the spaces: they give away the lengths of words, and an experienced codebreaker guesses short words from them. Cipher clerks did the same. The frequencies of the ciphertext have flattened: e makes up thirteen percent of the plaintext, while the most frequent letter of the ciphertext gets less than seven, and the rest run almost neck and neck. Al-Kindi’s method is powerless here. People lived with that for three centuries.

Kasiski’s idea goes like this. The key repeats, and so do words and syllables in a text. If the same group of plaintext letters falls twice on the same position of the key, it is encrypted the same way both times, and a repeat appears in the ciphertext. The distance between such repeats is a multiple of the key length. So find identical chunks in the ciphertext, measure the distances, and see what they are all divisible by. For that we have the greatest common divisor of Chapter 5: in the math module it is called gcd.

The greatest common divisor came out as 2, which would mean a two-letter key. But the list tells more: every distance except 226 and 452 is divisible by 8. Those two come from a single coincidence, a four-letter chunk of ciphertext that repeated with no help from the key. The key most likely has eight letters. That is Kasiski’s method for you: a short message has few repeats, one stray repeat at a “wrong” distance ruins the common divisor, and then you have to see what most of the distances are divisible by. In the 1920s the American cryptologist William Friedman proposed a more reliable method, and it is about frequencies again.

Pick two letters from a text at random. What is the chance that they are the same? In English text, where e and t turn up constantly, about 6.6%. In a text where all 26 letters are equally frequent, $1/26 \approx 3.8\%$. This probability is called the index of coincidence, and a substitution cipher leaves it alone: renaming the letters doesn’t change their frequencies. Suppose the key length is $k$, and cut the ciphertext into $k$ columns: the first gets the letters numbered $0, k, 2k, \ldots$, the second $1, k + 1, \ldots$, and so on. If the guess is right, each column is encrypted with one shift, which makes it an ordinary Caesar, and its index is that of English, 0.066. If the guess is wrong, each column mixes different shifts, and the index sinks toward 0.038.

Eight shoots up to 0.0656, practically the index of English. Four and twelve rise as well, since their columns mix only two shifts each; at the other lengths a column mixes four or eight. The key length has now been found twice, by two independent methods. Next, take each of the eight columns, break it as a Caesar with the function likeness from the first room, and put the eight shifts together into the key. Do it by hand on the ruler below, then check against the program.

The key is “otradnoe”. Otradnoe is the Rostovs’ estate. In the spring of 1809 Prince Andrew drove past the old oak of the second room; in mid-May he stayed at Otradnoe, and in early June, on his way home, he rode into the same grove and at first failed to recognize the oak in its new leaves. That is what the message of the third room is about. The function max with the key argument from Chapter 10 picks the shift with the greatest likeness, and the decrypted line runs without spaces but reads. The door of the third room is open.

What undoes Vigenère is repetition. An eight-letter key gives eight Caesar ciphers, and each gives in within a second. The longer the key, the shorter the columns and the thinner their statistics: with a key a hundred letters long and a message of a thousand, each column has ten letters, and the frequencies say almost nothing. And what if the key is as long as the message itself and contains no word at all, only random letters?

Room 4. The door that can’t be opened

In the fourth room lies a short message, and next to it a note: “The key is random letters, as many as there are letters in the message, and they are used once.” This is Vigenère taken to the limit: the key never repeats, there are no Kasiski columns, and every letter is encrypted with its own shift, chosen by lot. Try to read it.

Type whatever you like: each time there is a key under which the ciphertext means what you wrote, whether “meet me at noon by the old oak tree”, “operation off, everyone go south” or any other 27 letters. Each such key is every bit as good as the real one, since all of them are equally random. The ciphertext tells nothing but the length of the message. Neither brute force nor frequencies will help here, and this can be proved.

A cipher with such a key is called a one-time pad: the keys were printed in pads, and the sender tore out and burned each sheet once it was used. The machine version was invented in 1917 by Gilbert Vernam, an engineer at the American telephone company AT&T. A teleprinter sent letters as five-bit codes on punched tape, and Vernam proposed combining each code with a code from a second tape, the key tape. He received a patent in 1919. An Army Signal Corps officer, Joseph Mauborgne, added the decisive condition: the key tape must be perfectly random and must never repeat. Later it turned out that a California banker, Frank Miller, had described the same scheme for the telegraph as early as 1882, in a book of telegraph codes, but it had been forgotten.

Vernam added the bits modulo 2: this is exclusive or, XOR, the gate from Chapter 29. In Python it is the operator ^: for each pair of bits it gives 1 if the bits differ and 0 if they are the same. We need one property of it: applied twice with the same key, it gives back the original, $(m \oplus k) \oplus k = m$. So encryption and decryption are the same operation. We get the bytes of a message with the method encode, as in Chapter 28, and a random key from the module secrets, which, as Chapter 26 explained, takes its randomness from the operating system. The Mersenne Twister won’t do for keys, because it is predictable.

Run the cell a few times: the ciphertext is new every time, but the third line is always “abort, go home.” For any ciphertext and any message of the same length there is a key that turns one into the other. Here is the same thing stated as a theorem.

This property is called perfect secrecy. It was proved by Claude Shannon, the man who in Chapter 29 translated logic into the language of relays. In 1945 he wrote a classified report on a mathematical theory of cryptography, and in 1949 he published an open version, Communication Theory of Secrecy Systems. The same paper proves the converse: perfect secrecy costs a key at least as long as the message.

That price is the whole trouble. A key as long as the message has to be delivered to the receiver in advance and in secret: for every page of correspondence, a page of random numbers. It can’t be kept on a server along with everything else, and it can’t be used twice. Why not follows from the same algebra: if two messages $m_1$ and $m_2$ were encrypted with the same key $k$, then

$$c_1 \oplus c_2 = (m_1 \oplus k) \oplus (m_2 \oplus k) = m_1 \oplus m_2.$$

The key has canceled out. What is left is a mixture of the two messages, and a mixture of two English texts has structure: a guess about any piece of one message immediately reveals the same piece of the other.

Even without a guess the mixture says a lot. The bytes of lowercase English letters all begin with the same three bits, 011, so where two letters meet, those bits cancel, and the mixture is full of bytes from 00 to 1f. Where a letter meets a space, which is 20, the byte jumps to 40 and above: it is that letter in upper case. So the leak shows where the spaces of both messages fall. And a guess about the beginning of the first message (weather reports always begin the same way) reveals the beginning of the second. Go back to the widget, to the tab “The pad twice,” and do this letter by letter: every letter you guess in one message reveals a letter of the other.

The one-time pad was used where a mountain of random numbers could be exchanged in advance. It protected, for example, the teleprinter of the Moscow–Washington hotline, opened in 1963: each side delivered the key tapes through its embassy. For everyone else it is impractical. The door of the fourth room can’t be opened, and that is its main lesson: security can be proved. But keys that can’t be delivered turn out to be as weak a spot as a weak cipher.

The Enigma machine

Here the quest breaks off. In the Second World War, the convoys in the Atlantic and the lives of many people depended on whether the next cipher could be read. So from here on the story is told plainly: how the machine worked and who broke it.

The German engineer Arthur Scherbius filed a patent application for a cipher machine on February 23, 1918, and from 1923 his firm sold it under the name Enigma, at first to banks and trading companies. The navy adopted the machine in 1926, the army by 1928. From the outside it is a typewriter in a wooden box: a keyboard, and above it a panel of 26 lamps marked with letters. Press a key, and a lamp lights up with the letter of the ciphertext. Inside is a mechanical Vigenère with a very long key.

The current from a key passes through three rotors, disks with 26 contacts on each side joined by wires in a jumbled order. Each rotor is a substitution cipher. Then the current reaches the reflector, which connects the contacts in pairs and sends the current back through the same three rotors by a different path, and only then does a lamp light up. What matters most, though, is the motion: before every letter the right rotor turns by one position, and the substitution changes. Once every 26 letters the right rotor pushes the middle one, and the middle one, once every 26 of its own steps, pushes the left one. The letter A pressed five times in a row gives five different letters. Finally, in front of the rotors sits the plugboard: ten cables with plugs swap ten pairs of letters on the way in and on the way out.

The same machine in Python takes thirty-odd lines. The wiring is that of the historical rotors I, II, III and reflector B, and you can check yourself against the textbook example: five presses of A with the windows at AAA give BDZGO. Each rotor is described by a string that says which letters A, B, C and so on go to.

Turning a rotor by $s$ positions amounts to a Caesar shift before and after the wiring: the current enters contact $i + s$ of the fixed wiring and leaves from a contact $s$ lower. The method step reproduces the mechanics of the historical machine, quirk included: the middle rotor, once it reaches its notch, steps again on the next key press and pushes the left one. The last line of the cell shows a convenient property: a ciphertext typed on a machine with the same setting turns back into plaintext. The Enigma has no separate decryption mode.

The key was the setting: which three of the five rotors to insert (the army introduced five in December 1938; before that there were three) and in what order, which letters to set in the windows, which pairs to connect on the plugboard. The settings for each day were printed on key sheets a month ahead. How many settings are there in all?

The number of plugboard pairings is counted like this: of the 26 letters we choose 20 for the cables, six are left without one, and the 20 letters are split into 10 unordered pairs, so we divide by the orderings of the six, by the order of the pairs and by the order of the letters within each pair. That makes 159 quintillion, about $2^{67}$, and that is without the ring settings on the rotors, which we leave out for simplicity. Trying them all by hand is unthinkable. But, as the substitution cipher showed, a large number of keys does not by itself make a cipher secure.

The price of the reflector

The reflector was put in for convenience: thanks to it, one and the same setting both encrypts and decrypts. This convenience has a consequence, which you can see on the diagram of the current’s path.

The property looks like a trifle, but because of it the ciphertext reveals something about the message for certain: in every position it holds a letter that is not the plaintext letter. The one-time pad has no such leak. At Bletchley Park this was later put to use.

Warsaw, 1932. A mathematician against the machine

Bletchley Park. Cribs and bombes

By the start of the war the British Government Code and Cypher School had moved to Bletchley Park, an estate northwest of London. Alan Turing, whose machine we built in Chapter 55, came there too. Together with Gordon Welchman he designed the British bombe. The Polish bomba found the setting by way of the doubled message key, but in May 1940 the Germans stopped doubling it, and a foothold was needed that didn’t depend on procedures. It came from the crib, a piece of plaintext that is almost certainly in the message.

Military traffic is monotonous. Weather stations sent their report every morning in the same format, with the word WETTER, “weather.” Posts with nothing to report said so in so many words: KEINE BESONDEREN EREIGNISSE, “nothing special to report.” Long messages began with FORT, “continued.” If you know which word is in the message, it remains to find out where, and here the theorem about the reflector helps. Lay the crib against the ciphertext at some position. If even one letter of the crib matches the ciphertext letter under it, that position is impossible: the Enigma doesn’t encrypt a letter to itself.

Of the 27 positions, 15 remain, and the right one, number 14, is among them. The crib doesn’t pinpoint the position, but it cuts down the work and, more valuable still, gives for every possible position twenty-seven pairs of the form “plaintext letter, ciphertext letter.” Turing’s bombe ran through the rotor positions and checked, for each one, whether all these pairs could hold at once under some plugboard or other. Welchman added the “diagonal board,” which used the fact that the plugboard swaps letters in pairs and cut off contradictions even faster. Almost all positions fell away at once, and the few that remained were checked by hand on a copy of the Enigma.

The first British bombe, “Victory,” went into operation at Bletchley Park in March 1940, and by the end of the war there were more than two hundred. They were run mostly by women of the Women’s Royal Naval Service. In January 1945 nearly nine thousand people worked at Bletchley Park and its outstations, about three quarters of them women. For decades they said nothing of what they had done: the work stayed secret until the mid-1970s. How many lives the reading of Enigma saved and how much it shortened the war, historians still argue; what is beyond dispute is that the fate of convoys and of people depended on it.

What’s on the doors today

After the war ciphers moved into computers, and letters gave way to bits. In 1977 the United States adopted the DES standard, with a 56-bit key. At the time that seemed enough, but brute force gets cheaper every year: in 1998 the nonprofit EFF built a machine called Deep Crack for less than $250,000, and it found a DES key in 56 hours, trying more than 90 billion keys a second. Here is every lock in the bureau measured against it.

Every extra bit of key doubles the work, and the difference between 56 and 128 bits is not a factor of two and a bit but a factor of $2^{72}$. To replace DES, an open competition was announced in 1997: fifteen ciphers from teams all over the world, and more than two years of public attacks on one another. On October 2, 2000, the winner was named, the cipher Rijndael by the Belgians Joan Daemen and Vincent Rijmen, and in November 2001 it became the AES standard. Today it encrypts almost everything: connections to websites, the storage of phones, archives.

AES is a block cipher: it takes 16 bytes and turns them into another 16 bytes. Inside are rounds, ten for a 128-bit key, and in every round you can recognize the rooms of the bureau. First each byte is replaced according to a table: that is the substitution of the second room, only with an alphabet of 256 “letters,” and with a table chosen to have no convenient regularities. Then the bytes are rearranged and mixed, so that each byte of the result depends on several bytes of the input. Then a round key is added to the block with XOR: the fourth room. And again. In the same 1949 paper Claude Shannon named two properties a good cipher must have: confusion, when the relation between the ciphertext and the key is complicated, and diffusion, when every bit of the plaintext affects many bits of the ciphertext. Substitution confuses, mixing diffuses, and the rounds pile one on top of another until nothing is left of the statistics of the language.

AES uses one and the same key for encryption and decryption, like every cipher in this chapter. Such ciphers are called symmetric. But there is no need to write AES yourself for production code.

Why you shouldn’t invent your own cipher

This is Kerckhoffs’s rule in action: the secret of the design held only until someone picked up a microscope. Look back at the rooms of the bureau. A small number of keys gets brute-forced. A large number doesn’t help if the cipher preserves the structure of the text, which statistics will then break. A repeating key turns a complex cipher into several simple ones, and even the pad, whose security is proved, falls to a reused key. And the story of the Enigma showed that a flaw allowed for the sake of convenience, together with human habits, opens what would have withstood brute force. None of these weaknesses is visible from the inside. A designer’s confidence in their cipher means only that they haven’t thought of a way to break it.

There is a second half to the lesson. A good cipher won’t save you from bad handling of keys: a key written down next to the ciphertext, one pad for two messages, passwords that can be guessed. Mistakes in systems built from sound parts are the subject of Chapter 61. But first comes a question we have been avoiding all along.

Tasks

Four tasks, one for each technique of the bureau. The module cs.ciphers holds the chapter’s tools: ALPHABET, FREQ, letters, caesar, likeness, vigenere and the class Enigma. Feel free to use them.

An enemy radio station encrypts its messages with Caesar all day long, and all the messages of one day share the same shift, the key of the day. Write break_day(messages): given a list of intercepts, return a list of their decryptions in the same order. The intercepts are strings of lowercase English letters, spaces and punctuation; the cipher leaves spaces and punctuation alone. The trouble is that many intercepts are very short: “yes”, “no”, “wait”. There may also be a day without intercepts, and then the answer is an empty list; for a day of three thousand intercepts the tests allow two seconds. The starter breaks each intercept separately, as in the first room: run the tests and find out what trips it up.

A two-letter “kv” could just as well be “do” as “it”: two letters give the statistics nothing to stand on. But the shift is shared by all the intercepts.

Find the shift once, from all the intercepts at once. For example, join them into one long string with spaces and break that. Then decrypt each intercept with this shift.

One at a time, short intercepts can’t be broken: likeness on two letters goes wrong all the time. Together they make hundreds of letters, and the shift is plain at once. It was the same with the Enigma: the setting was shared for the whole day, so each message that was broken opened all the others, and the weather reports and “nothing to report” supplied the cribs. An empty day is handled too: " ".join([]) is an empty string, and the answer is an empty list. The solution is also fast: the twenty-six shifts are checked once for the whole day.

Write key_length(cipher): given a Vigenère ciphertext made only of lowercase English letters, return the length of the key, a number from 1 to 20. The keys in the tests are random, and the messages are pieces of War and Peace from 600 to 2500 letters long; every column gets at least fifty letters. If both a length $k$ and a multiple of it, $2k$ or $3k$, fit, the answer is the smallest. For forty ciphertexts of 1500 letters each the tests allow two seconds. The starter is Kasiski’s method from the chapter: it finds repeats and their common divisor, but it is often wrong.

Kasiski’s method breaks down at a single chance repeat: the common divisor drops straight to one or two. The index of coincidence is more reliable. Compute the average index of the columns for every length from 1 to 20, as in the cell coincidence.py.

It remains to decide which length is the “right” one. You can’t take the highest index: multiples of the length score just as high, and long lengths jump up by chance besides, since their columns have few letters. Take the smallest length whose index is close to that of English, for example above 0.061.

Why so high, and so precise? At half the true length every column mixes two Caesars, and the index of such a mixture runs from 0.048 to 0.055: two frequent letters under different shifts can coincide. Worse, a random key sometimes repeats a letter at the wrong distance, and then at half the length some columns are pure Caesars, which lifts the average to 0.060. The threshold has to lie above all that and below the 0.066 of English.

At the right length and at all its multiples the columns are pure Caesars, and the index is that of English. At every other length the columns mix several shifts, and the index stays below the threshold. So the first length to clear the threshold is the answer. The threshold sits between two worlds: a mixture of two Caesars gives 0.048 to 0.055, a half-mixed average reaches 0.060, and English text gives 0.066. In English the gap between the worlds is narrow, and with fifty letters to a column the threshold has to be set carefully. The whole solution costs $O(20 n)$ operations: forty ciphertexts of fifteen hundred letters are checked in a few tenths of a second.

Two messages were encrypted with the same one-time pad: $c_1 = m_1 \oplus k$, $c_2 = m_2 \oplus k$. Write two functions. xor(a, b) returns the byte-by-byte exclusive or of two byte strings (bytes); if their lengths differ, the result is as long as the shorter one. recover(c1, c2, known) receives both ciphertexts and the known beginning of the first message, known, and returns the same number of bytes from the beginning of the second message, as many as the lengths of all three arguments allow. The tests include megabyte-long messages, which get one second.

zip(a, b) goes through the pairs of bytes and stops by itself at the shorter string. When you loop over bytes, Python hands out integers from 0 to 255, and bytes(…) builds a byte string out of such integers.

Recall the formula from the fourth room: $c_1 \oplus c_2 = m_1 \oplus m_2$. What do you get if you XOR this with $m_1$?

One line, and all of Venona is in it: $c_1 \oplus c_2 \oplus m_1 = m_1 \oplus m_2 \oplus m_1 = m_2$. We never learned the key, and we didn’t need it. The length limit takes care of itself, since zip stops at the shortest of the three. In practice nobody knows the whole first message, and the work goes piece by piece: guess a word in one message, read a piece of the other, guess the next word from it, as in the tab “The pad twice.”

A weather station begins every report with the word WETTER. The reports were encrypted on an Enigma with rotors I, II, III (left to right), reflector B and no plugboard; the position of the rotors at the start of a message is unknown. Write find_setting(cipher, crib), returning a list of all positions, three-letter strings like "QEV" in alphabetical order, at which the decryption of cipher begins with crib. The machine is in the module: Enigma("I II III", "QEV"); its method press(letter) encrypts one letter, and encrypt(text) a whole text. The starter is correct, but it decrypts each message in full at every one of the 17,576 positions. The tests give four messages of 150 letters and three seconds for all of them.

Why decrypt 150 letters if the first one already fails to match the crib? Press one letter at a time with the method press and stop as soon as a letter differs from the crib. For most positions the check ends at the first letter.

There is also a free check before any search. If somewhere a letter of the crib coincides with the ciphertext letter in the same place, no position will fit, because the Enigma doesn’t encrypt a letter to itself. And if the crib is longer than the ciphertext, all the more so.

The for … else construction: the else branch runs only if the loop got to the end without a break, that is, if all the letters matched. The first letter matches the crib at roughly one position in 25 (a letter never goes to itself, which leaves 25 options), the second at one in 25 of those, so instead of $17\,576 \times 150$ key presses you get a little over 17,576, a hundred and fifty times fewer. Going through the alphabet in order gives a sorted list for free. The British bombe did the same mechanically: it spun drums that imitated the rotors, and it also took the plugboard into account. Without the plugboard the problem would have been too easy for Bletchley Park.

What next

The internship is over, and all four doors are behind you. On your way out, look back at the keys. Caesar needs a shift, Vigenère a word, the one-time pad a mountain of random numbers, the Enigma monthly key sheets that couriers carried to units and ships. AES needs 128 random bits. All these ciphers are symmetric: the sender and the receiver hold the same key, and it has to be handed over in advance and in secret. Throughout the history of ciphers, keys were carried by messengers, diplomatic couriers and signal officers. A captured key sheet was worth more than any attack.

Look at the padlock in your browser’s address bar. You have just opened your bank’s website for the first time. You and the bank have never met, nobody brought you a key, and every word you send passes through dozens of strangers’ computers, any of which could record it. And yet, a fraction of a second later, you and the server share a secret AES key that none of the eavesdroppers knows. How do you agree on a secret when everyone hears every word? The answer rests on a kind of hardness related to the problems of the last chapters: a problem whose solution is easy to check but, as far as anyone knows, hard to find. And it came to people twice: openly in 1976, and in secret a few years earlier. That is the subject of the next chapter.