One thing this paper ignores is side channel attacks. Those may involve hardware or software vulnerabilities, or they may be inherent to the process itself.
So the real bogeyman is not whether we have figured out how to factor large numbers yet (aside from Shor and the as of now mythical quantum computer), but how much information you might leak by using your key.
One (generally) overlooked idea might be, some sort of vulnerability between they key and the data being used. E.g., by multiplying many, many smaller numbers with the private key, is it possible to increase the efficiency of the sieve.
Then it might be the case that commonly used keys are more vulnerable and keys used less are less vulnerable.
Another idea would be a rainbow table of keys. It might not matter so much that you can arbitrarily factor a large number, if generating keys is fast. Especially when you mount attacks on the random number generators involved, you can reduce the search spaces.
Forcing the key itself is not so much the concern, this doesn't make me think "oh we are fine".
Historically we only have to look back to e.g. Heartbleed to be reminded that we broke ssl not by factoring primes, but by exploiting the many flaws in the protocol itself.
> One thing this paper ignores is side channel attacks.
I mean, that's fair right? The article doesn't talk about encryption in general but tries to answer "How secure is RSA?" or rather "When is/will N bit RSA be considered insecure?", so scoping it to only talk about that seems fair.
Of course, one could only focus their attention on so many things. Misuse, misconfiguration, side channel attacks and etc become unrelated to the topic at hand in this case.
My point was essentially that key-length could have unintended side-effects.
E.g. if you were to have some rainbow table approach, e.g. in theory larger key size would mean more possible key combinations, meaning more expensive space complexity, and harder-to-crack keys. Factoring a key is not necessary if you already know the factors, a hashtable has O(log(N)) complexity. If you implement some custom FPGA hardware and a nice database its not too difficult to imagine some specialized operation storing off generated public keys to their corresponding private key pairs, and the power costs are rather low.
Of course due to combinatorics the size of this output space is rather large, despite the fact that the distribution of primes shrinks as they grow larger, but the argument is about factoring a single number, not about efficiently computing primes and their common multiples. Counter to the article, it completely obviates the need to hide your power bill, as you can cache every single computation from the past 30+ years...
To bring it back to what I was saying, the difficulty of brute-forcing RSA (or other schemes) is potentially irrelevant to the cost of obtaining a solution, and higher bit-length key-pairs offer some hedge against that possibility. It seems pretty relevant to the question "how secure is RSA" to me.
So the real bogeyman is not whether we have figured out how to factor large numbers yet (aside from Shor and the as of now mythical quantum computer), but how much information you might leak by using your key.
One (generally) overlooked idea might be, some sort of vulnerability between they key and the data being used. E.g., by multiplying many, many smaller numbers with the private key, is it possible to increase the efficiency of the sieve.
Then it might be the case that commonly used keys are more vulnerable and keys used less are less vulnerable.
Another idea would be a rainbow table of keys. It might not matter so much that you can arbitrarily factor a large number, if generating keys is fast. Especially when you mount attacks on the random number generators involved, you can reduce the search spaces.
Forcing the key itself is not so much the concern, this doesn't make me think "oh we are fine".
Historically we only have to look back to e.g. Heartbleed to be reminded that we broke ssl not by factoring primes, but by exploiting the many flaws in the protocol itself.