Locked in Plain Sight

The last time you bought something online, your computer did something that should be impossible.

In the moment the little padlock appeared in your browser, your computer and a server it had never spoken to before agreed on a secret. A shared key that only the two of them knew. They did this out loud, over an open wire, in a coffee shop or an airport or your living room, with every byte of the exchange visible to anyone who cared to look. Your internet provider saw it. Anyone on the same wifi saw it. If someone had been quietly recording the whole conversation, they captured every step of it, start to finish.

And at the end of it, the two computers shared a secret that the recorder does not have and cannot work out. Not because the computers whispered. They shouted. The eavesdropper heard every word and still walked away with nothing.

I have spent a good part of my career operating the systems that make that moment work. I am not the person who invented the mathematics behind it. I am the person who needed to understand what that mathematics protects, because I am responsible for machinery that depends on it. This post is about that mathematics. In the first post of this series, I told you the industry I work in is replacing it. Before I can show you why, I have to show you something that sounds like the opposite. I have to show you why it has never been broken, and why, against every classical computer on earth, it never will be.

The padlock and the key

Start with the trick that makes the coffee shop moment possible, because it is one of the genuinely great ideas of the twentieth century.

For most of the history of secret-keeping, encryption had a chicken-and-egg problem. If you and I want to exchange coded messages, we first need to agree on the code. But to agree on the code secretly, we already need a secure channel, which is the thing we were trying to create. For centuries the only answer was to meet in advance, or to trust a courier with the code itself. Enigma had this problem too. The daily settings had to be printed in codebooks and physically distributed to every U-boat and field unit, and captured codebooks were among the most valuable prizes of the war.

Public key cryptography dissolved the problem. The idea is to split the code into two halves that are mathematically linked but do different jobs.

One half is called the public key, and you can think of it as an open padlock. I can hand open copies of my padlock to anyone. I can pile them on a table in the town square. Anyone who wants to send me something snaps my padlock shut on a box, and from that moment even the sender cannot reopen it.

The other half is called the private key, and it is the one physical key that opens that padlock. It never leaves my possession. It is never transmitted, never shared, never in the coffee shop at all.

Lock with the public half, unlock with the private half. Anyone can lock. Only one party can unlock. That asymmetry is the entire trick, and it is why this family of systems is also called asymmetric cryptography. It is what your browser and that unfamiliar server were doing while the padlock icon appeared. The exact recipe varies from protocol to protocol, and in the first post I named the family members you have most likely seen on the ingredients list, RSA, ECC, and Diffie-Hellman. They differ in the details, and the differences will matter later in this series. But every one of them rests on the same kind of mathematical object, and for the rest of this post I am going to hold up the oldest and easiest one to see into. RSA.

Easy one way, impossible the other

Here is RSA’s foundation, and I promise this is the only arithmetic in this post.

Pick two prime numbers. Multiply them. That is the whole move.

Take 61 and 53. Multiply them and you get 3,233, and you got it in a second or two, or instantly if you reached for a calculator. Now run it backward. I hand you 3,233 and tell you it is the product of exactly two primes. Find them. There is no formula. You check. Does 3 divide it, does 7, does 11, does 13. That backward search has a name. Finding the numbers that multiply together to produce 3,233 is called factoring, and 61 and 53 are its factors. Forward is one multiplication. Backward is factoring, and factoring is a search.

An RSA public key is built around a number like 3,233, except unimaginably larger. The key size is the length of that number measured in bits, the same units your hard drive is measured in. The standard today is RSA-2048, which means the public number is 2,048 bits long. Written out in ordinary digits, it is 617 digits long. The two secret primes behind it are around 300 digits each.

The forward direction does not care about the size. Your phone multiplies two 300-digit primes in less time than it takes the screen to refresh. The backward direction is where the universe runs out of patience.

The best public factoring record stands at 829 bits. In February 2020, a research team factored a 250-digit number using roughly 2,700 years of processor-core time, spread across a large cluster of machines running for months. That is the record. Not 2,048 bits. 829.

And here is the part that matters. The difficulty of factoring does not climb gently as the numbers grow. Every bit you add multiplies the work. The 829-bit record is not a step on the road to 2,048 bits. Scale the mathematics behind the 2020 record up to a 2,048-bit key and the workload grows by a factor in the hundreds of billions. The 2,700 core-years becomes hundreds of trillions of core-years. Turn a hundred thousand processor cores loose on it, a respectable supercomputer’s worth, and the job runs for billions of years. The universe has only existed for 13.8 billion.

You may have heard this put more dramatically, that breaking RSA would take “longer than the heat death of the universe.” The heat death of the universe is cosmology’s forecast for the very end, the point almost unimaginably far in the future when the last stars have burned out and no usable energy remains anywhere, on a timescale so vast that the current age of our universe rounds to zero against it. And the dramatic phrase is true, but only of the naive attack. Checking possible divisors one at a time really would outlast the heat death of the universe, comfortably. The clever structural methods that set the 2020 record are what collapse the job from beyond-the-end-of-everything down to merely billions of years. Hold that collapse in your mind. It is what exploiting structure buys you, it is the spine of this series operating in plain daylight, and it is still nowhere near enough. For every practical purpose, billions of years is forever.

This is the design. The security of RSA is the size of the gap between multiplying and factoring. You publish the product to the whole world, padlocks piled in the town square, and you sleep well, because recovering the primes from the product is beyond every computer that exists.

RSA is nearly fifty years old. It was published in 1977, and it has been protecting the internet for roughly thirty of those years, since the mid-1990s, when the first secure web connections made online commerce possible. In all that time, against every classical computer and every classical algorithm ever pointed at it, properly sized RSA has never been broken.

