I have a rather silly question regarding the comparison of RSA with ElGamal over integers. If you want to compare their performance in the same level of security, does the modulus of both of them need to be the same size, or does RSA have to be double the size of ElGamal?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
You never need larger parameters than for RSA. In the worst case ElGamal parameters and RSA parameters are equal size. But you can significantly reduce ElGamal parameters depending on the setting you are using for ElGamal.
If you are working in $Z_p$ with $p$ being a prime number, you work in a field of the same bitlength as required for RSA. But to obtain IND-CPA security you have to work in a subgroup where the DDH is hard (take a safe prime and work in the large prime order subgroup). Then, considering costly operations (exponentiations) it is cheaper than RSA for private key operations (public key operations with a small exponent in RSA are far cheaper).
If you instantiate ElGamal over elliptic curve groups, you can drastically reduce parameter size (1024 bit RSA vs 160 bit elliptic curves at the same security level). However, curve arithmetic can be expensive and is not necessarily more efficient (especially for "small" security levels).
$\begingroup$
$\endgroup$
RSA and ElGammal are about equally secure at the same modulus size (assuming, of course, intelligent parameter selection in both cases).
For RSA (assuming you use good padding), the best known-attack is to factor the modulus with NFS.
For ElGammal (assuming you use a subgroup with a large enough prime factor), the best known-attack is to compute the discrete log of the public key with NFS.
Now, the version of NFS to compute discrete logs is somewhat more complicated than if it were used to factor; however I don't believe that extra complication adds a significant time to the time taken.
