What are the advantages of RSA signatures against ElGamal signatures? Is there a situation in which it would be better e.g. to use RSA signatures?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Are you talking about actual ElGamal signatures or are you talking about (EC)DSA signatures? If it is the former, the question should rather be "why would it be better to use ElGamal signatures?". $\endgroup$– SEJPMCommented Jun 5, 2016 at 12:38
-
$\begingroup$ I'm talking about actual ElGamal signatures. So, why would it be better to use ElGamal signatures? $\endgroup$– userkirCommented Jun 5, 2016 at 12:46
-
$\begingroup$ I have read that RSA encryption (with the public key) is faster than the corresponding operation with ElGamal. On the other hand, RSA decryption (with a private key) is a bit slower than ElGamal decryption. But this doesn't helped me to awnser my question. Si is there just a speed difference ? $\endgroup$– userkirCommented Jun 5, 2016 at 12:58
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
TL;DR: The main reasons to prefer RSA over ElGamal signatures boild down to speed, signature size, standardization, understandability of the method and historical establishment as the result of a lot of lobby work.
The main technical advantage of RSA is speed.
With RSA you only need to do a small-exponent exponentation to verify a signature, where as with plain ElGamal signatures you'd have to do three full-sized exponentiations to verify a single signature. And if you read this, also think about embedded processors who have a public key hardcoded and have to verify the integrity of security-critical firmware updates and other things sent from a central server.
Another domain where RSA is faster, is key generation. If you do ElGamal naively, you'll generate your own field and generator, which is really slow, especially if you consider that "ElGamal primes" $p$ need the special property that $(p-1)/2$ is also prime. Compare that to RSA where you'd only need to find two (random) half-sized primes without any special property and take into consideration that the workload grows superlinear in bitsize.
Of course, if you use standardized fields and generators, ElGamal key generation becomes much faster as it simply is one exponentation and selecting a random integer.
The next domain where RSA is superior to ElGamal is signature with message recovery.
RSA allows you to sign messages which you don't have to encode outside the signature itself which allows very short messages (less than 1700 bits or so) to be directly embedded in the signature, greatly reducing bandwidth requirements in embedded devices and smartcards.
ElGamal signatures on the other hand require you to hash the message and thus you have to append the message to the signature as there's no way to recover it from the hash 100% of the time.
The third point why RSA is superior to many people is standardization.
RSA is greatly defined and standardized in PKCS#1 allowing any developer to just grab the specification and produce an interoperable implementation without any doubt, as every single step is documented. How to encode the hash? Documented. How to convert integers to byte sequences? Documented. How to transfer public keys? Documented.
ElGamal signatures on the other hand completely lack such a specification and the best you can find are some "ad-hoc" implementations following the original mathematical description. Not exactly ideal for interoperability.
It should be noted however, that the related DSA (which is a variant of ElGamal signatures) does have excellent specifications in the form of FIPS-186 (PDF) or your national equivalent.
One of the less technical but still important points to be noted is understandability.
When it comes to RSA, it's super-easy to understand. You take 5-15 minutes with a developer and you can explain him how they work and he can imagine why they are secure. Signature and verification are straight-forward operations and there isn't an awful lot to be done wrong.
ElGamal signatures on the other hand are more difficult to understand. For example in ElGamal your verification is at best an "consistency check" at a first look and the overall description is much much more complex to read and understand, especially compared to RSA. After all, there's a reason why RSA is taught in (some) schools and not ElGamal.
The final and probably one of the more important reasons is lobbying.
Back in the day when RSA was invented, Rivest, Shamir and Adleman sat together and also founded the RSA company. This company sold the RSA cryptosystem to companies and lobbyied a lot for it's use and ensured it ended up in a lot of standards for data authentication (for example at the IEEE).
ElGamal signatures had no comparable economical interest behind them that supported them. It must be said however that DSA did had a similar interest behind it, as the US government established it specifically to avoid RSA (and the related patent cost) and mandated it for quite some time for official products.
-
2$\begingroup$ Congratulations if you have made it this far down the post (if you read it all) :) $\endgroup$– SEJPMCommented Jun 5, 2016 at 13:53
-
$\begingroup$ Mostly agree, but one small point: RSA-signature-with-recovery is up to the modulus size minus some overhead; for currently common size (2048) that's about 1700-1800 bits. 1500 bytes would require a modulus of about 12500 bits which is possible but very unusual. $\endgroup$ Commented Jun 12, 2016 at 4:49
-
1$\begingroup$ Great post, but… "Another domain where RSA is faster, is key generation." – err, no, au contraire, ElGamal key generation is ridiculously faster than for RSA, because you literally only need to pick one random number and perform one modular exponentiation. You are right that finding safe primes is expensive i.e. the naive approach, but that is a user error, not any problem with the cryptosystem. In particular, while ElGamal signatures are rarely used, it is based on Diffie-Hellman and e.g. OpenSSL will only generate dhparams once per installation. See also e.g. ephemeral DH. $\endgroup$ Commented Jun 4, 2019 at 10:15
-
$\begingroup$ @ArneVogel when I said "key generation" I meant "including parameters for ElGamal" ie without using predefined fields and instead finding your own random safe prime of full size which is much slower than finding two random half size primes. $\endgroup$– SEJPMCommented Jun 4, 2019 at 10:19