undefined | Better HN

0 pointsAnotherGoodName1y ago0 comments

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

0 comments

doetoe1y ago

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

AnotherGoodNameOP1y ago

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.

j / k navigate · click thread line to collapse