54
$\begingroup$

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

$\endgroup$
8
  • 7
    $\begingroup$ 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. $\endgroup$
    – maple_shaft
    Aug 17, 2011 at 14:29
  • 1
    $\begingroup$ Some related posts from Sec.SE: security.stackexchange.com/questions/4286/… and security.stackexchange.com/questions/6345/… $\endgroup$
    – Iszi
    Aug 17, 2011 at 20:02
  • 9
    $\begingroup$ 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. $\endgroup$
    – Justin L.
    Apr 16, 2013 at 5:51
  • 4
    $\begingroup$ 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! " $\endgroup$ May 17, 2013 at 10:59
  • 4
    $\begingroup$ @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. $\endgroup$ Mar 25, 2015 at 9:44

10 Answers 10

45
$\begingroup$

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.

$\endgroup$
7
  • 20
    $\begingroup$ 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. $\endgroup$
    – corsiKa
    Aug 21, 2011 at 22:09
  • 4
    $\begingroup$ @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). $\endgroup$
    – D.W.
    Aug 22, 2011 at 3:54
  • 2
    $\begingroup$ @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 ... $\endgroup$
    – corsiKa
    Aug 22, 2011 at 14:55
  • 4
    $\begingroup$ ..., 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. :-) $\endgroup$
    – corsiKa
    Aug 22, 2011 at 14:56
  • $\begingroup$ 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. $\endgroup$ Jan 24, 2015 at 20:46
24
$\begingroup$

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.

$\endgroup$
7
  • 5
    $\begingroup$ 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) $\endgroup$
    – Christopher Mahan
    Aug 17, 2011 at 17:02
  • 1
    $\begingroup$ @Christopher Mahan - The NSA can't keep secrets as well as you'd expect. If they had really cracked RSA, the public would have (probably) found out by now, and we'd already be in World War 3. $\endgroup$
    – IDWMaster
    Aug 17, 2011 at 17:37
  • 5
    $\begingroup$ @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. $\endgroup$
    – Rob Z
    Aug 17, 2011 at 17:47
  • 1
    $\begingroup$ @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. $\endgroup$
    – bbosak
    Aug 18, 2011 at 14:17
  • 7
    $\begingroup$ "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 $\endgroup$
    – Fixee
    Oct 15, 2011 at 0:44
8
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – Rob Z
    Aug 17, 2011 at 17:44
  • $\begingroup$ @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. $\endgroup$
    – D.W.
    Aug 19, 2011 at 4:43
  • $\begingroup$ (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". $\endgroup$
    – D.W.
    Aug 19, 2011 at 4:45
8
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Aug 19, 2011 at 4:52
  • $\begingroup$ There's a huge difference between physical qubits and logical qubits. Quantum computers are inherently unstable things and physical qubits will always have random errors. The question is how many physical qubits a given quantum computer needs to be able to implement a single logical qubit (that is, something that can produce non-random computation results). For existing systems this is typically 15 or more. When somebody says they have 128 qubit quantum computer, that's typically physical qubits and that would be maybe 8-10 logical qubits at best. For n bit RSA, you need 2×n+3 logical qubits. $\endgroup$ Apr 13, 2022 at 11:52
  • $\begingroup$ @MikkoRantalainen but wheren t there a paper some years ago that described an alternative algorithm for rsa factorization using unstable qubits directly? $\endgroup$ Jun 21, 2023 at 8:33
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Unless something changed recently, they only have a 128-qubit model on the market. $\endgroup$
    – user560
    Aug 17, 2011 at 23:17
4
$\begingroup$

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)

$\endgroup$
3
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ but wheren t there a paper some years ago that described an alternative algorithm for rsa factorization using unstable qubits directly? $\endgroup$ Jun 21, 2023 at 8:38
  • $\begingroup$ As of 2023, there have been many such such papers, often quickly debunked. The one which are not flatly wrong have enough dust swept under the carpet to make the claim totally useless $\endgroup$ Jun 21, 2023 at 17:08
  • $\begingroup$ Bien sûr je ne parlais pas de quelques chose de faisable actuellement mais sur du matériel dans quelques décennies. $\endgroup$ Jun 22, 2023 at 7:51
  • $\begingroup$ If you think about «in a few decades», the precise pace of technological progress is difficult to predict, and such proposals only make sense when the scaling is carefully shown to be robust against such impredictibility. Most do not fit the bill. A possible exception is Bernstein, Biasse, Mosca (2017), which is less efficient than Shor, but uses less qubits. $\endgroup$ Jul 3, 2023 at 16:05
  • 1
    $\begingroup$ Since discrete logarihtms seem to be coputed classically by field sieves, I guess a similar approach applies. One would need to replace all research phase of the classical algorithms by Grover search, and re-optimize to get the relevant parameters $\endgroup$ Jul 4, 2023 at 7:25
1
$\begingroup$

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.

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: arxiv.org/abs/1201.1842: Experimental Determination Of Ramsey Numbers With Quantum Annealing

$\endgroup$
-3
$\begingroup$

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.

$\endgroup$
0

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