Enigma & Lorenz

Julius Caesar, according to the historian Suetonius, wrote his private letters by replacing each letter with the one three places further along the alphabet. a became D, b became E, and so on. The rule is simple enough to carry in your head, and the reader needs to know only one number to undo it.

It helps to treat letters as numbers, with A = 0, B = 1, and so on up to Z = 25. Encryption then becomes addition, and the alphabet wraps around like the face of a clock: after Z comes A again. Mathematicians call this arithmetic modulo 26.

There are only 25 useful keys, so an enemy could simply try them all. The real weakness goes deeper, and it survives even when the number of keys is enormous. A general substitution, where the 26 letters are shuffled into any order, has 26! ≈ 4 × 10²⁶ possible keys, and it still falls in minutes.

The reason is that a substitution changes what the letters look like but not how often they occur. In English, E makes up about 13 percent of ordinary text, T about 9 percent, and Z less than a tenth of one percent. The Arab scholar al-Kindi described how to count the symbols in a secret message and match them against the known frequencies of the language. The shape of the letter histogram survives encryption, and a Caesar shift merely slides it sideways.

The answer to frequency analysis was to stop using a single alphabet. In 1553 Giovan Battista Bellaso proposed using a keyword to switch between Caesar shifts, one letter at a time. The method was later credited to Blaise de Vigenère and has carried his name ever since. For about three hundred years it was known as le chiffre indéchiffrable, the indecipherable cipher.

The tool is a square of 26 alphabets, each shifted one place further than the one above it. Johannes Trithemius described it as the tabula recta in his Polygraphia, written in 1508. To encrypt, write the keyword repeatedly above the message. Each plaintext letter picks a column, the key letter above it picks a row, and the ciphertext letter sits where they cross.

The effect on the fingerprint is dramatic. Each letter of the key applies a different shift, so the E’s of the message are spread over several ciphertext letters and the tall bars of the histogram melt into each other. The longer the keyword, the flatter the result.

We can measure flatness with one number. The index of coincidence is the probability that two letters picked at random from a text are the same letter. For English it is about 0.067. For letters chosen uniformly at random it is 1/26 ≈ 0.038.

Flat is not the same as random, though. The keyword repeats. If the key has seven letters, then letters 1, 8, 15, 22 and so on were all encrypted with the same shift. Write the ciphertext in rows of seven and each column is an ordinary Caesar cipher, with the full English fingerprint intact.

In 1863 Friedrich Kasiski published a way to find the key length from repeated fragments in the ciphertext. In the 1920s William Friedman made the attack statistical. Try every possible length, split the ciphertext into that many columns, and compute the index of coincidence of each column. At the right length the columns look like English again and the IC jumps. Once the length is known, each column falls to the frequency attack from Chapter I.

Friedman’s attack worked because the key repeats. What if it never did? Suppose the key is a string of truly random letters, as long as the message, used once and then destroyed. This is the one-time pad. It grew out of Gilbert Vernam’s 1917 teleprinter cipher and Joseph Mauborgne’s insistence that the key be random and never reused.

In 1949 Claude Shannon proved that it cannot be broken, however much computing power the attacker has. The argument fits in the figure below. For any ciphertext and any plaintext of the same length there is exactly one key that connects them, and every key was equally likely to be chosen. The ciphertext tells the enemy nothing except its length.

The catch is the key. It must be as long as all the traffic ever sent, delivered in advance to every radio operator, and never used twice. For an army sending thousands of messages a day, that was impossible. The machines of the next two chapters are an engineering compromise. They take a short secret setting and stretch it mechanically into a very long key that only looks random.

Arthur Scherbius patented the Enigma in 1918 and first sold it as a business machine. The German navy adopted it in 1926 and the army in 1928, and by the end of the war tens of thousands had been built. One operator typed on the keyboard, and for each key a lamp lit up on the board above it showing the enciphered letter. A second operator wrote the lamp letters down, and a radio operator sent them in Morse code.

