Now that quantum computers have been out for a while, has RSA been cracked?

Question

D-wave systems has released a commercially viable quantum computer. This means in theory, that all asymmetric encryption algorithms — such as RSA — are now useless due to the speed at which quantum computers can factor.

Has RSA been cracked yet? If not, why hasn't it?

The reason for our company's concern is an upcoming product that relies heavily on cryptography, and a significantly large number of hackers may attempt to break it. If the code was found to be insecure, it would be a huge problem for our company, our users, and anyone on the Internet if RSA was found to be insecure.

Update: article on D-Wave recent announcement here

Answer 1

RSA has not been cracked. No one has demonstrated practically viable computing that's anywhere in the realm of breaking RSA. There is no reason to change any of your practices.

The first thing to understand is that D-Wave has a long history of repeatedly making bogus claims to the popular press. Experts in quantum computing have been criticizing and debunking D-Wave's claims for years. (Try clicking each of the last seven words, for examples.) So, this is not a company with a lot of credibility.

The latest news is that D-Wave has published a paper in Nature that describes very limited progress towards quantum computing. It is not a full-fledged quantum computer. It can't do general-purpose computation; it can only solve one algorithm. In particular, it can't be used to factor numbers or break RSA. It can't handle realistic problem sizes; it only has 8 qubits, so it can only solve toy-sized problems (problems that you could have solved with pencil-and-paper anyway). There is no evidence that it is faster than classical algorithms. It's not faster than existing classical computers. It does represent a step forward, but it's a limited step.

Researchers have been studying quantum computing intensely over the past decade or so. There has been some progress, but it has been slow, and building a working quantum computer will require us to surmount some fundamental challenges (e.g., decoherence) that today no one knows how to deal with. D-Wave gets a lot of press (mostly because they make irresponsible statements to the press to hype their work beyond its true importance), but others have made more significant contributions.

You use the phrase "commercially viable quantum computer". That's not a useful phrase. Please understand that D-Wave has not demonstrated a viable quantum computer. D-Wave may have sold something to one or two customers, but that doesn't mean they have licked the quantum computing problem or that their claims therefore necessarily have any validity. Snake oil salesman managed to sell their stuff to plenty of customers, too, but their claims were invariably bogus.

If someone did build a working quantum computing that scaled to an unlimited number of qubits, and solved the decoherence problem, that'd be different: in that case, we'd have to move away from RSA, pronto. But we're a long ways away from that. Right now, it's an open question whether we'll see such a quantum computer in our lifetimes (or even if it will ever be possible to build one) -- quantum computing experts like to debate questions like those over drinks. I suspect, if general-purpose quantum computing is possible, we'll have plenty of warning before quantum computers that can threaten RSA become readily available.

So, in short, no, you don't need to change your strategy or drop RSA. I wouldn't. Continuing to use RSA is perfectly reasonable and in line with industry practices.

Answer 2

After contacting D-Wave and asking them the implications of their quantum computer against RSA, they responded that they had not cracked RSA for the following reasons…

Short answers:

Q. Is RSA effectively cracked by your quantum computer

A. No.

Q. Should our customers be concerned that companies with quantum computers are intercepting our encrypted traffic?

A. No.

Longer answers:

The utility of quantum computers in code-breaking and other number theoretical problems is WAY over hyped.

The types of quantum computers that work in practice have architectures that are not well suited to number theoretical type problems. Where they excel is in machine learning, which is where our partners focus their applications development work.

I suspect that conventional encryption techniques are secure against all but extremely sophisticated attacks.

Answer 3

As @Jono pointed out in his answer the D-Wave device is not a general purpose computer.

There also remains some controversy as to whether it is a bona-fide quantum computer. From the January 2010 IEEE Spectrum, "D-Wave Does Not Quantum Compute":

If this were the real thing, we would know about it," says Christopher Monroe, a quantum-computing researcher at the University of Maryland, in College Park. He says D-Wave hasn't demonstrated "signatures" believed to be essential to quantum computers, such as entanglement, a coupling between qubits.

Answer 4

D-Wave does quantum annealing. It's not general-purpose quantum computing; in fact, the CEO claims that the gate-model for quantum computers is the worst thing that ever happened to the field.

I have worked on quantum research as recently as 2012 and the gate-model is still the main focus for funded research.

