Sign up ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question

migrated from Aug 17 '11 at 18:17

This question came from our site for professional programmers interested in conceptual questions about software development.

Researchers have also figured out how to transport a photon from one location to another, but this doesn't mean that we are near ready to start having a discussion about the future of air travel. Quantam computers have an incredibly long way to go before they can be even remotely usable for any real world situation. – maple_shaft Aug 17 '11 at 14:29
Some related posts from Sec.SE:… and… – Iszi Aug 17 '11 at 20:02
It also might be interesting to note, in the context of the question, that the largest prime number ever factorized using Shor's algorithm is -- wait for it -- 21. Not 2^21. 21. Or, 3x7. – Justin L. Apr 16 '13 at 5:51
I want to point as worthwhile this opinion and report on the recent events surrounding the D-Wave computer. Especially that part: "Matthias Troyer’s group spent a few months carefully studying the D-Wave problem—after which, they were able to write optimized simulated annealing code that solves the D-Wave problem on a normal, off-the-shelf classical computer, about 15 times faster than the D-Wave machine itself solves the D-Wave problem! " – fgrieu May 17 '13 at 10:59
@MichaelJonathanSimpson When you're worried about quantum computers, larger RSA keys won't offer much peace of mind. The number of required ideal qbits is linear in the key size. With error correction that increase might be steeper, but still not that big. Once a QC can factor a 2048 bit key it will probably only be a few years to factoring a 4096 bit key. – CodesInChaos Mar 25 at 9:44

10 Answers 10

up vote 18 down vote accepted

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.

share|improve this answer
I will accept this in two days – IDWMaster Aug 17 '11 at 16:50
Perhaps they can't answer because the NSA is a client and has told them to deny any claim that quantum computers can be used to crack encryption? (Pure speculation on my part) – Christopher Mahan Aug 17 '11 at 17:02
@IDWMaster - Clifford Cocks described the algorithm in five years prior to the Rivest, Shamir, and Adleman paper and nobody heard about it for 25 years. Granted Cocks' was affiliated with GCHQ as opposed to NSA, but people do know how to keep quiet about stuff. – Rob Z Aug 17 '11 at 17:47
@Rob Z - European governments seem better at it than the USA. Look at WikiLeaks for an example, and that's not even the beginning. The National Institute of Health also lost sensitive data… on a laptop, because it was not encrypted. Our government has lost its ability to keep secrets in the digital era. – IDWMaster Aug 18 '11 at 14:17
"Their claimed speedup over classical algorithms appears to be based on a misunderstanding of a paper my colleagues van Dam, Mosca and I wrote on "The power of adiabatic quantum computing." That speed up unfortunately does not hold in the setting at hand, and therefore D-Wave's "quantum computer" even if it turns out to be a true quantum computer, and even if it can be scaled to thousands of qubits, would likely not be more powerful than a cell phone." -- Umesh Vazirani, UC Berkeley – Fixee Oct 15 '11 at 0:44

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.

share|improve this answer
You might or might be surprised at how fast the state-of-the-art moves, they recently published a paper in Nature in regards to their technique - Likewise, Nature also had a news article about them while back addressing the same issue - – Rob Z Aug 17 '11 at 17:44
@Rob, keep reading. They've demonstrated only 8 qubits, and not for general-purpose computing. They are a long way from being able to compete with classical computing. There remains a good bit of [skepticism]() from experts in quantum computing, who use words like "bogus statements", "smoke and mirrors", "hype" to describe Dwave's past behavior. – D.W. Aug 19 '11 at 4:43
(cont.) Scott Aaronson said their latest system "doesn't by itself do anything useful" and isn't claiming a quantum speedup, but is "an important step". – D.W. Aug 19 '11 at 4:45

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.

share|improve this answer
Unless something changed recently, they only have a 128-qubit model on the market. – rjzii Aug 17 '11 at 23:17
@Rob:oops, quite right. Corrected, and thank you. – Jerry Coffin Aug 17 '11 at 23:20

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.

share|improve this answer
Experts in quantum computing are very skeptical about Dwave's claims to have 128-qubits. Their latest Nature paper only claims 8 qubits (and not even for general-purpose computation). In short: many of Dwave's claims are phony baloney. – D.W. Aug 19 '11 at 4:52

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)

share|improve this answer

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.

share|improve this answer
It is worth noting that all seven of your debunking links come from one man's blog. I'm not disagreeing with you that RSA seems to be safe for now (and the foreseeable future) because I think it is; but seven links from the same source isn't as credible as say... seven links from 4 or 5 different sources. – corsiKa Aug 21 '11 at 22:09
@glowcoder, keep reading and you'll see that considerable skepticism is also expressed by other quantum computing experts, including Umesh Vazirani, Seth Lloyd, and David Bacon -- all of whom are leaders in the field. (And you'll see many others who are skeptical, if you read the comment threads and press articles and know who the commenters are.) Scott Aaronson has been the most visible critic because, well, Scott is about the most effective person in the field at communicating to the public about everything and anything related to quantum computing (not just D-Wave). – D.W. Aug 22 '11 at 3:54
@DW And I'm not denying that at all. I'm just saying... imagine you published a paper, and you had 10 refrences (like this post does) and 8 of them were from the same source (like this post does) you'd probably not publish it in your journal. While I'll be the first to admit that posts on a QA site are held to a different standard as professionally submitted articles, I do see how one might question having so much from a single source. I did read some of the articles (before I made my comment) and saw that he was simply passing along the message of others ... continued ... – corsiKa Aug 22 '11 at 14:55
..., and that in some cases, those 'others' are authors of published works that were bastardized by D-Wave. After reading them, I certainly agree with you about the validity of the content. But I still think it would greatly add to the constitution of the article if there were a wider variety of sources. :-) – corsiKa Aug 22 '11 at 14:56
Above comments of D.W. were because I asked if "unlimited number of qubits" is really a requirement for a quantum computer. I however used infinite instead of unlimited, which is of course quite something different. @D.W. Yeah, I understood enough to see why D-Wave's solutions are different from what we expect when we talk about quantum computing, I just fixed one word in your excellent answer but I had some doubts about changing "unlimited" to something else - rightfully so it seems. – Maarten Bodewes Jan 24 at 20:46

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 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.

Ramsey computing

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: Experimental Determination Of Ramsey Numbers With Quantum Annealing

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

I would like to give an update to this answer. It is now 2015 and mathematicians have managed to crack RSA using quantum computers.

The computers are brute force cracking the RSA keys by taking 2 prime numbers and putting them together to see if the resulting key can decrypt the encrypted data.

There is a chance of false positives as the key could decrypt the data into something meaningful due to the vast number of possibilities, however the situation is no different to the bombe used in Bletchley Park during WWII.


share|improve this answer

protected by e-sushi Oct 13 at 23:56

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.