RSA 4096 ridiculous?

[Werner Koch]

On Wed, 20 Jun 2007 14:32, brian at briansmith.org said:

> None of the mobile phones I tried had no trouble using RSA 4096 to
> encrypt or decrypt a 16 byte key. If the phone has a JVM and/or a web
> browser, RSA 4096 and AES should be no problem.

I did a quick benchmark:

$ tests/benchmark rsa
Algorithm       generate  100*sign  100*verify
----------------------------------------------
RSA 1024 bit        150ms     830ms        30ms
RSA 2048 bit       2140ms    4310ms        80ms
RSA 3072 bit       5470ms   12430ms       160ms
RSA 4096 bit      14350ms   28420ms       270ms

This is raw signing of a random number 8 bits shorter than the modulus
using a public exponent of 65537.  The numbers indeed show that
verificaion is only by a factor of 3 slower for a 4k key compared to 2k
key.  Thus, this proves your statement.

The sign operation is of course far slower: A single sign operation
takes 0.28 seconds on my 1500Mhz Pentium M.  Given that this is the same
time as for a decrypt operation, this will be noticable if you receive a
mail encrypted to several hidden keys (--throw-keyid) and you need to do
trial decryptions.

FWIW, here are the figures for other algorithms:

$ tests/benchmark dsa
Algorithm       generate  100*sign  100*verify
----------------------------------------------
DSA 1024/160           -     910ms       440ms
DSA 2048/224           -    1570ms      1900ms
DSA 3072/256           -    3630ms      4400ms


$ tests/benchmark ecc
Algorithm       generate  100*sign  100*verify
----------------------------------------------
ECDSA 192 bit       60ms    1530ms      1170ms
ECDSA 224 bit       30ms     760ms      1380ms
ECDSA 256 bit       40ms     960ms      1800ms
ECDSA 384 bit       90ms    2150ms      4210ms
ECDSA 521 bit      210ms    5430ms     10510ms

(ECC is still experimental in Libgcrypt and not much opmitized)



Shalom-Salam,

   Werner