Shor's algorithm for factorization (which runs in poly time on a quantum computer) does not run on a D-Wave computer. It requires a circuit to compute the modular exponent of large numbers and to compute a Quantum Fourier Transform of its output.

It's actually a simple algorithm... it's the decoherence and error-correction that's hard.

Answer 5

The largest quantum computer that can definitely run Shor's algorithm is now up to 14 qubits. This was achieved sometime last year. This computer was probably not used to actually run Shor's algorithm, though. Shor's algorithm was actually demonstrated to work in 2001, with 7 qubits.

We are still a long way from creating quantum computers that can work with the hundreds or thousands of qubits that are needed to break RSA or other asymmetric cryptographic algorithms.

There's some discussion on what the D-wave quantum computers can do (they claim 128 qubits), but it seems somewhat unlikely they could be used to run Shor's algorithm.

Answer 6

To try to put this into perspective, the D-Wave system has (or at least claims) a 128-qubit processor. To factor a 1024-bit RSA key, you need roughly 2000 qubits (and, of course, many people are already using keys much larger than 1024 bits).

If you were using elliptical curve cryptography instead, you'd be a bit closer to vulnerable. You can do a discrete logarithm on a 160-bit ECC key with about ~1000 qubits.

It's open to argument whether the D-Wave system is really suited to implementing Schor's algorithm, but even assuming it is, the current system isn't really suited to breaking current public-key cryptography systems -- in particular, anything with a key small enough for the current D-Wave system to attack at all is also trivial to break with a more conventional computer.

Also note that scaling up a quantum computer is quite a different story from scaling up a conventional computer. Although it wouldn't be very fast, I could design a functioning 256-bit or 1024-bit conventional computer and implement it in something like a large FPGA fairly easily. Building a (functioning) quantum computer with lots more qubits is a whole different story -- producing a quantum computer with twice as many qubits isn't just a matter of repeating one qubit twice as many times or anything like that.

Answer 7

Just another point. Just because the complexity of quantum factoring is quadratic with respect to n for a composite N of length n bits does not mean it is cheap. It will still take a very long time on a quantum computer with a suitably large number of qbits (>= 2n). This difference is if you could produce a fast enough conventional system to crack 1024bit RSA (e.g. the TWIRL design) you could make it infeasible to perform by simply doubling n. However, if you could build a big and fast enough quantum computer doubling n would simply double the qbits required and increase the time factor by a moderate amount so may not be sufficient to re-secure the system.

Ok, I should say it would take a long time to build the quantum gates: at least 1,000,000,000,000 of them for factoring 1024bit RSA (and the gate layout must be resdesigned for each integer you want to factor). Also there is a problem with error bit propergation (and there is only so much quantum ECC can do about it) and also decoherance. As the number of gates increases the bit error rate increases until ECC can not correct it and the total gate propgation time also increases until it eventually equals the decoherance time for the system. There could well be point where a quantum computer could just not get any more complex (given current ideas for encoding qbits)

Answer 8

TL;DR: As of 2015 quantum computing is not an immediate threat to RSA. But it is a long-term threat (decades away). Whether you should be worried depends whether you are interested in keeping the secrets for so long (2035, if you want a pessimistic guesstimate).

As the other answers already say, D-Wave machines are not generic quantum computers and will never be of any consequence for RSA cryptography (even if you accept D-wave’s claim, they are not built for this).

According to most experts in the field, generic quantum computers are decades away. Furthermore, the first quantum computers performing useful computations undoable classically will be pretty small (50-100 logical qubits) and are not an immediate threat for quantum cryptography. At least an order of magnitude improvement in the number of qubits will be needed to break even small (512 bits) RSA keys. But then, the polynomial scaling will allow to quickly crack bigger and bigger keys. Depending on who you ask, this is expected to happen in 20 to 50 years from now (2035–2065), in other words, just beyond the predictable technological horizon: no one really knows when RSA will be broken by quantum computers, but it could happen in two decades, and the consensus is it will definitely happen in this century. Don’t believe anyone telling they’ll have an RSA-breaking quantum computer within the current decade ; but also don’t believe anyone saying there is no hope to have one 20 years from know (it’s optimistic, but not impossible).

As others have already answered, this means that RSA-based cryptography is secure today, and will stay secure in the next decade. But if you want to use it to guarantee long term security (say, beyond 2035), quantum computers are a threat you need to consider.

