Tag: Enigma

It started with a certificate.

I work in public key infrastructure. The shorthand for what I do is PKI, and the practical version is that I spend my days working with the systems that make it safe to type your bank password into a web browser. I’m the person who needed to understand what the cryptographer’s work means for the world I live in, and I did the work to find out, and now I am going to walk you through it. For the last thirty years, almost all of that work has rested on a small family of math problems that everyone in my field knows by name: RSA, ECC, Diffie-Hellman. These are the foundations of your bank login, your encrypted messages, your software updates, and roughly every secure connection on the internet.

The industry I work in is in the middle of replacing all of it.

The reason we’re replacing it is a kind of computer that does not yet exist. Quantum computers, the real ones, capable of breaking the cryptography that protects the internet today, are still years away. But the migration to new algorithms is happening now, and it is happening because of a credible threat from a machine almost nobody, including most of the people in my own industry, actually understands.

I needed to understand it. So I started reading.

What I found was that the articles available to a smart non-specialist reader are not very good. They tell you that quantum computers try every possibility at once. They tell you a qubit (short for quantum bit) is both 0 and 1 at the same time. They tell you it’s like a coin that’s both heads and tails until you look at it. Each of these explanations gestures at something profound, and then backs away before saying what the something actually is. After a few weeks of reading, I started to suspect that most of the writers did not understand the thing they were trying to explain.

This is the first of several posts about what I found when I kept going. By the end of the series, you will have a real understanding of how a quantum computer breaks the cryptography that protects almost every secure connection you make in a day. There will be no hand-waving. There will be some work for you to do, and I will not waste your effort.

But to get there, we have to throw out almost everything you have been told about what quantum computers are. The best way I have found to do that is to start somewhere most of us have already been: with a man named Alan Turing, a machine called the bombe, and a code the Germans thought could not be broken.

This first post is about that machine and that code. It is about how something the Germans considered mathematically impossible to break was broken anyway, day after day, by exploiting a single tiny weakness in the machine. The reason we are starting here is that the same principle is what makes quantum computers dangerous to the cryptography we use today. Once you see what Turing did at Bletchley Park, the rest of the series is the modern version of the same story.

The code the Germans trusted

If you have not seen The Imitation Game, I highly recommend it. The film is a useful entry point to a story that matters here, and most of what I am about to walk you through will land more easily if you have a picture in your head of Bletchley Park, Alan Turing, and the rooms where the work happened. If you have already seen it, I am going to take you a layer deeper than the film does, into how the machine actually knew it had won.

Here is the setup. The Germans, during the Second World War, encrypted nearly all of their military communications with a machine called Enigma. Enigma was about the size of a typewriter. It had a keyboard, a set of rotors that scrambled letters as you typed, a plugboard that swapped letters around before and after the rotor stage, and a daily setting that changed all of those configurations at midnight. The Germans used it for everything from U-boat coordinates to weather reports to the communications of the German high command.

The reason the Germans believed Enigma was unbreakable came down to one number.

A standard three-rotor Enigma with a ten-pair plugboard had exactly 158,962,555,217,826,360,000 possible settings. About 159 quintillion. The Germans looked at that number and concluded, reasonably, that no machine of their era could ever grind through 159 quintillion possibilities by counting. They were right about that part. They were wrong about everything else.

The German Navy used an even more complex four-rotor version of Enigma, which made the math harder still. The British codebreakers eventually broke that one too, but it took longer, and there was a period in 1942 when they could not read U-boat traffic at all. Hold that detail. We will come back to the idea of “just make the key bigger” later in the series, because it is exactly the move companies will reach for when they hear that quantum computers can break the cryptography we use today.

The hidden crack

Enigma had one rule baked into its physics that the Germans did not understand was a vulnerability.

Because of how the machine’s reflector was wired, no letter could ever encrypt to itself. An A could become any of the other twenty-five letters of the alphabet, but never an A. A B could become anything except a B. This sounds like a tiny detail. It was the crack that broke everything.

To see why, think about a detective working a case. The detective knows one ironclad rule: the culprit cannot have been somewhere else at the time of the crime. Every suspect with a verified alibi is eliminated instantly. Not by proving them innocent. By structural impossibility. The detective does not have to investigate those suspects further. The alibi rules them out.

Enigma’s quirk worked the same way. Any guess that required a letter to encrypt to itself was instantly, structurally impossible. Alibied out. No further checking needed.

This is the first move you should hold on to, because it returns later. The way you break something that looks unbreakable is not by checking every possibility. It is by finding a structural rule that lets you eliminate entire categories of possibilities at once.

Cribs

Even with the no-self-encryption rule, the machine Turing designed could not work in a vacuum. That machine was called the bombe, a name borrowed from the bomba kryptologiczna built by Polish cryptographers who had been attacking Enigma since the 1930s and whose work Turing’s design built on. A later refinement by Gordon Welchman, the diagonal board, was what made the bombe practical, by ruling out most of the false leads that would otherwise have buried the real answer. The bombe needed a foothold. That foothold was something codebreakers called a crib: a guessed fragment of plaintext (the original message, before encryption). The encrypted version, the scrambled output that came over the radio, is called the ciphertext.

The Germans were creatures of habit. Weather reports broadcast on regular schedules always began with the word WETTER, the German word for weather. Routine military messages ended with HEIL HITLER. Operators, against orders, repeatedly used their girlfriends’ names or simple keyboard patterns like QWERTZU as the message-specific settings that prefaced the real ciphertext. The film The Imitation Game dramatizes this as a single character whose German counterpart always used the name Cilly. The real history calls these patterns Cillies, and they were not the work of one operator. They were a class of operational discipline failures committed across the entire German military for years.