Inside, each key press closes an electrical circuit. The current passes through a plugboard, then through three rotors, bounces off a reflector, comes back through the three rotors by a different route, passes through the plugboard again and lights a lamp. Each rotor is a disc with 26 contacts on each face, wired to each other in a scrambled order. On its own a rotor is just a fixed substitution alphabet. Because the rotors turn, the alphabet of the whole machine changes with every letter.

III.1The stepping mechanism

The rotors turn like an odometer. The right rotor steps on every key press. Each rotor has a notch on its alphabet ring, and when the right rotor passes its notch it pushes the middle rotor one step. When the middle rotor passes its notch it pushes the left one.

One mechanical detail breaks the odometer pattern. The pawl that pushes the left rotor rests on the middle rotor’s notch, so when it pushes, it drags the middle rotor along as well. The middle rotor therefore steps twice in a row, once on the way into its notch position and again on the way out. This is the double step. It shortens the cycle from 26³ = 17,576 positions to 26 × 25 × 26 = 16,900.

III.2The mathematics of a scrambler

Each component of the Enigma is a permutation of the 26 letters, a rule that sends every letter to exactly one other letter. The whole machine is their composition. Write P for the plugboard, R, M and L for the right, middle and left rotors at their current positions, and U for the reflector. A letter passes through P, R, M and L, is reflected by U, and comes back through the inverses. Reading from right to left, the machine applies

A rotor that has turned s places is the same wiring seen from a shifted position. If ρ is the rotor’s wiring and C is the shift A → B → C → …, the turned rotor is C^−s ρ C^s. In the language of group theory, turning a rotor conjugates its permutation by a shift, and every key press changes s.

Now group the terms. With X = L M R P the machine is

The reflector U swaps 13 pairs of letters, so applying it twice does nothing, and it never sends a letter to itself. Two consequences follow in one line each.

1. The Enigma is its own inverse. E² = X⁻¹U X X⁻¹U X = X⁻¹U²X = identity. If A encrypts to Q, then Q encrypts to A at the same setting, so the machine that encrypts also decrypts. The operators liked this.
2. No letter ever encrypts to itself. If E(x) = x, then U(Xx) = Xx, and U has no fixed points. The codebreakers liked this far more.

III.3How many settings?

An army key sheet told operators which three of its five rotors to use and in what order, the ring settings, and which ten pairs of letters to connect on the plugboard. Each message also began from its own starting position. The possibilities multiply.

At a million settings per second, trying them all would take about five million years. The Enigma was not broken by trying them all.

III.4The flaw

Bletchley Park’s codebreakers worked from cribs, pieces of plaintext they could guess. Weather reports contained WETTERVORHERSAGE, the weather forecast. Routine messages said KEINE BESONDEREN EREIGNISSE, nothing special to report. The difficulty was knowing where in the ciphertext the crib sat.

Here the reflector gave the answer away. Since no letter encrypts to itself, the crib cannot sit anywhere that one of its letters lies directly over the same letter in the ciphertext. Slide the crib along the intercept below and watch positions get ruled out.

A 16-letter crib survives a random position by luck with probability (25/26)¹⁶ ≈ 0.53, so this test alone removes about half of the candidates. It narrows the search, and the Bombe finished it.

III.5The Bombe

Alan Turing and Gordon Welchman designed the British Bombe in 1939 and 1940, building on the Polish bomba. With the crib placed at a candidate position, the crib and the ciphertext define a menu. This is a graph whose nodes are letters, with an edge between two letters whenever one was enciphered as the other, labelled with the step at which it happened.

The loops in the menu are what matter. Suppose the plugboard partner of E is some unknown letter. Travelling round a loop, through the rotors at each step’s position, must bring that letter back to itself. For a wrong rotor position almost no choice of partner survives the trip, and the Bombe rejects the position electrically, without anyone having to guess the plugboard.

