Best encryption and signing algorithm for GnuPG: RSA/RSA or DSA/Elgamal?

Question

I have found this relatively old question about whether RSA or DSA is the preferred algorithm for signing and encrypting with GnuPG.

When using gpg --gen-key, the two relevant choices are either "RSA and RSA" or "DSA and Elgamal". Which is better? What are the pros and cons for each? Has anything changed since 2009?

Solution 1

Trustworthy Recommendations

When at the time of the last post, there still was debate on changing default algorithms still found in web archive which had rough consensus, the switch to RSA 2k keys as default has been performed.

Debian recommends using a 4k RSA key in their document about using subkeys and debian-keys readme file. A vast majority of about three quarters of keys in debian developers keyring is (still) DSA/Elgamal (counted by grepping through gpg's output).

In an interview with iX (a German computer sciences magazine, issue 11/2013, also available online for free), the inventor of PGP Phil Zimmermann recommends "at least 3k length when using RSA", although 1k keys are not broken yet. But they're "in reach of attackers rich in resources".

Regarding Security

Right now both are said to be secure for adequate key sizes (4k recommended for RSA, 2k necessary for DSA2, otherwise you will use DSA1 which uses SHA-1).

For selecting a RSA key length, have a look at an overview on the actual strength provided by NIST (p. 64). It is easy to see that the strength does not linearly grow with the key length (and computing time), so double size does not mean "double security".

There was a problem with OpenSSL's DSA-implementation on Debian, but this was caused by using bad random data and could have happened with RSA, too.

Choosing Between RSA and DSA2

pro RSA

• RSA is more wide-spread, though not necessary in OpenPGP standard, all major implementations can deal with it; DSA2 not (yet)
• RSA offers much faster signature checking

pro DSA2

• Smaller signatures, but they're small anyway; for e-mail and code signing probably negligible
• Faster key creation (can be relevant on low power and embedded devices like mobiles and routers)
• Slightly faster for signing

---

My own Decision

When recently creating a new OpenPGP key, I decided to go for 8k RSA for primary keys and 4k RSA as subkeys for daily use. RSA signatures are fast to verify anyway and the huge 8k signatures are only used for signing other keys, but 8k should be considered sufficient for a really long time. 4k is fine for a current subkey as it's cheap to revoke it without loosing all your signatures.

Creating that 8k key took about 20 minutes on my Core 2 Duo T9300, so take your time and do some work (for feeding the random source).

Solution 2

Whereas I opted for a 4K RSA master key with a 3K RSA signing subkey and a 4K El-Gamal encryption subkey. The only reason I haven't gone for a higher master key at this point is because of the prevalence of users with mobile devices which really struggle with the larger keys.

Of course I do have larger keys for certain specific purposes, but that tends not to be for communication with others.

Comments

[code_monk]

why El-Gamal for encryption?