Actually RSA has several "gotchas", so it is not that it has held up but people have managed to work around those gotchas into a working encryption system

(Basically your data is not encrypted with RSA, you encrypt a secondary key, send it with RSA but the main encryption is AES see https://en.wikipedia.org/wiki/Transport_Layer_Security#Key_e... )

There's "gotchas" with every encryption scheme - in fact whenever TLS uses any Public Key encryption scheme it'll pair it with a Symmetric Key encryption scheme. So you could say that by your definition no Public Key encryption scheme has "held up" and they've all had to be worked round :)

There are benefits to pairing the slower Public Key schemes with a Symmetric Key encryption scheme using a session key, as you get the benefits of an Public Key encryption scheme with the performance of a Symmetric Key encryption scheme.

Key exchange is done for speed (symmetric key crypto is way faster than public key) and forward secrecy. It’s not done because RSA is flawed per se. We use DH instead of e.g. ElGamal encryption for the same reasons.

Yeah it's not so much of a flaw of RSA, but encrypting pure text with it for example is more complicated (and has more caveats with padding, etc) than just encrypting a fixed amount of bytes

Don’t think this merits an “actually” - using a session key et al. is basic usage and does not bear on the strength of RSA itself.

A lot of the RSA gotchas are due to trying to take implementation shortcuts either for convenience or speed.

If you don’t choose your primes truly randomly for example.

Using a secondary key and using RSA for the key share is not about avoiding RSA gotchas it’s just about performance.

RSA has effectively been broken many times. We literally had 128bit RSA encryption hardware at one point. There were even export controls on keys beyond a certain length (512bits) that today are trivial to break with the general number field seive. You look at the history of RSA and it’s not pretty. Dixons method had us all scrambling to use 512bit keys (pushing the export restrictions), special number field seive had us rushing to get to 1024bit. The general number field seive more recently pushed us to 2048bits. Who can tell what’s next here. In fact look at the complexity of the special vs general number field seives and you’ll see the statements are almost the same, just some constants reduced. That’s worrying because there’s no reason to think the current constants are a minimum here. We may well find out 2048bits is not enough.

Heck just read a paper in state of the art dedicated RSA encryption hardware from the 80s. All now completely broken. They are very impressed with some of the 512bit hardware!

https://people.csail.mit.edu/rivest/pubs/pubs/Riv84.pdf

That is not when an encryption algorithm is usually considered to be broken, it just means that a certain key length is not sufficient anymore. You can break 20 bit RSA with pen and paper, but as long as a linear change in the key length causes an exponential increase in the decryption time, the algorithm is not broken. At this moment, the record for the factorization of a specific RSA key is one of 829 bits, which suggests (by extrapolation) that within a few decades 1024 bits may not be safe if your adversary has the resources. No (reasonable) key length can be expected to be safe forever, even without any mathematical breakthroughs

I’d say it’s a break if the encryption you once used (512bit and below RSA) is now trivially decrypted thanks to mathematical advances.

RSA 2048 hasn’t been broken but 512bit RSA definitely had been by any definition.

I feel “RSA is fine because much longer key lengths still work” is hiding what happened here. Yes we can still get into the infeasible realm with RSA and really long keys but the algorithm has definitely let us down multiple times thanks to mathematical improvements in factorization that just keep coming.

> Before you start worrying about it though consider that RSA has held up for 47 years of active cryptanalysis so far

True, but is there much overlap between the set of people who actively do cryptanalyses on RSA and the set of people who actively research integer factoring?

As far as I know the skills needed to make progress on integer factoring are not really needed for anything in cryptography other than that specific problem and include a bunch of other skills that have nothing whatsoever to do with cryptography and take a long time to master. It's also been an open and important problem long enough that if it is solved it is likely to be by someone who is a world class expert in it, similar to how Fermat's Last Theorem was finally solved.

Similarly the skills needed for anything in cryptanalysis other than trying to break RSA by factoring are useless for working on integer factoring. The result is that very few, if any, people have the time and ability to become both cryptanalysts and world class integer factoring researchers.

Thus I'd expect nearly all of the 47 years of active RSA cryptanalysis has been on finding and fixing the numerous mistakes that can be made when implementing RSA that allow it to be broken without factoring.

I'd guess it is also similar with the P = NP problem. A solution to that has implications for cryptography but I doubt many cryptanalysts are working on the P = NP problem. Also maybe same for the Riemann hypothesis (I'm not sure if that one has implications for cryptography).