Michele Mosca, from Intitute for Quantum Computing discuss this specific threat in this talk (from 42:00 onwards).

Answer 9

Quantum computers are not yet at the stage where they can be deployed to brute-forcing public RSA moduli. There is no evidence of a quantum computer using more than 7 qubits.

The company D-Wave has made several bold claims, but offered little evidence.

Via technologyreview.com: World's Largest Quantum Computation Uses 84 Qubits:

World's Largest Quantum Computation Uses 84 Qubits

The most extensive quantum computation in history took just 270 milliseconds, say quantum physicists.

Quantum computers are in danger of losing their lustre. These machines exploit the strange rules of quantum mechanics to carry out calculations that are vastly more powerful than anything that conventional computers can do.

Or so we’re told. Quantum computers in one form or another have been carrying out calculations for more than a decade. But far from putting conventional computers to shame, these devices have yet to outperform the calculating abilities of a primary school child.

Ten years ago, physicists used a quantum computer to factorise the number 15 using seven quantum bits or qubits. The result received great acclaim. Last year, they beat this record by factorising the number 143 using four qubits. Hardly a meteoric improvement.

But this dismal state of affairs may be finally changing with the announcement today of a calculation involving 84 qubits carried out by Zhengbing Bian at D-Wave Systems, a quantum computer manufacturer based in Vancouver, Canada, and a few mates.

Their task was to calculate various so-called ‘two-colour Ramsey numbers’, exotic mathematical entities that are intimately connected with the emergence of order in disordered systems.

The famous example used to explain Ramsey numbers is the party problem which can be stated like this: how many people do you need to invite to a party to ensure that a subset of them, denoted ‘m’, will know each other and another subset of them, denoted ‘n’, will not know each other and so be forced to mingle. The required number, R(m,n), is a two colour Ramsey number.

These numbers are notoriously difficult to calculate. The mathematician Paul Erdos once said that if an alien species threatened to destroy the human race unless we could tell them the R(5,5) Ramsey number, our best bet would be to put humankind’s best minds to work on the problem, since we should have a chance of getting it.

But if the aliens asked for R(6,6), our best bet would be to launch an immediate all-out strike against the aliens since the calculation would be too difficult to contemplate.

The task is essentially a counting problem. The guests at the party can be thought of as nodes on a graph and their connections (or the absence of them) as edges. Calculating Ramsey numbers is really a question of counting the permutation of connections for a given number of guests.

But even for a small number of guests the permutations can be nhuge. For example, R(5,5) is still unknown, even today, although mathematicians think it lies between 43 and 49.

With the threat of alien extermination ringing in their ears, Bian and co have calculated R(3,3) and R(m,2) where m = 4, 5, 6, 7 and 8.

Their quantum computer uses qubits in the form of superconducting circuits in which 1s and 0s correspond to the currents travelling in opposite directions and the laws of quantum mechanics allow both states to exist simultaneously. So a single circuit can represent both a 0 and 1 at the same time.

What’s useful in this calculation is that whenever a solution occurs, it is the result of increasing the number of guests by one. So in R(3,3), parties with 1, 2, 3, 4, and 5 guests produce a null result. However, the dynamics of the problem change dramatically when their are 6 guests and this is straightforward to spot with the appropriate quantum algorithm.

Bian and co say the calculation for R(8,2) used 84 qubits, of which 28 were used in the computation and the rest for error correction. It took just 270 milliseconds. The result is 8 (as has been known for many years by conventional methods).

That’s an impressive result. Bian and co say “The R(8, 2) computation…to the best of our knowledge is the largest experimental implementation of a scientifically meaningful quantum algorithm.”

It’s also a vindication of kind for D-Wave Systems, the company that built this computer and markets a 128-qubit computer for $10 million.

The company’s approach to computing, known as adiabatic quantum computing, has been heavily criticised. Various physicists have said that the theory behind the machine is flawed and that the company has shown little evidence of the kind of improvement expected over classical computers.

Nevertheless, various companies have partnered with D-Wave Systems to further develop the approach, including Google and Lockheed Martin.

So it’ll be interesting to see whether this result quells the storm or fuels it.

Ref: arxiv.org/abs/1201.1842: Experimental Determination Of Ramsey Numbers With Quantum Annealing

Answer 10

There still is no general-purpose quantum computers available at the time of writing this. As soon as Shor's algorithm and quantum computers become available, it will be possible to crack RSA.