how slow are 4Kbit RSA keys? [was: Re: multiple keys vs multiple identities]

[David Smith]

Jean-David Beyer wrote:
> David Smith wrote:
>> Not truly "quantitative", but I notice a significant difference
>> between encrypting emails to people with 1024-bit keys vs people with
>> 4096-bit keys.  I'd say that the difference is in the order 3-6
>> seconds.
> 
>> I'm running GnuPG 1.4.x on a Sun Ultra10 with a 500 MHz CPU and 1 GB 
>> RAM.  Yes, I know it's old.  :-)
> 
>> We're forced to use 4096-bit keys because some of our customers
>> require it.
> 
> Am I missing something?
> 
> I thought the keys were used to encrypt the block containing the session
> key (that is, IIRC, 512 bits). And it is the session key that is used to
> encrypt and decrypt the actual message. Since the session key is small,
> encrypting or decrypting it should not take a lot of time compared with
> doing an entire message (depends on its length, of course).

Yes, that's partially true, although I thought that the symmetric cipher
is usually a 256-bit key (often AES-256).

> So unless the time to encrypt or decrypt the session key is large
> compared with the time to encrypt or decrypt the actual message, is this
> discussion not about the wrong thing? What is the message size of the
> messages being used to come up with the numbers on this thread? Are they
> realistically large (whatever that might be)?

I was talking about small emails (e.g. a couple of kB).  Since the
symmetric cipher is usually much easier computationally (that's one of
the reasons for going for a hybrid cipher system), the encryption of the
session key starts to dominate the operation, and in my case, there's a
noticable difference of the order of a number of seconds between the two
types of keys.

Most of my emails are short, between members of the team, some of which
have 1024-bit keys, some 2048, some 4096.  Adding on a 5-second delay to
the sending of every email can be a bit of an annoyance (although we
have to live with it...), and although the effect is less pronounced on
decryption, it's still noticeable and probably even more important.