37

I've been reading about quantum computing and turns out that 512-bit quantum processors are already a thing. I also read about Shor's algorithm, which can break RSA and several asymmetric encryption schemas in the next upcoming years.

Quantum computing power has been growing faster than Moore's law and now I wonder how many qubits Shor's algorithm needs to factor 2048-bit key modulus.

Source: https://www.youtube.com/watch?v=6VIAL8gQRTI

Improve this question
4
  • 2
    Something around 4000 ideal qubits should be enough. In practice you'll need a lot for the error correction. Luckily the best real quantum computers (not dwave bullshit) still limited to 5 qubits or so.
    – CodesInChaos
    Commented May 2, 2015 at 14:19
  • Why are dwave's quantum computers bullshit? Can't they used to crack RSA?
    – Nacib Neme
    Commented May 2, 2015 at 14:44
  • 2
    crypto.stackexchange.com/questions/436/…
    – CodesInChaos
    Commented May 2, 2015 at 15:29
  • D-Wave is a quantum computer, but it is not a cryptoanalytic quantum computer. It can solve different problems. Recently (in the last year or two), it was demonstrated to actually have some properties of a quantum computer, but it will never be able to run Shor's algorithm.
    – forest
    Commented Feb 3, 2018 at 6:06

2 Answers 2

Reset to default
21

Actually the question must be clarified, that in which time you want to break RSA, for example scientists say that RSA with 512-bit can be broken in 6 week with quantum computers, but with how many qubits? So time is important, 2 qubit can break 2048-bit but in which time? Because in quantum computers each qubit can be 0 and 1 in each moment, so n qubit can handle 2n state in a moment, if number of qubits are increased the break time decreases(reverse relation). For example 2048 qubit can handle 22048 state in moment. Also only qubits are not enough, qubits are memory for quantum computers. More qubits mean you can factor bigger numbers.

According to mentioned paper:

... If large quantum computers can be built, then RSA ciphers become useless. It is estimated that 2048-bit RSA keys could be broken on a quantum computer comprising 4,000 qubits and 100 million gates. Experts speculate that quantum computers of this size may be available within the next 20-30 years.

Quantum Computing and Cryptography

And according to this one:

Quantum memory units are called qubits and the largest quantum computers capable of running Shor’s algorithm only have about 20 qubits. (A Canadian company called DWAVE has a quantum computer with 512 qubits but it has very high error rates on its qubits and is based on another principle called quantum annealing.) To run Shor’s on 2048 bit RSA would require at least 10,000 qubits. It will probably be a while before such a machine can be built.

Online security, cryptography, and quantum computing

Improve this answer
9
  • 5
    The problem is error correction, which currently require (the latest D-Wave 2X) to use ~12 physical qbits for every logical qbit. For example, in this [2016] paper they manged to factor 200,099 = 499*401 using 897 physical qbits in 3.5 seconds. (We estimate that an RSA-1024 factor can be up to ~309 decimal digits long.)
    – not2qubit
    Commented Feb 3, 2017 at 16:10
  • 5
    You cannot run Shor's algorithm on a D-Wave (crypto.stackexchange.com/questions/40893/…). You can do factorisation with quantum annealing (physics.stackexchange.com/questions/11063/…) but the complexity is not the same.
    – Francis Davey
    Commented Jul 18, 2017 at 18:21
  • 2
    It's important to notice that the current best result (factor 200099) means that best quantum computers can execute Shor's algorithm for up to 18 bit number. To put this into perspecitive, to factor that number with classical computer, the most simple algorithm would be to just try every odd number between 3 and square root of 200099 or 447. For this example, it requires doing maximum of 447/2 divisions which can be executed in around 1341 CPU clocks (modern CPUs have effective throughput of about 6 clock cycles per division). That requires about 260 ns or 0.00000026 seconds in total.
    – Mikko Rantalainen
    Commented Apr 13, 2022 at 11:13
  • 3
    @Mikko Rantalainen Taking into account, that measurement errors grow exponentially with the number for Q-Bits, this implies that ´Shor's algorithm won't be a security threat for long time´.
    – Sam Ginrich
    Commented Apr 14, 2022 at 14:19
  • 2
    If measurement error indeed grows exponentially with the number of physical qubits, I'd say that Shor's algorithm will never work for 4096 bit RSA keys. However, this paper claims to have more efficient error suppression: arxiv.org/abs/2102.06056
    – Mikko Rantalainen
    Commented Apr 14, 2022 at 14:43
10

According to publication from August 24, 2021, Quantum Attack Resource Estimate: Using Shor’s Algorithm to Break RSA vs DH/DSA VS ECC:

Equivalent (classical)
bit-security		 Minimum qubits needed
to attack RSA, DSA etc		 Minimum qubits needed to attack
ECDSA and similar EC schemes
112 4098 (RSA 2048) 2042 (ECC 224)
128 6146 (RSA 3072) 2330 (ECC 256)
192 15362 (RSA 7680) 3484 (ECC 384)

A newer publication from 23 Dec 2022 lists lower theoretical numbers although without certainty that there will be actual acceleration (arxiv.org/abs/2212.12372, credit to kutschkem):

  • RSA 2048: 372 qubits
  • RSA 1024: 205 qubits
  • RSA 512: 114 qubits
Improve this answer
2
  • 6
    This answer could be improved by indicating if these are physical or logical qubits. These are logical qubits, you may need hundreds or possibly thousands of qubit per logical qubit to make this work (the error correction circuits have improved as well). Of course, current quantum computers are measured in physical qubits. The article is well worth the read, although I would have preferred it in peer review paper form of course.
    – Maarten Bodewes
    Commented Apr 15, 2022 at 7:16
  • 3
    Can you update your answer with this publication from late 2022 which seems to drastically lower the estimates? arxiv.org/abs/2212.12372
    – kutschkem
    Commented Mar 8, 2023 at 14:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .