I have just read a passage in Zeilinger's book about quantum world.
My question is: Suppose there exist quantum computers. Given that a quantum computer can use Shor's algorithm, what key length must a user use today for secure RSA encryption?
Information Security Stack Exchange is a question and answer site for information security professionals. It only takes a minute to sign up.Sign up to join this community
Any reasonably sized RSA key will be broken by a quantum computer of comparable size using Shor's algorithm. Don't use RSA if you want to resist quantum computers, no matter the keysize.
The only claim of a variant of RSA that survives are some slides by Bernstein mentioning a 2^43 bit RSA key consisting of 2^31 primes with 4096 bits each. This is obviously ridiculously impractical.
Concrete analysis suggests that RSA with 2^31 4096-bit primes provides > 2^100 security vs. all known quantum attacks. Key almost fits on a hard drive.
If you want asymmetric cryptography that survives quantum computers, you should look elsewhere. For example code or lattice based cryptography are believed to be secure against QCs while having reasonable properties. pqcrypto.org gives a reasonable overview over the impact of QCs and which algorithm classes are useful as post-quantum cryptography schemes.
If general purpose quantum computers can be scaled up to feasibly attack RSA of any modest key size (e.g., b=128 bit), then RSA at any key length is unsafe (or soon will be, unless there is some major theoretical barrier that allowed building systems of that size but prevents building larger systems). To attack 1024 bit RSA you need a quantum computer with b=1024 qubits. Then, it should be able to break RSA in O(b^3) by factoring the modulus using Shor's algorithm. For b=4096 bit RSA, its only a modest scale up of the quantum system (by a factor of 4 in the number of qubits) and running time is only 64 times worse. Compare to the classical difference where a 4096-bit key using the best sub-exponential factoring algorithm is 100 000 000 000 (that is 1011) times stronger than a 1024-bit key. Also note for ordinary users of the cryptosystem, that encryption/decryption time of 1024-bit RSA is roughly 64 times faster than 1024/4096-bit RSA meaning there's not going to be a larger key-size where a classical user of RSA gains an significant advantage over a quantum computing attacker.
However, quantum computers that can run Shor's algorithm to factor large integers are a long way off. The best published runs of Shor's algorithm factored 15 into 3x5 in 2001, and it took more than a decade before another group factored 21 into 3x7 (the current record). The quantum annealing systems by DWave systems are a far way off from being general purpose quantum computers that can do Shor's algorithm; they can only solve one specific problem -- the Dwave problem and haven't been shown to solve that faster than optimized classical annealing problems.
However, if you are worried about quantum computing you must migrate away from PKE systems based on integer factorization or discrete logarithms (including RSA/DSA/El Gamal even with elliptic curves) that can be attacked by Shor's algorithm (or a slightly modified version for elliptic curves).
Types of PKE resistant to Shor's algorithm exist but none of them seem to have widespread use.
One of the most promising is the McEliece cryptosystem which is faster than RSA and can have security grow with key size quickly, except the public key is typically about half a megabyte.
Another one is NTRUEncrypt which has reasonable key sizes and performance, but hasn't gone through as much cryptoanalysis as RSA (and is patented).
Note that while there's no guarantee that a new quantum algorithm will come along and break these Shor-resistant PKE, it isn't expected. You can show that these algorithms are based on NP-hard problems, so if they are broken by a new quantum algorithm this will be major breakthrough in complexity theory (not as big as solving P=NP or P!=NP, but close).
Finally, we should note the difference between symmetric encryption and asymmetric encryption with regards to quantum computing. For symmetric encryption (e.g., block cipher), Grover's algorithm allows one to break a symmetric key of complexity O(N) in O(sqrt(N)) time. Meaning a 128-bit key, which would take O(2128) time to brute-force classically, would only take O(264) time with a suitable quantum computer. So in contexts like the size of your symmetric key and size of your hash, you should just double the length needed classically (that is migrate from AES-128 to AES-256 to be secure).
The slides mentioned by CodesInChaos detail a method of doing multi-prime RSA crypto (something not in widespread use) to get around the primary problem with RSA with respect to Shor's Algorithm: if qbit operations are as fast as bit operations, then Shor's Algorithm can factor primes as fast as RSA can encrypt for any given key size.
In order to get around this, the method explained by DJB uses multi-prime RSA to allow for faster encryption with while using significantly more key material.
How much more? 8 Terabytes to get you approximately the same level of security we have today.