36

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

Nacib Neme
  • 1,194
  • 2
  • 9
  • 11
  • 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 May 02 '15 at 14:19
  • Why are dwave's quantum computers bullshit? Can't they used to crack RSA? – Nacib Neme May 02 '15 at 14:44
  • 2
    http://crypto.stackexchange.com/questions/436/now-that-quantum-computers-have-been-out-for-a-while-has-rsa-been-cracked – CodesInChaos May 02 '15 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 Feb 03 '18 at 06:06

2 Answers2

19

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

forest
  • 64,616
  • 20
  • 206
  • 257
Ali
  • 2,694
  • 1
  • 14
  • 23
  • 3
    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](https://arxiv.org/abs/1604.05796) [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 Feb 03 '17 at 16:10
  • 4
    You cannot run Shor's algorithm on a D-Wave (https://crypto.stackexchange.com/questions/40893/can-or-can-not-d-waves-quantum-computers-use-shors-and-grovers-algorithm-to-f). You can do factorisation with quantum annealing (https://physics.stackexchange.com/questions/11063/can-quantum-annealing-be-used-for-factorization) but the complexity is not the same. – Francis Davey Jul 18 '17 at 18:21
  • The best implementation of Shor's algorithm on an _n_-bit semiprime requires 2n + 3 logical qubits. – forest Jun 12 '18 at 04:27
  • 1
    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 Apr 13 '22 at 11:13
  • 1
    @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 Apr 14 '22 at 14:19
  • 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: https://arxiv.org/abs/2102.06056 – Mikko Rantalainen Apr 14 '22 at 14:43
4

According to latest publications:

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)

Source: Quantum Attack Resource Estimate: Using Shor’s Algorithm to Break RSA vs DH/DSA VS ECC

akostadinov
  • 555
  • 3
  • 8
  • 1
    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 Apr 15 '22 at 07:16