[AnotherGoodName]

That happened many many times over with rsa!

The us government used to restrict export of long rsa keys. At one point much of the world was using 128bit rsa keys but Dixon method had everyone scrambling to use 512bit keys. Then the special number field drive had us all scrambling to use 1024bit keys and the general number field seive again had us scrambling to get to 2048bit keys.l and that really wasn’t that long ago relatively speaking.

Check out rsa encryption hardware from the 80s. They are really proud of some of the hardware that can do 512bits! (Useless today)

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

The special and general number field seize complexity statements are a few constants in difference. Look at those constants. Do they seem to be some root limit to you? Is it really that unlikely that there’s not a way to reduce those further making even 2048bit keys useless?

You don’t need to ask “what would happen if RSA broke” because those of us who have been through this many times now can straight up tell you. You’ll be scrambling to once more bump up the key size and you’ll be auditing all the potential data leaked.

[jjav]

> At one point much of the world was using 128bit rsa keys

When?

I was writing crypto libraries in the early 90s to support RSA, DSA and ElGamal at my company (this predates the times when good open source crypto libraries were broadly available).

Even back then 128 bit RSA keys were not used. The smallest the library supported was 512 and the smallest we ever used in production was 768 bits.

That's how far back my own memory goes. But here's a paper from Arjen Lenstra from 2001 which has a table showing computationally equivalent key sizes back to 1982.

https://infoscience.epfl.ch/server/api/core/bitstreams/c323a...

In 1982, security comparable (at the time!) to DES would have been 417 bit RSA keys.

So even in 1982, using 128 bit RSA keys made no sense!

> You’ll be scrambling to once more bump up the key size and you’ll be auditing all the potential data leaked.

If you've had to do this for RSA keys (more than once, even!) I respectfully suggest you need to be a lot more conservative picking key lengths. There has never been a sudden breakthrough in factorization that has rendered conservatively chosen RSA key lengths obsolete overnight.

[simpaticoder]

RSA failures with bit-depth were a matter of degree; a prime number factorization break-through would be a matter of kind.

[AnotherGoodName]

It’s not log(n) but still a break since we were literally using lower bit strength than was trivially factorable thanks to mathematical advances and to the point of thinking RSA 2048 is safe, well we once thought that about 128bit RSA. If the above pans out like the general number field seive did we may yet need to move the goal posts further. And we really really shouldn’t be surprised if it happens since it’s happened so many times already.

[MobiusHorizons]

I believe this was one of the reasons for the broad adoption of elliptic curve based cryptography. The mechanism is not based on prime numbers, so smaller keys were adequate, and it was hoped that they might avoid future degradation due to prime factorization research. Of course they could still be vulnerable to their own attacks, but it still requires an attacker to expend more resources.