[adrian_b]

Even if many older RSA implementations had serious security bugs, that is not the reason why it is not preferred any more.

For equivalent security with ECC (or with AES) at their typical parameters (i.e. 256 to 512 bit elliptic curves or 128-bit to 256-bit AES keys), RSA must use very long keys, even longer than any RSA keys that are used in practice (which are normally no longer than 4096 bits), which makes the RSA operations slow and adds a large overhead to the communication protocols that must send and receive such long keys.

[upofadown]

>RSA must use very long keys, ...

But probably no longer than 2048 bits:

https://articles.59.ca/doku.php?id=em:20482030

[adgjlsfhk1]

imo this article dramatically understates the likelihood that the NSA has unpublished factoring algorithms. it also shows the CPU performance plateau, but GPUs have mostly followed exponential performance scaling

[upofadown]

The bottleneck is with a process that can't be parallelized very well. So GPUs are not useful here.

The NSA might have a computer from a crashed alien spacecraft as well but we have to work with what we know. Of course that alien computer is well known to be helpless against RSA and effective against everything else... :)

[adgjlsfhk1]

that bottleneck is a bottleneck specific to the GNFS. There are about a dozen pretty different factoring algorithms known to the public (e.g. trial division, Polard, ECM, quadratic sieve, GNFS). I don't think any mathematicians believe that the GNFS is the optimal factoring algorithm out there. GNFS has runtime L(1/3, cbrt(64/9)) if there is a known algorithm of say L(1/3, 1.5) which would be a pretty minor optimization equivalent to making the GNFS as good as the SNFS, or a bigger breakthrough of say, L(1/4, 2.5), 4096 bit keys could easily be necessary. For reference, this amount of improvement is about the same as the difference between the Quadratic sieve and GNFS.

[upofadown]

Why yes, if there was an algorithm known good enough to make 4096 bit keys necessary then 4096 bit keys would be necessary. But there isn't and there has been little progress for a long time now.

[adgjlsfhk1]

> But there isn't and there has been little progress for a long time now.

publicly. The algorithm side and the hardware side are really really different because we can be pretty sure that the NSA doesn't have a giant super computer that is either dramatically more efficient than commercially available computers, or that uses more than say 1% of US electricity consumption. On the algorithm side, we know that the NSA employs a decent number of number theory people, and given the way that math research progresses, it's pretty easy to imagine that one of those people has found a slight algorithmic improvement over public state of the art. CFRAC was invented in the 1970s. QS invented in the 1980s. The NFS was the 1990s with some improvements in the 2000s. If we go another 50 years or so with no progress, it maybe starts to be reasonable to believe that there isn't a secret algorithm that's better, but with 5 improvements in the last 50 years, it seems pretty likely that there could be 1 more that has been found but not published.