How can a machine test a loop without knowing the plugboard? It guesses, and follows the consequences. Take the letter with the most connections in the menu and suppose its plugboard partner is A. Every edge at that letter then forces a new connection. If the scrambler at step 23 turns A into K, the letter joined to it at step 23 must be plugged to K, and that conclusion spreads along the next edges in turn. Gordon Welchman’s diagonal board added one more rule: the plugboard swaps letters in pairs, so if T is plugged to K, then K is plugged to T.

At a wrong rotor position the consequences spread until the test letter seems to be plugged to every letter at once, which is impossible, and the Bombe moves on. At the right position they stop short. The machine halts, and the one wire of the test register that stayed dark, or the only one that lit, names the real partner. The Bombe carried all 26 guesses on 26 wires at once, so one electrical test settled every guess for a position.

The real Bombe ran through all 17,576 rotor positions for one wheel order in about twenty minutes. By the end of the war more than two hundred of them were working in Britain, and the US Navy built more. Each stop was checked by hand on an Enigma replica, and when readable German came out, the day’s key was broken. Even then nobody had read the day’s traffic. Every message still had to be decoded on Typex machines, translated and assessed, as Fig. 22 shows.

III.6The fourth rotor

The German navy guarded its Enigma more closely than the army did. Its operators chose their three rotors from a box of eight rather than five. On 1 February 1942 the U-boats in the Atlantic switched to a new machine, the M4. Bletchley Park called the new U-boat key Shark, and for ten months it could read almost none of it.

The M4 made room for a fourth rotor by using a thinner reflector, and the fourth rotor was thin as well. It sits between the reflector and the left rotor, and it never turns while the operator types. It is set by hand to one of 26 positions before the message begins. There were two of these thin rotors, called Beta and, from July 1943, Gamma. Switch Fig. 7 to the M4 to see where it sits.

Mathematically, little changed. Group the middle terms and G⁻¹U′G is itself a reflector. It swaps 13 pairs of letters and leaves none in place, because U′ does the same. So the M4 is still its own inverse, and it still never encrypts a letter to itself. In effect the fourth rotor offers 26 different reflectors to choose from, and that is all it does.

On paper the gain in key space was modest. Eight rotors instead of five, plus a fourth rotor with 26 positions, add about seven bits to the army machine’s 67, and the plugboard still dominates. The trouble for Bletchley was where those bits landed. The Bombe never searched the plugboard, because its loops dealt with the plugboard by logic. It searched rotor positions by brute force, and the fourth rotor multiplied exactly that search by 26.

Bletchley got back in through captured paper rather than faster machinery. On 30 October 1942 sailors from HMS Petard boarded the sinking U-559 in the eastern Mediterranean and recovered its short-signal book and short weather cipher. Lieutenant Tony Fasson and Able Seaman Colin Grazier went down with the submarine. The documents gave cribs for the U-boats’ brief weather reports, and on 13 December 1942 Shark was read again.

The lasting answer was more Bombes, and faster ones built for four rotors. The US Navy’s high-speed four-rotor Bombes, designed by Joseph Desch at the National Cash Register Company in Dayton, Ohio, came into service in the summer of 1943 and carried much of the Shark work from then on. The fourth rotor never moves, so it added nothing to the period of the machine.

The Enigma carried tactical traffic in Morse. For the highest level of command, between Berlin and the army groups, the German army used teleprinters that sent text automatically over radio. The Lorenz company built an attachment for them, the Schlüsselzusatz SZ40 and later SZ42, which encrypted the signal on the fly. Bletchley Park called all German teleprinter ciphers Fish, and this one Tunny.

IV.1Five holes per letter

A teleprinter does not send letters as such. It sends the International Telegraph Alphabet No. 2, the Baudot–Murray code, in which every character is five binary pulses called impulses. On paper tape each impulse is a hole or no hole. Five bits give 32 codes: the 26 letters, and six control characters for space, carriage return, line feed, the shift to figures, the shift back to letters, and a blank.

