So in the news this week, IBM have created a universal quantum computer with 5 fully functional qubits. Logic and Moore's law dictates they will be able to scale this up to a lot more qubits within a few years. With Shor's algorithm, elliptic curve cryptography will likely be the first to fall as it has lower key lengths and therefore a lower number of qubits are required to break it. If using RSA with larger key sizes e.g. 2048 bits, this may buy a few more years of time, hopefully then a transition to post-quantum algorithms can be made.
Does anybody know:
- How many qubits are required for breaking RSA 2048 and RSA 4096 in real-time with a quantum computer?
- How many qubits are required to break Curve25519?
- I want to work out the relationship between the key length and number of qubits required to break that key length. Is there a simple layman's formula for working out how many qubits are required using the number of key bits and number of qubits as inputs into the function? E.g. n = number of public key bits, q = number of qubits the machine has, a = the answer (number of qubits required to break it). Maybe the formula is just a = n = q, i.e. 2048 qubits are required to break RSA 2048.
If you can prove your answer with citations to any papers or research that would also be beneficial.
Edit: I have found this answer. Anyway if I plug in N = 2048 to the Θ(log(N^2)) equation, this gives me 15.25 qubits required to factor RSA 2048. RSA 4096 bits is not much better, requiring only 16 qubits. Is that correct?! Why is everyone not running around with their hair on fire?