11

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?

elcojon
  • 213
  • 2
  • 6

3 Answers3

15

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.

CodesInChaos
  • 11,854
  • 2
  • 40
  • 50
  • It seems strange that a composite number with 2^31 primes would be all that much more secure. You'd think that a 2^43 bit semiprime would be superior. – forest Feb 03 '18 at 06:07
  • @forest but then decryption would be much slower. – CodesInChaos Feb 03 '18 at 07:52
  • I'd assume that decryption with a 2^43 bit key would be slow anyway. But then again I'm not a cryptographer. – forest Feb 04 '18 at 02:05
  • @forest I'd guess the version using a billion small primes would take a couple of months for decryption knowing the private key (using a single CPU core), while doing the same using the semi-prime version would take a billion years (about as expensive as breaking it using Shor's algorithm). Security against known attacks should be about the same for both variants. – CodesInChaos Feb 12 '18 at 13:09
10

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).

Community
  • 1
dr jimbob
  • 38,768
  • 8
  • 92
  • 161
  • `To attack 1024 bit RSA you need a quantum computer with b=1024 qubits.` I think you need double the qubits, so 2048 qubits for RSA 1024, 4096 qubits for RSA 2048, etc. – forest Feb 03 '18 at 06:08
  • 1
    Correct. I meant that it's obvious you need at least n qubits (e.g., to at the very least initialize the number to factor that's possibly modified in place). Searching the literature the best circuit I can find for Shor's is 2n+3 qubits ( https://arxiv.org/abs/quant-ph/0205095 ), and possibly more if you require error correction. But the general argument still stands. Once you can get hundreds qubits coherent for long periods, RSA dies unless there is a major barrier preventing going larger. – dr jimbob Feb 04 '18 at 03:45
  • 1
    I think even hundreds of qubits in coherence would not be able to factor an average RSA key. It's not like you can get away with half the qubits or something. It won't just take a little longer to factor. – forest Feb 04 '18 at 04:03
  • 1
    Yes. But when the technology gets good enough to break say 64-bit RSA with O(hundreds qubits) that can be maintained coherent long enough to run Shor's algorithm (and there aren't any known theoretical barriers to scaling up), I wouldn't feel safe with RSA of any size -- because soon enough (possibly still years to decades) someone should be able to scale it up to thousands of qubits with coherence long enough to run Shor. Whereas, I'm still relatively confident in RSA when it can't factor numbers bigger than b ~ 5 bits. – dr jimbob Feb 04 '18 at 21:38
3

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.

tylerl
  • 82,225
  • 25
  • 148
  • 226