IV.2Adding a key, bit by bit

Lorenz encrypted with the rule Gilbert Vernam had devised for teleprinters in 1917. Each impulse of the message is combined with an impulse of key by exclusive-or, written ⊕. The result is 1 if exactly one of the two bits is 1. Exclusive-or is addition modulo 2, the binary version of Caesar’s addition modulo 26.

Like the Enigma, the same operation encrypts and decrypts. That symmetry will matter again shortly.

IV.3Twelve wheels

The key came from twelve wheels with cams around their rims. Each cam could be set raised or lowered, and the cam at the reading position gave one bit. Five χ (chi) wheels, one per impulse, had 41, 31, 29, 26 and 23 cams and stepped once per character. Five ψ (psi) wheels had 43, 47, 51, 53 and 59 cams and stepped together, but only when the two motor wheels allowed it. The μ61 motor wheel stepped every character and moved the μ37 wheel whenever its own cam was raised. The ψ wheels moved whenever μ37’s cam was raised.

The sizes share no common factors, so the χ wheels alone come back to their starting positions only after 41 × 31 × 29 × 26 × 23 = 22,041,682 characters. With 501 cams to set, the machine seemed impossibly complex.

IV.4The depth

On 30 August 1941 an operator sent a message of about 4,000 characters from Athens to Vienna. The receiving operator asked for it again, and the sender repeated it with the same machine setting, which was forbidden. He also abbreviated as he retyped, so the two texts were not identical. SPRUCHNUMMER, message number, became SPRUCHNR.

Two messages sent with the same key are said to be in depth, and the key simply cancels.

What is left is two plaintexts added together. Guess a word in one of them, add it at the right place, and the other message appears. John Tiltman worked through both texts this way and recovered almost 4,000 characters of key.

IV.5Tutte’s rectangle

Tiltman’s key was a stream of 4,000 characters with no machine to explain it. Nobody at Bletchley had seen a Lorenz machine. Bill Tutte, a 24-year-old chemistry graduate recruited from Cambridge, took the first impulse of the key and wrote it out in rows, looking for a width at which the columns would repeat. It is Friedman’s column trick from Chapter II. At a width of 41 a pattern appeared.

The pattern was blurred, because the key is χ ⊕ ψ′ and the ψ wheels add noise. It becomes much clearer in the difference of the key, the sum of each character and the one before it, written Δ. Whenever the ψ wheels stand still, Δψ′ = 0, and the difference of the key equals the difference of the χ wheel.

From patterns like this Tutte and his colleagues in the Research Section reconstructed the logical structure of the whole machine, all twelve wheels and the motor, by January 1942. It was one of the great intellectual feats of the war. The British did not see an actual Lorenz machine until 1945.

IV.6Colossus

Reading Tunny day to day meant finding the wheel settings of each message without the luxury of a depth. Tutte found a statistical way in. The difference trick works on the ciphertext too. For impulses 1 and 2,

The right-hand side is 0 more often than 1. German teleprinter text is full of repeated characters, where ΔP = 0, and the ψ wheels often stand still, where Δψ′ = 0. So if you guess the starting positions of χ₁ and χ₂ correctly and count how often the left-hand side is 0, the count comes out noticeably above half. For a wrong guess it stays close to half. There are 41 × 31 = 1,271 guesses to test.

Counting that by hand was hopeless. Max Newman proposed a machine, and Tommy Flowers, an engineer at the Post Office, built one with about 1,600 valves. Colossus read the ciphertext from a loop of paper tape at 5,000 characters a second and counted electronically. It attacked its first message in February 1944. An improved Mark 2, with 2,400 valves, was running on 1 June 1944, days before D-Day.

