Depending on who you ask, the big news this week is that quantum computing researchers out of China have broken RSA. (Here’s the PDF of their paper.) And that’s true… sort of. There are multiple caveats, like the fact that this proof of concept is only factoring a 22-bit key. The minimum RSA size in use these days is 1024 bits. The other important note is that this wasn’t done on a general purpose quantum computer, but on a D-Wave quantum annealing machine.
First off, what is the difference between a general purpose and annealing quantum computer? Practically speaking, a quantum annealer can’t run Shor’s algorithm, the quantum algorithm that can factor large numbers into primes in a much shorter time than classical computers. While it’s pretty certain that this algorithm works from a mathematical perspective, it’s not at all clear that it will ever be possible to build effective quantum computers that can actually run it for the large numbers that are used in cryptography.
We’re going to vastly oversimplify the problem, and say that the challenge with general purpose quantum computing is that each q-bit is error prone, and the more q-bits a system has, the more errors it has. This error rate has proved to be a hard problem. The D-wave quantum annealing machine side-steps the issue by building a different sort of q-bits, that interact differently than in a general purpose quantum computer. The errors become much less of a problem, but you get a much less powerful primitive. And this is why annealing machines can’t run Shor’s algorithm.
The news this week is that researchers actually demonstrated a different technique on a D-wave machine that did actually factor an RSA key. From a research and engineering perspective, it is excellent work. But it doesn’t necessarily demonstrate the exponential speedup that would be required to break real-world RSA keys. To put it into perspective, you can literally crack a 22 bit RSA key by hand.
Continue reading “This Week In Security: Quantum RSA Break, Out Of Scope, And Spoofing Packets” →