> quantum computers would be able to retroactively break any public keys that were stored
Use a key exchange that offers perfect forward secrecy (e.g. diffie Hellman) and you don’t need to worry about your RSA private key eventually being discovered.
> Forward secrecy is designed to prevent the compromise of a long-term secret key from affecting the confidentiality of past conversations. However, forward secrecy cannot defend against a successful cryptanalysis of the underlying ciphers being used, since a cryptanalysis consists of finding a way to decrypt an encrypted message without the key, and forward secrecy only protects keys, not the ciphers themselves.[8] A patient attacker can capture a conversation whose confidentiality is protected through the use of public-key cryptography and wait until the underlying cipher is broken (e.g. large quantum computers could be created which allow the discrete logarithm problem to be computed quickly). This would allow the recovery of old plaintexts even in a system employing forward secrecy.
The relevant RSA break is sufficiently powerful quantum computers, which also break ECDH (actually, ECDH is easier than classically equivalent-strength RSA for quantum computers[1]), so no, you’re not fine.
I would actually expect RSA to see a resurgence due to this. Especially because you can technically scale RSA to very high levels potentially pushing the crack date to decades later than any ECC construction. With the potential that such a large quantum computer may never even arrive.
There are several choices with scaling RSA too, you can push the primes which slows generation time considerably. Or the more reasonable approach is to settle on a prime size but use multiple of them (MP-RSA). The second approach scales indefinitely. Though it would only serve a purpose if you are determined to hedge against the accepted PQC algorithms (Kyber/MLKEM, McEliece) being broken at some point.
also that paper (IMO) is ridiculously conservative. Just using 1GB keys is plenty sufficient since it would require a quantum computer with a billion bits to decrypt.
How long does it take to generate a key that big? What probabilities do you need to put on generating a composite number and not a prime? Does the prime need extra properties?
Based on https://eprint.iacr.org/2017/351.pdf it would be about 1900 core hours (but I'm pretty sure optimized implementations could bring it down a bunch). No extra properties needed and moderate probability is sufficient.
Perfect forward secrecy doesn't work that well when NSA motto is - store everything now decrypt later. If they intercept the ephemeral key exchange now they can decrypt the message 10 or 50 years later.
Diffie Hellman doesn’t ever send the key over the wire, that’s the point. There is nothing to decrypt in the packets that tells you the key both sides derived.
Unless they break ECDHE, it doesn’t matter if RSA gets popped.
Diffie Hellman to the best of my understanding also relies on the same hard problems that make the public key cryptography possible. If you trivialize factoring of big numbers, you break both RSA and the original DHE. Not sure how it will work for elliptic curves, but my instinct tells me that if you make the fundamental ECC problem easy, the exchange will also go down.
Perfect forward secrecy requires the exchange of ephemeral keys. If you use either ECC or RSA for this and the traffic is captured a quantum computer will break it.
All perfect forward secrecy means is that you delete your own ephemeral private keys, the public keys stay in the record. And a quantum computer will recover the deleted private keys.
Also, none of the currently accepted post-quantum cryptographic algorithms offer a Diffie-Hellman construction. They use KEM (Key Encapsulation Mechanism).
Use a key exchange that offers perfect forward secrecy (e.g. diffie Hellman) and you don’t need to worry about your RSA private key eventually being discovered.