With χ₁ and χ₂ set, the other three χ wheels needed only short runs of 29, 26 and 23 settings, each pairing the new wheel with one already found. Once all five were known, Colossus could strip them from the ciphertext. What remained is called the de-chi: the plaintext with only the ψ stream added.

The de-chi went to the Testery, Major Ralph Tester’s section, where the motor and ψ settings were found by hand, and a British-built Tunny machine set to all twelve wheels printed the German. Colossus itself never produced a line of plaintext. The simulation does that part with statistics instead. Wherever the motor holds the ψ wheels still, a doubled letter in the plaintext shows up as a doubled letter in the de-chi, and that finds the motor. Then each ψ wheel in turn is set to the position that makes the text read most like German.

Each of these ciphers turned a small secret into a long key, and each stretch left structure behind. Caesar used one shift for the whole message. Bellaso’s keyword repeats. The Enigma’s rotors cycle, its plugboard never moves, and its reflector forbids a letter from becoming itself. The Lorenz wheels are periodic and their ψ wheels pause together. Every break on this page found that structure and measured it.

The machines were rarely the weakest part. The breaks came from operators who repeated message keys, sent the same text twice, or began every report with the same words. Auguste Kerckhoffs had warned in 1883 that a cipher system must stay secure even if the enemy knows everything about it except the key. Enigma and Lorenz were built on the hope that the machines themselves would stay secret, and in the end the enemy knew everything about them.

V.1No machine read a message

It is tempting to picture the Bombe or Colossus printing out German orders. Neither did. The Bombe produced a few candidate rotor settings, Colossus a few wheel positions. Before and after them stood thousands of people: intercept operators copying Morse through the night, analysts sorting the traffic, codebreakers finding cribs, Wrens running the machines, typists, translators and intelligence officers. By 1945 nearly 10,000 people worked at Bletchley Park and its outstations, about three-quarters of them women.

Follow a message through either lane below. The machines on this page sit in the amber stages. Everything else was done by hand, and every stage passed a different product to the next.

Bletchley Park’s work remained secret until the 1970s. Most of the Colossi were broken up after the war, and Tutte’s reconstruction of the Lorenz machine was publicly recognised only decades later.

Every cipher on this page is symmetric: the same secret sits at both ends of the line. It was Caesar’s shift, Bellaso’s keyword, the Enigma’s daily key sheet, the settings of the Lorenz wheels, the one-time pad. Symmetric ciphers can be very strong, and today’s are. Their weak point was the key itself, which had to be printed, carried and guarded, and could be captured, as U-559’s codebooks were.

In 1976 Whitfield Diffie and Martin Hellman showed how two people can agree a secret key while an eavesdropper hears every word they exchange. The idea rests on the clock arithmetic of Chapter I. Raising a number to a power modulo a prime is quick. Going backwards, finding the power from the result, is called the discrete logarithm, and for large primes nobody knows a fast way to do it.

Diffie–Hellman agrees a key but cannot tell you who is on the other end. Public-key encryption and signatures add that. In 1977 Ron Rivest, Adi Shamir and Leonard Adleman published RSA, in which each person has two keys. The public key works like an open padlock that anyone can snap shut, and only the matching private key opens it again. Multiplying two large primes is easy. Recovering them from their product is the hard problem that keeps the private key private.

Public-key arithmetic is slow, so it is used only to agree or carry a key. The message itself goes through a fast symmetric cipher. When your browser opens a page over https, it runs an elliptic-curve version of Diffie–Hellman with the server, checks the server’s signature against a certificate, and then encrypts everything with AES or ChaCha20 under the fresh shared key. Every session gets a new key, so there are no depths to exploit, and every part of the design is public, as Kerckhoffs asked.

Real keys are far larger than the ones in these figures. Diffie–Hellman primes run to more than 600 digits, or elliptic curves give the same strength with shorter numbers, and RSA moduli have 617 digits or more. The best known attacks on them would need something like 2¹¹² to 2¹²⁸ operations, which no computer on Earth can do.