I had a Source request some information on how encryption works. Rather than get into the mathematical nuances I figured it would be easiest to discuss the types of encryption used. As I use Linux based protocols,
DSA and Elgamal are both based on an underlying mathematical problem, called the discrete logarithm problem, or DLP. The DLP is believed to be very, very hard to solve in any reasonable amount of time.
RSA is based on an underlying mathematical problem, called the integer factorization problem, or IFP. The IFP is believed to be very, very hard to solve in any reasonable amount of time.
Notice a similarity, here? Other than the problem that they’re based on, they’re both very secure. Sorry to be the contradictor here, but RSA is used a hell of a lot more than DSA/Elgamal. Cryptographic tokens such as USB tokens and smart cards use RSA. Most SSL/TLS sites utilize RSA keys. SSH uses, mostly, RSA keys. GnuPG, though, didn’t use RSA until more recently, so older GPG users might have a problem.
The main reason that DSA keys are used in GnuPG is because of the signature system. DSA keys generate signatures whose length depends on the length of the hash used to make the signature. DSA is also restricted on the type of hash that it can use. It’s REQUIRED to use SHA1, you don’t have a choice. RSA keys generate signatures whose length depends on the length of the signing key. RSA keys tend to generate obnoxiously long signatures.
On the flip side of convenience, you have security (which is obviously a hell of a lot more important.) It’s believed, but not proven, that the DLP that DSA is based off of is a harder problem to solve than the IFP that RSA is based on. You’ve also got public exposure and scrutiny. DSA was developed by someone at the NSA. RSA was developed by three guys at MIT. RSA, since it’s so common, has undergone a ridiculous amount of scrutiny and research. DSA hasn’t had that much exposure or scrutiny. It’s also led to the recent factoring of a 1017-bit number. Remember what I said about RSA being based on integer factorization? Beware, though. While it may sound like DSA is the winner, there is something that plays against it. I mentioned that DSA has to use SHA1. Well, SHA1 has been broken. Not “totally useless” broken, but “cryptographically iffy” broken. See below for a greater explanation. You’re also restricted to a 1024-bit DSA key. You can’t make it any bigger, except in a certain case that I’ll discuss later.
So, to summarize what we’ve got so far:
Pros:
RSA – Common, studied, widely believed to be secure.
DSA – Widely compatible with GPG of just about any version. Shorter, more convenient signatures.
Cons:
RSA – Believed to be less secure than a DSA key of the same length. Ridiculously long signatures. Not as compatible, GPG wise.
DSA – Small keysize might leave it quickly vulnerable to a break. Underlying hash, while still trusted, is not suggested for use in new cryptographic applications.
That last one sounds like an issue, right? When SHA1 was cracked, and the keysize started getting a little too small for comfort, the DSS (the underlying specification of the DSA algorithm) was updated. Instead of being restricted to a 1024-bit key using SHA1, you’re now able to use 2048 and 3072 bit DSA keys with better hashing algorithms (SHA224/256 for 2048, and SHA256/384/512 for 3072, your choice.) This does create a compatibility problem for any version of GPG released prior to the updated specification (which is still in draft form. Final draft, but draft, nonetheless.) And it’s a fairly inconvenient thing, too – Anyone that doesn’t have a specific command in their gpg.conf won’t be able to utilize your key.
So, all in all, it’s pretty much your choice. A 2048-bit RSA key, or a 1024/2048 DSA/Elgamal keypair should be more than secure enough, even with the relative (and, currently, minor, though that may change) insecurity of the SHA1 algorithm. The SHA1 break is more theoretical than practical. They found collisions (two different plaintexts that hash to the same output) in 2^69 operations, instead of the 2^80 that they should have. That means that finding a collision is 2000 times easier than it should be. It’s still trusted as a cryptographic hash, but in new systems, it’s suggested to move away. It’s one of those “if you’re using it, keep using it, but if you’re making a new system, use something else” situations.
If you’re paranoid, like me, you can go higher; 4096-bit RSA, or 1024/4096 DSA/ELG-E. Throwing the following in your gpg.conf will let you generate the later revision DSA keys and specify the hash algorithm you want to use, like what I created for experimental purposes (3072/4096 DSA/ELG-E, SHA512):
expert
enable-dsa2
digest-algo sha512
But remember, anyone without the “enable-dsa2” line won’t be able to use keys generated with this method, even your public key. They also will have a problem verifying your signatures.
My Public Key
—–BEGIN PGP PUBLIC KEY BLOCK—–
Version: OpenPGP.js v.1.20130228xsFNBFFX1tABD/98u4EgxQp7YNicJ4zl4RVnSQADGcasRu0BpwdbG7FDS+Ws
3GRWFCTQguF42Ae28FQopIj3mGsJ2W+nrHuPHzxfdQ/8mR5CteyJQwpM1vbT
h0OABObCjdDTLzYmZj/pGt/UjyNVNTYiSBUQ+hVGLJdL1M40CoEhw0jF7hiD
VpwXmjjnqqAbpyvF4eBZbgMcKxDB9ZQwaZZs5fkLFxpGcLJ/b1JUnE4oVlSq
ZyoS8z6hBKi2u4GOCw0eh4CJ2xlRwdQmUzp4jDaeSQEcnM9LVG2BFg71DMtS
cxBQvHvzkcLYtDY0EKL/96qs+/BCf0DgAlhFXH/l7EieE89q2BNajALOfrR6
9fp8YR5CTzFC6WAV7YCTu9q4wCAY82xFlpworXZMGcomM1COvmc9pJjCXfoM
v0acaUZ7bjjd+KuK+s8TnInOED5/ch8ogw2x6vUTZS+m/i62sXy+mOI4NUct
aCluDaQhtUwpKVfOGPIylXYhL6QtlMFI+R4v/JMrX9YabrhrC3FxnNO4cLD0
msgB6hUntJfvTKw5UcQy34a/B1gWPsp8W/6xGQAn0w4/gJKLoT2kDei2uA6x
LtC5K/X2Y8UTeQVf130knTu+fNON/6kmx+LKpyiLcL6lvmbiuAA576XthnEX
wMlsJgPWTWM3VfFGsKgGDB36j4b4b5b11wT9rwARAQABzTFGb3JlY2xvc3Vy
ZXBlZGlhIElTVEFSIDxjb29AZm9yZWNsb3N1cmVwZWRpYS5vcmc+wsFcBBAB
AgAQBQJRV9c1CRCRuoTT5lxkJwAAglcP/jyrV+FHmElrdLAKxwy9i1InWtzA
9vS1t7UXLpqAJP4WGT3W+JUy3B0pxmBhB8NxUSfRyROfqud4CsyfyoQ7Dvb+
roMLxz8wvCCbO0MATVAVZkeyndtFOOoD1LI0VSxix1nWJV4ZH4nQAe+DKzel
2urRIotR0431J1Y3zOEJ27D0epreTqNzooYiwrai/6U2g1BANOC/srZ3bQnf
sE55A6mZnow5D6JHP7hMWrcLfFA8XdHGTJzDd0PbFjbrQwdGHlzAQ8txFCzp
HwgcDgPG444ogb3T2eBdZxs35ov2gnEGw5zHMeF6smTmwxokgm1WvgQ87hLs
0EOrF0GbWfcYbwXVq+UyNCksj/z9YGQAzi3BR2JZ3fTLtJR6GpqNaoGxB/sy
/DBUGH2/Yz9dqfiNSwMbXbeCs69OjDTkitlidZm3q9XniKCt1qYGcsBgargQ
IZ2V+Xk5ZUWcUCunb8bcJHTqDV/0QF0fnMGYVneKXRauHG4VKGMMCvQlNnaY
AahD5e9GHjVB1J/bQwvHTX9jGbrdx9IyOdeU9HxD6+d2kyCHUttE/fAV1bAx
b/Y1fKO+BhdTRFHIf/jVszr1fTTbhCcmNg3x8qbUdsGkgtEBmrKcSt3jeYot
IK6yqCu+nqWxshk0kj9qdDaVx3Xsy2hCOF7aH5U6vtbe63Lrfpf31lOo
=QTMu
—–END PGP PUBLIC KEY BLOCK—–
