Encryption keys: RSA vs. ElGamal

[Sven Radde]

Hi!

at120 at hushmail.com schrieb:
> I know that "A disadvantage of 
> the ElGamal system is that the encrypted message becomes very big, 
> about twice the size of the original message", 
This may be true, but mind you that the "message" the ElGamal (or RSA)
encrypts is only the symmetric (=256bit) key which will then be used to
encrypt the actual plaintext. Therefore, the impact of size overhead is
minimal. (Mostly the same goes for performance issues.)
The size of the key has a vastly greater impact on performance issues
than algorithm choice, IMHO.

Anyway, keys are free. Go ahead and create two "test" keys: One RSA and
one ElGamal and write a little script that simulates your intended use
and makes a protocol of ciphertext sizes and performance measurements.
This way, you will probably get the most detailed information for your
intended application and make your own assumptions whether each
algorithm satisfies your (unstated) requirements.
> and that both seem 
> to be limited to use no larger than 4096-bit keys, but that's all I 
> know.
I don't think that this is a theoretical limitation. It is definitely
not for RSA (there are larger keys around).
The current implementations do not generate larger keys because larger
keys don't bring real advantages.
>  Please don't give me "they're both secure enough"
Well, without going into the algorithm details, this is probably as
detailed an answer as you can get.
4096 bit RSA is as secure as 4096 bit ElGamal - both are "unbreakable"
(in practice). Then, if you are worried about an attacker that might
break 1024 bit RSA, you won't be safe with 1024 bit ElGamal, either.
One might add that (it is my impression that) more research goes into
factoring algorithms (hence, into breaking RSA) than on the discrete
logarithm problem. But as far as I understand the math, both problems
are rather related, anyway. So, if factoring research yields practical
advances in algorithms for attacking RSA, ElGamal breaking might become
easier as well.
> Are there any patent issues with ElGamal?
IANAPL (I'm not a patent lawyer), but the general opinion is: "No."
> if there's a patent on it, will 
> it expire/has it expired in 2007?
>   
This depends on your jurisdiction and the exact dates when those
hypothetical patents would have been filed.
Regarding patent 4,200,770, it has apparently expired:
<http://cr.yp.to/patents/us/4200770.html>

HTH, Sven