The codebreakers did not see the plaintext. They inferred it. From radio traffic analysis, captured codebooks, and operational pattern recognition, they knew which intercepted messages were weather reports, and they knew weather reports began with WETTER. They could not read the message yet. They could guess what its first six letters had to be.

A guess, combined with a structural rule, was enough.

How the bombe worked

Turing’s insight was that you could compile the logical implications of a crib into an electrical circuit.

Here is what that means in plain language. Suppose you guess that a particular stretch of ciphertext is the encryption of WETTER. If your guess is right, and if the rotor positions you are testing are right, then a chain of letter relationships is implied. The first ciphertext letter must be the encrypted form of W. The second must be the encrypted form of E. And so on. Those relationships form a web of constraints. The bombe energized the entire web at once with electrical current.

For most rotor settings, the web of constraints contradicted itself. The current would flow through the wires and find that the rotor setting required letter A to equal letter B, and also required letter A to equal letter C, and also required letter A to equal letter Q. Three different requirements for the same letter. Impossible. Current would distribute itself across all twenty-six possibilities for some test letter, which the machine read as “everything is still possible, no information yet, this setting is wrong, move on.”

For one rotor setting in the entire space, the contradictions collapsed. Every implication held. Current flowed through exactly one wire for the test letter, with the other twenty-five dark. A relay clicked. A motor stopped. An operator wrote down the setting.

The bombe had not read anything. It had not decrypted a message. It had found the one rotor configuration where the hypotheses generated by the crib did not contradict themselves.

The speed of it

The mechanical part of the bombe was not slow. The top drum of each rotor assembly spun at about one hundred rotations per minute. A single bombe could run through all 17,576 possible rotor positions in roughly twenty minutes. With thirty-six rotor sets working in parallel, and often several bombes running at once, the codebreakers at Bletchley Park were frequently cracking the daily Enigma key within an hour of getting a viable crib.

Twenty minutes. Out of a space of 159 quintillion settings.

The Germans were not wrong that 159 quintillion was a number too large to count through. They were wrong to assume that counting through it was the only way to break their cipher.

You do not defeat an astronomical number by counting through it. You defeat it by exploiting structure.

That sentence is the spine of everything we are going to talk about for the rest of this series. Hold it. We will come back to it more than once.

What the bombe was actually looking for

There is one more thing to notice about how the bombe worked, because it is the move that connects directly to quantum computing.

The bombe did not test rotor settings by decrypting messages and checking whether the result looked like German. It would not have known German if it saw it. It searched for consistency. At the right rotor setting, the implications generated by the crib held together. At every wrong setting, they contradicted themselves.

Read that again, because it is the part most explanations of the bombe miss. The bombe did not check answers. It arranged a physical situation where every wrong setting destroyed itself, and the right one was simply the setting left standing.

What the bombe tells us about computers

The bombe was not a general-purpose computer. It was a single-purpose machine, built to attack one cipher, and it could not do anything else. But the way it worked tells us something important about what every computer is, including the one you are reading this on.

A computer is a physical machine that arranges electricity, or light, or atoms, according to rules, and produces an output we can read. The bombe was electromechanical. Your laptop is silicon. Different substrates, same kind of thing.

What makes a machine computational is that the mathematical structure of a problem can be compiled into physical structure. The bombe’s wires were Enigma’s logical relationships rendered in copper. Your laptop’s transistors are the rules of arithmetic and logic rendered in silicon. The bombe did not think about Enigma. The bombe was Enigma’s logic, run backward in electricity.

Every computer that has ever existed works the same fundamental way. Your laptop, your phone, the bombe, the supercomputers at national laboratories. Each one has definite states, deterministic transitions, and symbols manipulated according to rules. Faster, bigger, more parallel, but the same model. This is what computation has been since Turing wrote down the formal definition of it in 1936, three years before he walked into Bletchley Park.

This kind of computer is what we now call classical. Not because it is old, but because it follows the rules of classical physics, the physics of the everyday world. The states are definite. The operations are deterministic. The world the machine lives in is the world you live in.

What comes next

Turing’s bombe broke a code that the Germans had every reason to believe was unbreakable. The breaking did not come from a faster machine grinding through more possibilities. It came from finding a tiny structural rule, a single quirk in how Enigma was wired, and compiling that rule into physics. Once the rule was in copper, the impossible became routine. Most days for the rest of the war.

Today, the cryptography that protects almost every secure connection on the internet has its own hidden structural weakness. It is not a flaw in the engineering. It is a property of the mathematics itself. And there is a machine being built right now, by companies you have heard of and some you have not, that can compile that weakness into physics the way Turing compiled Enigma’s weakness into copper.

That machine is a quantum computer. It is not a faster version of your laptop. It is a different kind of machine, operating on different physics, doing a different kind of thing. The next post is about what that means. We are going to take the principle the bombe established, that you defeat an astronomical number not by counting through it but by exploiting structure, and we are going to see how a quantum computer does the same trick on a substrate so different from copper wires that almost everything your intuition tells you about computers will have to be set aside.

The Germans of 1940 could not have imagined the bombe. We are about to look at the machine that the cryptographers of today cannot yet build, but are racing to defend against anyway.