Increasing the length by a factor of 2^400 only increased the amount of work by a factor of 20? Staggering, if true in general.

Yeah, that's what got me. Doubling the length of the key only requires a single order of magnitude more work?. If that turns out to be true, I'm going to need to revise my beliefs about how the universe works. In particular, information theory and thermodynamics, because multiplying two numbers together doesn't preserve information about what the factors were. Or at least pretty much everyone thought so. (Caveat: if the values of primes turn out to have a predictable pattern, that could provide the needed information. However, that would mean that the Riemann Hypothesis is false, and that'd be an even more astounding result.)

Thing is, RSA keys are rather 'sparse' because they are the product of two primes. There aren't that many primes, so there aren't that many numbers that only have two (proper) divisors.

Hence, if you look at the strength of the currently best-known attack on RSA keys, you see that the key strength grows quite slowly as the keys get larger. This is purely from how sparse prime numbers are. From [1] which quotes NIST in 2015 we see (both collumns are in bits):

    Strength  RSA modulus size
      80        1024
     112        2048
     128        3072
     192        7680
     256       15360

> Because multiplying two numbers together doesn't preserve information about what the factors were. Or at least pretty much everyone thought so.

Technically the information is still there, it was just thought to be very hard to extract. This paper shows an easier way to extract it.

[1] https://crypto.stackexchange.com/questions/8687/security-str...

Thanks very much.

Actually, you're only increasing the length of the number by a factor of 2, since 2^400 is a 400-bit number.

If true, it's still leaps and bounds ahead of anything we have today, though.

Fair point. "Increasing the key [not the length of the key] by a factor of 2^400".