2048 or 4096 for new keys? aka defaults vs. Debian

[Robert J. Hansen]

On 10/27/2013 4:21 PM, Mark Schneider wrote:
> Are there formal reasons why the max length of the RSA key is limited in
> gnupg[2] linux packages to 4096 Bits only?

Yes; because past 3072 bits it's time to go to something other than RSA.

Several respectable organizations (not only NIST) have done their best
to come up with equivalencies between symmetric keys and asymmetric
keys.  They all seem to converge on the following:

A 1024-bit RSA key is equivalent to an 80-bit symmetric key
A 2048-bit RSA key is equivalent to a 112-bit symmetric key
A 3072-bit RSA key is equivalent to a 128-bit symmetric key
A 15,000-bit RSA key is equivalent to a 256-bit symmetric key

Each additional bit in an RSA key yields less resistance to
cryptanalysis than the one before it.  Moving from 1024 bits to 2048
bits gives you an additional 32 bits of entropy; moving from 2048 to
3072 only gives 16 bits of entropy.

If someone is able to successfully factor a 3072-bit key, they're quite
probably also going to be able to successfully factor a 4096-bit key.

PGP 5.0, way back in the day, introduced 4096 bits as the cap on RSA key
lengths.  This was before we'd put asymmetric and symmetric key lengths
on a firm mathematical basis.  Nowadays, there's really no reason to go
past RSA-3072 (and me, I think there's no reason to go past RSA-2048).
If you need more than that, you should be looking into elliptical curve
cryptography rather than a longer RSA key.