PGP RSA key size - encryption/decryption time

Question

From what I've read, PGP only uses the pub/priv keys for encrypting/decrypting a symmetric key used for actually encrypting/decrypting data. I'd reasonably assume that longer asymmetric keys wouldn't be much slower than shorter ones, since they would only be needed for encrypting/decrypting the mentioned symmetric key. This answer and some other googlable resources suggest that keys with bigger lengths decrease performance. Am I missing something here? Aren't bigger keys - for PGP at least - almost always better?

Answer 1

With RSA, encryption is mostly quadratic in the public modulus size, decryption is mostly cubic. This means that doubling the key size (e.g. from 2048 bits to 4096 bits) means four times the cost for encryption, eight times for decryption. (For ludicrously large keys, of more than 20000 bits or so, other algorithms become worthwhile and decryption is no longer cubic, but that does not apply to "normal" RSA implementations.)

However, you are right in that the encryption or decryption is only a one-time operation for a symmetric key. With a basic PC, a rough order of magnitude is that 1024-bit RSA takes about one millisecond for decryption; so 2048-bit RSA will mean 8 milliseconds, and 4096-bit RSA will imply 64 milliseconds or so. As you can see, the figures remain very low, in human terms. The perceived cost of encryption and decryption in PGP depends on the I/O costs more than anything else; when you receive and decrypt a 5 MBytes email, it will take a few seconds to download it, but only a few milliseconds to actually decrypt it (symmetric encryption can easily proceed at 100 MB/s, and the asymmetric decryption is a one-shot operation, as explained).

Longer keys are not necessarily better. We like longer keys because known cracking algorithms take more time when the key is longer. However, there is a point where this argument ceases to be valid: when the key is so long that it cannot be broken with Earth-based technology, then it is "long enough" and making it longer will not bring any significant good. Current RSA-breaking record is for 768 bits, and it is believed that 1024 bits are on the verge of the feasible (but we do not know on which side of the boundary it is). A 2048-bit RSA key is already more than big enough, with a comfortable security margin. The same can be said about 2048-bit ElGamal and DSA keys (which PGP also uses).

On the other hand, longer keys mean longer emails (because a signed email with PGP includes a copy of the key), although this is hardly significant (a few extra hundred bytes per email won't matter much). A more important reason not to use oversized keys is interoperability: some implementations may have internal limits, due to the way they were designed, and a huge key might exceed these limits. Apparently, some versions of GnuPG have trouble with keys of more than 4096 bits. Keys of 2048 and 4096 bits ought to work everywhere.

A more minor reason is that key generation can become prohibitively expensive with larger key sizes -- but you don't do that often, so this is only minor.

To sum up: with PGP, uses keys of 2048 or 4096 bits, and you will be happy. Don't be too worried about that choice; either is fine. Don't go beyond 4096 bits because it will trigger interoperability issues.