Take the 2-minute tour ×
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 programmers.stackexchange.com Aug 17 '11 at 18:17

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

5  
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
1  
Some related posts from Sec.SE: security.stackexchange.com/questions/4286/… and security.stackexchange.com/questions/6345/… –  Iszi Aug 17 '11 at 20:02
7  
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
3  
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
add comment

10 Answers 10

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 import), 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
7  
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
1  
@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
1  
..., 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
add comment
up vote 13 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
3  
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
3  
@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
1  
@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 washingtonpost.com/wp-dyn/content/article/2008/03/23/… 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
2  
"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
show 1 more comment

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 - nature.com/nature/journal/v473/n7346/full/nature10012.html Likewise, Nature also had a news article about them while back addressing the same issue - nature.com/news/2011/110531/full/474018a.html –  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
add comment

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. –  rob Aug 17 '11 at 23:17
1  
@Rob:oops, quite right. Corrected, and thank you. –  Jerry Coffin Aug 17 '11 at 23:20
add comment

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
add comment

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
add comment

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
add comment

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.

source: http://www.technologyreview.com/view/426586/worlds-largest-quantum-computation-uses-84-qubits/

share|improve this answer
add comment

Still there is no general-purpose quantum computers available. When available Shor's algorithm, which will run on quantum computers will crack the RSA
http://en.wikipedia.org/wiki/Shor%27s_algorithm

share|improve this answer
2  
This answer does not seem to add any added value over the existing answers. –  D.W. Dec 23 '13 at 6:30
add comment

us govt has implemented 1024 qb computers, currently lockheed martin, nasa and the dpt or energy employ 512 qb computers.

they use them for factoring things like all of the calculations of space travel, encryption and number crunching.

as far as modern quantum computing goes and encryption DONT go by a private company such as dwave, they just wana sell you one for 30 million , read the sites experts in the gieds use such ad the department of quantum computing at waterloo university.

in terms of the "safest" way to encrypt data is to ensure your keys exprire in a short amount of time and use strong rsa 2048bit or more.

share|improve this answer
5  
[citation needed] –  Thomas May 11 '13 at 3:30
    
That last part is actually good advice, but not because of quantum computers. –  Ilmari Karonen Dec 22 '13 at 14:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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