# Can Quantum Computers crack RSA and AES?

Im trying to learn more about cryptography and ran into a post, Is AES-128 quantum safe?, which asks if AES-128 is safe. From the articles and replies it seems that AES-128 (symmetric key) is safe even with the advent of quantum computers (for now). However, it seems that asymmetric keys are not safe?

So, assuming you have a TLS 1.3 (which uses symmetric AND asymmetric keys) would quantum computers be able to decrypt the traffic sent using a cypher like TLS_AES_128_GCM_SHA256? Is decrypting the Diffie-Hellman (asymmetric key) enough to see the plaintext of something or would you still need to decrypt the AES-128 as well?

Do you need to decrypt both the symmetric and asymmetric key in a TLS_AES_128_GCM_SHA256 or can you just decrypt the public key then you don't need to bother with the private key.

• For now, quantum computers do not crack any crypto. It's uncertain if (and then when) we'll have Cryptographically Relevant Quantum Computers.
– fgrieu
Mar 6 at 7:03
• I think this may answer a lot security.stackexchange.com/questions/87345/… Mar 7 at 11:42
• There appear to be limits the size of quantum computers. It's unclear whether we will ever be able to work around the physical constraints which prevent us from building Cryptographically Relevant Quantum Computers. All we can currently do is speculate. Mar 9 at 15:06

It's almost public knowledge by now.

• Quantum Computing (QC) does break existing asymmetric-key algorithms - those based on integer factorization and discrete-logarithm such as RSA, DH, ECDSA, etc.

• QC does weaken symmetric-key algorithm, but not breaking them in the practical sense.

So, in the TLS example you've given, once we've broken the DH key exchange, we'll be able to derive the symmetric key used in the cipher suite.

That's why we're developing post-quantum cryptography. The goal is to develop algorithms that're based on hard problems that quantum computers can't solve any more efficiently than classical computers.

• It might be worth changing "does" to "can, in theory" - as I understand it, this isn't something that current quantum computers can actually do, it's something that we can mathematically prove that more powerful quantum computers would be able to do. At best, it's an optimistic prediction about some future quantum computer which is orders of magnitude more powerful than those that currently exist. Mar 7 at 12:15
• @IMSoP QC here stands for Quantum Computing, not Quantum Computers. An important difference. Mar 7 at 22:20
• @OrangeDog Firstly, the answer currently uses the same abbreviation in two different ways ("QC does" and "QCs can't"); it would be improved by spelling both out. Secondly, the question says "Quantum Computers", so that is surely what the answer should be addressing. So, I stand by my comment that the answer would also be improved by stating the difference between theory and practice explicitly, rather than relying on such tiny subtleties. Mar 7 at 22:54
• Ah, didn't spot that last one Mar 7 at 22:55

In general in Internet cryptography there is a key establishment mechanism separate from a bulk encryption mechanism. Where Diffie-Hellman (including elliptic curve Diffie-Hellman) is used, it is as a key establishment mechanism that provides a symmetric key for a bulk encryption method such as AES-GCM or chacha20. Breaking an Internet Diffie-Hellman would likely provide a symmetric key which could then be trivially used to break the bulk encryption. There's a similar challenge around authentication which is where RSA might come in.

However, TLS1.3 is not limited to key establishment using Diffie-Hellman nor authentication using RSA. In addition to DH key establishment, TLS1.3 supports pre-shared key (PSK) mechanisms and mixed-mode. These allow keys to be established out of band. If the out-of-band establishment method is quantum safe, then the quantum vulnerability is avoided. Examples of quantum safe methods might include physical key management (such as using MILENAGE key material from mobile phone SIM cards) or symmetric key management systems such as Kerberos.

However, for many (most?) Internet connections today, the DH method is currently favoured. Future standards may support other key establishment options.

• @Daniel_S I see, I also ran into this thread crypto.stackexchange.com/questions/102675/… and see you mentioned that it'd take ~13 x 10^6 physical qubits to decrypt RSA. So in my example of TLS_AES_128_GCM_SHA256, if this is true then given Moore's law, it'd take 433 x 2^12 = >13 million qubits. Aka 12 years of development to decrypt in 1 hour? (433 is the record for qubits i believe)? And Is AES_GCM traffic something that can be stored and decrypted in the future or is this just theoretical? Mar 6 at 18:27
• @cryptoman534345 In terms of the number of qubits, quantum computing is currently growing faster than Moore's law. However the qubits need to improve not just in number, but also in quality. Having said that 10-15 years seems to be the best estimate of experts in the annual report of the Global Risk Institute. Store now/decrypt later attacks have happened previously in history (see e.g. Enigma/TUNNY at Bletchley Park), but AES128_GCM is estimated to have a shelf-life of at least fifty years. Mar 6 at 18:38
• @Daniel_S By shelf-life do you mean that TLS_AES_128_GCM_SHA256 data/traffic can be harvested/decrypted for 50 years? If so, it seems so much is hopeless then? Is there anything I'm not aware of in AES128_GCM that offers protection against QC? What is stopping nation states from harvesting consumer data? Mar 6 at 19:05
• @cryptoman534345 I mean that even if harvested now it will not be decryptable for at least 50 years. This is considered to be beyond the value lifetime of consumer data; for example government data is thought to have a value lifetime of thirty years. Mar 6 at 19:24
• @cryptoman534345 As in my answer the quantum attack applies only if the key were established using Diffie-Hellman. If the key were established using a quantum secure PSK, then the harvest attack could possibly work 10-15 years from now and if consumer data needs to be protected for this long then they should not be relying on Diffie-Hellman protections. Note for example that credit card data typically has a value lifetime of less than five years. Mar 6 at 19:48

Independent of quantum computing considerations, what you see is encrypted AES traffic if and when you decrypt the asymmetric encryption, as well as getting the keys for the symmetric encryption which is the point of asymmetric encryption, i.e., key exchange for the communication session.

• ahh I see. So 2 decryptions are required to see the plain text of a traffic? One for the asymmetric encryption first and then the symmetric (AES-128) encryption? Mar 6 at 0:46
• that is correct Mar 6 at 1:07
• If you decrypt the asymmetric encryption, you typically get the keys for the symmetric encryption.
– jpa
Mar 6 at 13:48