The question underneath the question

If you have been reading this series from the beginning, something should be nagging at you right now, and I want to drag it into the open.

In the first post, we watched the Germans make exactly this argument. Enigma had 159 quintillion possible settings. Counting through them was impossible, therefore Enigma was unbreakable. And the argument was wrong, because counting was never the only option. You do not defeat an astronomical number by counting through it. You defeat it by exploiting structure. Turing did not out-count Enigma. He found a structural flaw, the rule that no letter could encrypt to itself, and compiled it into a machine.

So the honest question about RSA is not “how long would it take to check all the possibilities?” We already know that question can lie to you. The honest question is the one Turing would ask. Does factoring have structure a machine can exploit?

Mathematicians have been probing that question for a very long time, longer than RSA has existed, because factoring fascinated number theorists for centuries before it guarded anything. And the answer, classically, is that factoring has some structure, and it is not enough. The best classical factoring methods are enormously cleverer than trial division. That 2020 record was not set by checking divisors one at a time; it was set by an algorithm that exploits real mathematical structure in the problem, and it is the reason the record is 829 bits instead of far less. But even the cleverest known classical method still faces work that grows explosively as the keys get longer. The structure that has been found chips at the edges of the mountain. It does not tunnel through it.

Nobody has proven that a devastating classical shortcut is impossible. That proof does not exist, and its absence is one of the famous open problems in mathematics. RSA’s security rests on something less formal and, after five decades, quite convincing. The smartest people on earth have been searching for the tunnel, with career-defining glory waiting for whoever finds it, and nobody has.

Hold that phrasing, because I chose it carefully. Classically, no one has found structure in factoring that turns the mountain into a doorway. That sentence has a second half, and it is coming in the next post.

The smaller, faster padlock

Before we get there, I owe you the other name from the ingredients list, because it is quietly running most of your day.

ECC, short for elliptic curve cryptography, is the same padlock idea built on a different mathematical foundation. Instead of hiding a secret in the difficulty of factoring, ECC hides it in a different one-way problem, a cousin of factoring involving mathematical objects called elliptic curves. You do not need the details, and I am not going to pretend to walk you through them. The shape is what matters. Easy in one direction, effectively impossible in reverse, against every classical computer on earth.

ECC is the younger sibling. It was proposed in 1985, eight years after RSA, by two mathematicians working independently, and it spent roughly two decades as a specialist’s tool before the mobile era pulled it into the mainstream. Call it forty years old, with about fifteen of them spent carrying serious internet traffic.

What ECC buys you is efficiency. The one-way problem behind it is, as far as anyone knows, even more stubborn per bit than factoring is. A 256-bit ECC key delivers roughly the same classical security as a 3,072-bit RSA key. Same strength, a fraction of the size. Smaller keys mean faster handshakes, less data on the wire, less battery burned doing the math. That is why ECC took over the mobile internet. When your phone set up the connection you are quite possibly reading this over, odds are the padlock moment ran on elliptic curves.

File one fact away before we move on. ECC’s entire advantage is that its keys are small. Small keys, same security. Later in this series, that advantage is going to come back and matter again, in a way you will not expect.

The lever everyone reaches for

There is one more classical fact you need, and it is the one this whole post has been building toward.

When people who run cryptographic systems get nervous, there has always been one reliable lever to pull. Make the keys bigger. And classically, that lever is magnificent. Because the attacker’s work grows explosively with key size while the defender’s work grows only modestly, every step up in key size costs you a little and costs the attacker a world. Moving from RSA-2048 to RSA-3072 slows your handshakes slightly. It multiplies the factoring effort by a factor large enough that nobody bothers writing it out. This is why the industry has stayed comfortably ahead for thirty years. When machines got faster, keys got longer, and the mountain grew faster than anyone could climb.

The instinct runs deep, and you can watch it operating right now. As quantum computing headlines pile up, plenty of organizations are quietly reasoning as follows. If a new machine threatens RSA-2048, we will move to RSA-4096, or RSA-8192, eat the performance cost, and buy ourselves a decade or two, the way bigger keys have always bought time. It is a perfectly sensible plan, built on the entire history of the field.

It is built on one more assumption, too. It assumes the attacker’s difficulty grows explosively with key size. That has been true of every attacker so far, because every attacker so far has been classical, and classically, no tunnel through the mountain has ever been found.

You already know where this is going, because you read the first two posts.

The machine we met in the last post does not count, and it does not climb. It arranges. And in the next post, I am going to show you the thing Shor discovered in 1994. Factoring, the problem I have just spent an entire post telling you has resisted structural attack for centuries, has a hidden structure after all. Classical machines cannot exploit it. It is invisible to them in a way that will become precise later. But it is exactly the kind of structure the new machine was born to exploit.

And that is why the lever fails. I will show you the details when we have the machinery to see them, but I will state the headline now, and your classical instinct is going to refuse to believe it, which by this point in the series you should recognize as a familiar feeling. Against the new machine, making the keys bigger barely helps. Doubling the key size does not multiply the machine’s difficulty astronomically. It roughly doubles it. RSA-4096 is not a fortress against this machine. It is the same door with a second lock of the same make.

The unbreakable lock of our era is sitting in plain sight, in the town square, in your browser, in the recording that eavesdropper made of your coffee shop purchase. For thirty years, plain sight has been perfectly safe, and everything in this post is the reason why. The next post is about the flaw Turing would have gone looking for. The rhythm hidden inside the numbers, and the trick that turns finding a factor into hearing a note.