Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for information security professionals. It's 100% free, no registration required.

Forgive me if this should be in the crypto sub, but sometimes the answers there are very mathematical and I would rather have an answer which is a bit lighter on the math but still strong on the tech if at all possible.

However, I was watching the Cryptographer's panel from RSA 2013 and at about 33 minutes in they mentioned that ECC is more vulnerable than RSA in a post-quantum world.

share|improve this question
    
I'd guess because the numbers used in ECC are smaller (256-521 bit) vs. (1024-4096 bit), they require a smaller quantum computer to break. –  CodesInChaos Mar 22 '13 at 17:13

2 Answers 2

up vote 9 down vote accepted

The current challenge in building a quantum computer is to aggregate enough "qubits", entangled together at a quantum level for long enough. To break a 1024-bit RSA modulus, you need a quantum computer with 1024 qubits. To break a 160-bit elliptic curve, which has a "similar strength" (with regards to classical computers), you need something like 320 qubits. It is not that elliptic curves are intrinsically weaker; on the contrary, they still seem somewhat stronger than RSA for the same "size". Rather, the strength ratio for a given size is not the same when considering classical computers versus quantum computers.

share|improve this answer
    
Are you saying it's just the number of qubits that makes the difference? If we succeed at building a quantum computer with 320 qubits, it seems unlikely that we would not be able to build a 1024 qubit quantum computer (at least a very short time later). the decoherence problems that currently would prevent us from building a 320 qubit quantum computer, if solved, would also enable us to build a 1024 qubit quantum computer (as well as much larger ones). –  Eliah Kagan Mar 23 '13 at 12:18
2  
Indeed, I don't think that the difference in robustness of ECC vs RSA against QC is really worth worrying. If a QC big enough to break ECC can be built at all, we can assume that RSA will not resist much further. –  Thomas Pornin Mar 23 '13 at 12:36
    
While it's true that a 320 qubit computer would only lag a 1024 would only lag 320 qubit computer by a few years, that IS what the question asked. Note that 320 qubits quantum computers are (arguably) already being produced. –  Indolering Sep 5 '13 at 17:40
    
No 320 bit general purpose computer have been produced. If you are speaking of DWave that is a unrelated field called Quantum Annealing which is utterly useless for breaking ECC or RSA. No large scale quantum computers capable of implementing Shor's algorithm are known to have been produced. For example the largest number factored with Shor's algorithm is "21" using a 5 qubit computer. –  Gerald Davis Mar 10 '14 at 17:25

The limiting factor for an attacker using a quantum computer is the number of qubits they can keep entangled long enough to perform a calculation. The qubits required to crack RSA keys are estimated to be 2•bits while ECC is roughly 6•bits, but RSA keys are generally much longer so they end up taking more qubits; roughly 3x on the low end (2048 vs 224) and 10x on the high end (4096 vs 384) see note.

Here's a heavily simplified table comparing the rough number of qubits required to crack common key lengths:

|           RSA       |           ECC       |
| Key Length | qubits | Key Length | qubits |
|------------|--------|------------|--------|
| 1024       | 2048   | 163        | 1000   |
| 2048       | 4096   | 224        | 1300   |
| 3072       | 6144   | 256        | 1500   |
| 4096       | 8192   | 383        | 2300   |
| 15360      | 30720  | 512        | 3000   |

Over the past 20 years, we haven't figured out how to build a fully-fledged quantum computer with more than a handful of qubits. So to compare how much longer it will take a quantum computer to crack an RSA key compared to an "equivalent" ECC key, we basically have to assume a manufacturer will figure out decoherence in a way that can be scaled up. Then it becomes a question of how quickly that scaling will occur.

Assuming linear rates of growth (with 2048 RSA vs 224 ECC low at the end and 4096 RS vs 384 ECC at the high end) RSA gets a ~5-10 year bonus at 500 qubits/year, ~3-5 years at 1K qubits/year, and ~1.5-3 years at 2K qubits/year.

If we assume exponential rates of growth, once we can crack a 224-bit ECC key (the weakest common ECC key) we are one generation from cracking a 4096-bit RSA key (the strongest common RSA key). At the pace of Moore's law (~2 years) RSA gets (at best) a 2 year bonus. Although DWAVE's adiabatic quantum computer isn't useful for these types of problems, they have been doubling their number of qubits roughly every 4 years.

So the difference is actually relatively small: 2-5 years + time to manufacturing breakthrough.

Note 4096 bit RSA and 383 ECC are not directly comparable in terms of symmetric key strength. 4096 bit RSA key is roughly equivalent to a 142 bit symmetric key whereas a 383 bit ECC key is equivalent to a 192 symmetric key. I compare them directly above because they are the largest commonly supported key sizes.

share|improve this answer

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.