16

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.

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. Can somebody explain why ECC is more vulnerable to RSA in a post-quantum world?

user
  • 7,670
  • 2
  • 30
  • 54
JZeolla
  • 2,936
  • 1
  • 18
  • 25
  • 2
    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 Answers2

24

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 twice that (2048) qubits. To break a 160-bit elliptic curve, which has a "similar strength" (with regards to classical computers), you need six times that (or 960 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.

forest
  • 64,616
  • 20
  • 206
  • 257
Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
  • 4
    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](http://en.wikipedia.org/wiki/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
  • 8
    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 05 '13 at 17:40
  • 10
    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
  • 2
    1024-bit RSA requires 2051 qubits (1024 × 2 + 3) and 160-bit ECC requires far more than 320 (it requires 160 × 6 = 960). RSA can be broken with _2n + 3_ qubits, whereas ECC can be broken with _6n_. – forest Nov 10 '18 at 09:40
  • Just my two cents here 2n + 3 < 6n for any given non negative n. Thus if you compare apples to apples, it would seem that ECC is much more resistant to Quantum attacks than RSA since for ECC you would need a 6n qit computer to crack, however the challenge is finding an appropriate curve for a 1024 key length. The P-521 curve for example provides a key length of 521 bits which would require a Q-computer of size 3126 qbits. Technically this would be weaker than RSA with 4028 bits but stronger than RSA with 256 bits. – Steve Owens Jun 20 '22 at 13:17
19

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 away from cracking a 4096-bit RSA key (the strongest common RSA key). At the pace of Moore's law (~2 years) RSA gets ~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.

Indolering
  • 852
  • 6
  • 21
  • Seriously, how many people, if there are any, use a 15360-bit RSA key in real life? The largest key size I've seen is 8192-bit and it's not very common. Usually just 2048/3072. – zypA13510 Aug 12 '19 at 16:07
  • @zypA13510 Indeed, GnuPG maxes out at 4096 bit keys! It's just included because the standard ECC key sizes max out at 512 and there was an empty table cell on the RSA side :) – Indolering Aug 13 '19 at 11:57