For those of us less familiar with cryptography and RSA in general: what are the implications if RSA is broken? What are the mitigations that would need to occur in its place?
The public web and code signing PKIs collapse overnight. Most certificate authorities use RSA-2048 either for the roots or intermediates. The HN site not only uses a RSA-2048 key in its own certificate, the CA issuing that certificate and the root CA issuing the intermediate also do.
All data transmitted without forward secrecy on most web sites is compromised. Most websites nowadays use forward secrecy and/or ECDSA, but data sent years ago may still be of value (e.g. passwords) and become decryptable now.
Any data (e.g. backups, past e-mails) encrypted using RSA keys is at risk.
Any authentication system relying on RSA keys has a problem. This can include systems like smartcards or HSMs that are hard to update, software or firmware updates, etc. Banking too.
Edit to add - if RSA-1024 is practically breakable but RSA-2048 is not: some systems that relied on RSA-1024 have a problem. These should be rare, but sometimes legacy doesn't get updated until it becomes an absolute emergency. Everyone realizes that RSA-2048 is only a matter of time, that time is running out quicker than expected, and starts upgrading to ECDSA with more urgency. This will likely take a long time due to legacy hardware.
The parameters can, in theory, be safely used by everyone, and generating them is relatively expensive. But because a few of these parameters were extremely widely used, and they were only 1024 bits strong, it is believed that a gargantuan effort to break them was worth it and the NSA did it.
Forward secrecy does not protect against broken cryptography, so this is more about what methods were used and how much an new technique like this affects them.
Forward secrecy only protects against the exposure of private key material. It does not protect against broken cryptography as it depends on the cryptography to keep old messages private. That's because it works by forgetting the session keys. If you can derive those session keys again then it is of no value.
The interesting part is using a weakness in one part to help decrypt a different part.
In TLS 1.3 all suites (such as TLS_AES_128_GCM_SHA256) have forward secrecy so it isn't even explicitly called out.
In these modern modes (and in other modern protocols like SSH) the two peers agree random ephemeral keys (these days with Elliptic Curve Diffie Hellman) and long term private keys are only used to sign things to prove who you're talking to over the resulting securely encrypted connection.
So if you break RSA you can forge those signatures but you can't decrypt messages sent to and from the legitimate owner of the keys, those were, as your parent explained, secured with AES and not RSA. You would need to perform a live active attack, a MitM to interpose between the real server and its clients so as to decrypt all messages in transit.
It's a continuum from "impossible to do with all the time and energy of the universe and the most advanced computers we have" to "my commodity hardware can crack it in a few minutes".
The same goes for fears of quantum computing breaking current cryptography. It goes from effectively impossible to "yeah, we could break it with a few years of constant computation, which is plenty of time to switch to quantum resistant schemes".
Even if the paper is correct it seems to fall into the 'moving down the continuum' category.
If there were, for example, a way to glean a private key without factoring the modulus, I think we'd all agree that this amounts to "breaking" the system insofar as that it changes the applicability of the hardness assumption.
On the other hand, simply achieving a faster way to factor the modulus is, at best, part of a continuum as you say.
That's not how you treat broken cryptography. If your data is already collected and stored encrypted by a third party which still holds value after several years, you're already in bad shape.
2. Major issue is going to be webpki and replaying govt captured encrypted communications.
3. There are a lot of abandoned servers out there that use RSA. There is a lot of code signing that uses RSA. There is just a lot of identity proven on the web that uses RSA to prove the identity. It's going to be a clusterfuck of identity. Again, assuming the paper means RSA is just completely broken.
Only if you somehow "know" quantum computing is ever going to be practically realized. It may never be.
The current quantum computers are just on the edge of what we can simulate classically, so we can't yet rule out the possibility that realizing a quantum computation requires an exponential amount of energy in the number of qubits. (Though it should be noted that quantum mechanics predicts that this will not happen.)
There is a possibility that QM will break somewhere, but I wouldn't consider this very probable...
I don't think this is true...
1024-bit and higher RSA is still unfactorable, so I don't think anyone will be attacking RSA directly any time soon.
Also, that whole thing about lots of computer encryption tech suddenly being effectively insecure.
But then there's that line: "This destroys the RSA cryptosystem" in the abstract of the paper.
The mitigation would be to move to experimental post-quantum crypto systems immediately (quantum computers have all the fuss because they can break rsa).
This is basically an unbelievable result. Without actually providing some factored numbers i am very doubtful.
[I have not read paper]
Edit: as pointed out below, i may have gotten overexcited. Still an incredible result if true.
"A bit"? A lot more than a bit. A world.
And on the surface, since it appears to be a factoring system, rather than a general purpose discrete log solver, the consequences, while incredible, are far more limited than the picture you paint. If this is even true; a matter over which I'm skeptical.
It does not extend to breaking eliptic-curve cryptography, for the same reason that the Quadratic Sieve does not extend to eliptic-curve crypto: the underling math problem is different (factorisation vs discrete logarithm).