Mike Howells's Blog

Tag: RSA

  • The Question Behind the Question

    The Question Behind the Question

    It started with a clock.

    Not a special clock. The one on your wall. Twelve numbers, and a rule so familiar you have never thought of it as a rule: when the hour hand passes 12, it wraps back to 1. Nine o’clock plus five hours is not fourteen o’clock. It is two o’clock. The clock does not care how many total hours have passed. It only cares about the remainder.

    Mathematicians call this modular arithmetic, which means arithmetic that wraps around a fixed number the way a clock wraps around 12. It is the kind of thing that looks like a curiosity, a party trick for number theorists. It is also the crack in the foundation of RSA. Because in 1994, a mathematician named Peter Shor noticed that the problem protecting most of the world’s encrypted traffic, the problem I wrote about last week, is secretly a question about clocks. And questions about clocks have a property that questions about factoring do not.

    They have a rhythm. And rhythms can be heard.

    Where we left off

    I am the person who needed to understand what the cryptographer’s work means for the world I live in, so let me restate the situation in plain terms. In the last post, I walked through why RSA and elliptic curve cryptography are safe from classical computers. The security of RSA rests on a single fact: multiplying two large prime numbers together is easy, but starting from the product and recovering the two primes is brutally hard. Every classical factoring method we know, even the clever ones, chokes when the numbers get big enough. That is why your bank can publish its public key on the open internet and sleep fine.

    And in the post before that, I made the case that a quantum computer is not a faster version of your laptop. It does not try answers more quickly. It plays a different game entirely, one where wrong answers can be made to cancel each other out and right answers can be made to reinforce.

    Here is the problem those two posts leave us with. Cancellation is a wonderful trick, but it only works if the problem has some structure for the cancellation to grab onto. You cannot point a quantum computer at a pile of random possibilities and ask the wrong ones to politely eliminate themselves. There has to be a pattern.

    Factoring, on its face, has no pattern. A 2048-bit RSA number is just a wall. There is no rhythm in a wall.

    Shor’s insight, the reason his name is on the algorithm, was not a quantum insight at all. It was a classical, mathematical insight. He found the pattern. He showed that hiding inside every factoring problem is a completely different problem, and that different problem repeats like a heartbeat.

    The trick: stop asking about factors

    Take the number you want to factor and call it N. Now pick some smaller number, more or less at random. Call it a. Then start computing the powers of a, but on a clock with N positions instead of 12. In other words, compute a, then a squared, then a cubed, and so on, but every time you pass N, wrap around and keep only the remainder.

    Let me make that concrete with a number small enough to do by hand. Say N is 15 and we pick a = 2. Here are the powers of 2 on a 15-hour clock:

    • 2 to the 1st power is 2
    • 2 squared is 4
    • 2 cubed is 8
    • 2 to the 4th is 16, which wraps around to 1
    • 2 to the 5th is 32, which wraps around to 2
    • 2 to the 6th wraps around to 4
    • 2 to the 7th wraps around to 8
    • 2 to the 8th wraps around to 1

    Look at the outputs: 2, 4, 8, 1, 2, 4, 8, 1. The sequence repeats. It cycles through exactly four values and then starts over, forever.

    That cycle length has a name. It is called the period, meaning the number of steps a repeating sequence takes before it starts over. Here the period is 4. And this is not a quirk of the numbers I picked. It is guaranteed. For any N and almost any a, the powers of a on an N-hour clock will eventually loop back to 1 and repeat. The sequence always has a rhythm. The only question is how long the rhythm is.

    Finding that number is called period-finding, and it is the question behind the question. Because here is the part that still strikes me as slightly unfair to classical computers.

    If you know the period, the factors fall out

    Watch what happens with our example. The period was 4. Take a raised to half the period. That is 2 squared, which is 4. Now compute two numbers: one less than that, and one more than that. You get 3 and 5.

    Those are the factors of 15.

    That is not a coincidence, and the reason is one step of algebra I will describe in words rather than symbols. Saying the sequence returns to 1 after r steps is the same as saying that a to the r, minus 1, is divisible by N. And a classic identity from school algebra says that “something squared minus one” splits into “something minus one” times “something plus one.” So N divides evenly into the product of those two smaller pieces. Since N cannot usually fit entirely inside either piece alone, its prime factors have to split up, some landing in one piece and some in the other. Run a greatest-common-divisor calculation between N and each piece, which is an operation so cheap that computers have done it instantly since the 1970s, and the factors surface.

    There are caveats, and I want to be honest about them because the details matter. The period needs to be even for the “half the period” step to make sense, and occasionally the algebra collapses in a way that tells you nothing. When that happens, you throw away your choice of a, pick a new one, and try again. The math says a random a works often enough that a handful of tries is essentially always sufficient. This is not a lottery. It is a procedure with a retry button.

    So here is the new shape of the world after Shor’s classical insight, before any quantum hardware enters the picture. Nobody needs to factor N directly. They need to find the period of one repeating sequence. Factoring has been converted, exactly and provably, into period-finding.

    Your classical instinct is now asking the obvious question: so what? And your classical instinct is right to ask.

    Why this does not help a classical computer at all

    Because for a real RSA number, the sequence is obscene. The period of that repeating pattern is not 4. It can be a number comparable in size to N itself, which for RSA-2048 means a number with hundreds of digits. A classical computer finds a period the only way it can: compute the sequence, step by step, and watch for the repeat. Walking a sequence whose period has 600 digits is the same astronomical wall we started with. We have not shrunk the problem. We have only changed its shape.

    But the shape is everything.

    Think back to the bombe. Turing did not defeat Enigma by trying every rotor setting and reading the output, because there was no time in the war, or in several universes’ worth of wars, to do that. He defeated it by finding structure: a known scrap of plaintext, and the machine’s own strange rule that no letter could encrypt to itself. The structure let whole continents of wrong answers be discarded without ever being visited. You do not defeat an astronomical number by counting through it. You defeat it by exploiting structure.

    A wall has no structure to exploit. A rhythm does.

    A period is not a property of any single step in the sequence. You cannot look at one value, or a thousand values, and read the period off of them. The period is a global property, a fact about the whole sequence at once. And a global property of a vast space is exactly the kind of thing a classical computer is worst at, because a classical computer can only ever stand in one place in that space at a time.

    It is also exactly the kind of thing a quantum computer was born for.

    The opera singer

    Here is the analogy I want you to carry into the next post, because the next post is the payoff of this entire series.

    An opera singer can shatter a wine glass with her voice. She does not do it with volume, and she certainly does not do it by singing every note on the piano one at a time, tapping the glass after each note to check for cracks. She does it by finding the one frequency the glass already wants to vibrate at. When she sings that note, the glass itself responds. Every wave of sound arrives in step with the glass’s own motion, each push reinforcing the last, until the energy piles up and the glass fails. Sing any other note and the pushes arrive out of step, canceling their own effort. The glass does not budge.

    The glass is not being searched. The glass is being asked, all at once, what its natural rhythm is. And the glass cannot help but answer.

    Now recall the machinery from two posts ago. A quantum computer can hold a superposition, which means it can load the entire repeating sequence, every step of it, into its qubits at once. Qubit is short for quantum bit, and the “not knowing versus not being” distinction from that post applies here with full force: the machine has not secretly picked one step of the sequence that we simply have not looked at yet. The whole sequence is genuinely present, the way the water of a pond is present across the entire pond and not hiding at one point on it.

    What Shor needed was the opera singer’s move. A way to make that loaded sequence ring at its own natural frequency. A way to make every wrong guess about the period cancel itself out, pushes arriving out of step, while the one right answer reinforces, wave after wave after wave, until it is the only thing left standing when you measure.

    That move exists. It is called the Quantum Fourier Transform (QFT), and it is the single most important idea in this entire story. It is also, I promise, less frightening than its name. You have been using a Fourier transform your whole life. Your ears do it every time you pick a single voice out of a crowded room.

    That is the next post.

    Where this leaves us

    Let me pin down what we have and have not established, because I do not want the excitement of the trick to outrun the truth of it.

    We have established that factoring, the wall that protects RSA, is mathematically equivalent to period-finding, and that the conversion between them is cheap and classical. No quantum hardware was involved in anything I described today. Shor’s bridge is pure mathematics, and it was in some sense sitting there waiting to be noticed, the way the flaw in Enigma’s design was sitting there waiting for Turing.

    We have not yet established that a quantum computer can actually find the period. That claim carries the whole weight of the threat to RSA, and it deserves its own post rather than a hand wave at the end of this one.

    But notice what has already changed. Before Shor, breaking RSA meant scaling a featureless wall. After Shor, breaking RSA means hearing a rhythm. Those are different problems in kind, not in degree. And if the last seventy years of this story have taught us anything, from the bombe forward, it is that problems with structure do not stay hard forever. Someone eventually builds the machine that listens.

    Fediverse Reactions
  • Locked in Plain Sight

    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.

    Fediverse Reactions