# When to use RSA and when ElGamal asymmetric encryption

If i am not wrong in cryptography there are 2 basic cryptographic schemes for public key cryptography. RSA encryption whose security is based on the infeasibility of solving the factoring of big primes problem and the ElGamal encryption which is as secure as the discrete logarithmic problem. The question is whether or not there are specific circumstances where you must use ElGamal instead RSA and vice versa. What are the weak and the strong points of each?

To sum up is it harder under the same attacking model to solve the factoring problem or the discrete logarithmic problem?

Actually, for most applications where we want to use asymmetric encryption, we really want something a bit weaker: key agreement (also known as "key exchange"). When RSA or ElGamal is used for that, one party selects a random string, encrypts it with the public key of the other party, and the random string is used as a key for classical symmetric encryption. Therefore, we must add Diffie-Hellman to the list. You can imagine Diffie-Hellman as a kind of asymmetric encryption in which you do not get to choose the random value you are encrypting: less versatile than ElGamal, yet sufficiently powerful for most protocols where asymmetric encryption is used. SSL/TLS and S/MIME happily use RSA and Diffie-Hellman in practice. Diffie-Hellman, like ElGamal, relies (more or less) on the difficulty of breaking discrete logarithm, and is internally relatively similar to ElGamal.

Among differences between RSA, DH and ElGamal, one can find:

• DH and ElGamal accept elliptic curve variants. They rely on hardness of discrete logarithm on elliptic curves, which is distinct from discrete logarithms modulo a big prime. Elliptic curve variants can use smaller fields, so while the mathematics are a bit more complex, performance is better.

• RSA encryption (with the public key) is faster than the corresponding operation with ElGamal, or half of Diffie-Hellman. On the other hand, RSA decryption (with a private key) is a bit slower than ElGamal decryption or the other half of Diffie-Hellman (especially the elliptic curve variants).

• An RSA-encrypted message is larger than an ElGamal-encrypted message or half a Diffie-Hellman, provided that elliptic curves are used for the latter.

• Historically, RSA was patented in the US, while ElGamal was not -- which is why OpenPGP specified ElGamal usage, and GnuPG tends to favour it over RSA (the RSA patent expired a decade ago, so this is no longer an issue).

• RSA is described by a clear standard, which is free (as in "free beer"), and says precisely where each byte should go. That's very good for implementers: it reduces the possible mishaps. On the other hand, the Diffie-Hellman standard (or that one for the elliptic curve variant) is not free, and, in my experience, less clear. There is no established standard at all for ElGamal, except the bits about it in OpenPGP, which do not deal with ElGamal "in general".

What protocol designers should do is to make some provisions for algorithm agility: the protocol should work with various algorithms, with fields indicating which algorithm is actually used. Algorithm agility helps quite a lot with dealing with future cryptanalytic advances, and with regulatory requirements.

• But Diffie-Hellman does not belong to the family of asymmetric cryptography. It is just the case by which with high probability you will be using it along with symmetry crypto it in scenarios where you share a secret to encrypt data(DH) and then encrypt this secret with public key cryptography(RSA or ELGamal)Right? – curious Jan 17 '12 at 15:31
• @curious: DH is totally asymmetric cryptography; it is not asymmetric encryption, but it is still cryptography and it is still asymmetric ("asymmetric" = "not all involved party share the same secret keys"). Digital signatures are also asymmetric cryptography (and I do not talk about them here). Also, when you use DH you do not use asymmetric encryption over it. You might have a somewhat skewed idea of what Diffie-Hellman is; I suggest you have a look at the Wikipedia page (unless it is shut off, they seem to want to black it out for a day as a protest against some kind of proposed US law). – Thomas Pornin Jan 17 '12 at 16:12
• After a key-exchange you get a symmetric key, yes. But the key-exchange itself is still based on asymmetric crypto. But that's true when you use RSA, DH, or even a combination thereof to exchange the key. Not sure where you got the idea that DH needs a shared secret. – CodesInChaos Jan 18 '12 at 12:28
• @curious: I think you read 99.9% of the books wrong -- quite possibly, the books were unclear. Symmetric cryptography is what you do with the shared key (e.g. AES, HMAC...). DH is how you obtain the shared key (with which you are going to do symmetric cryptography). DH is "asymmetric cryptography" just like, e.g. RSA. – Thomas Pornin Jan 18 '12 at 12:30
• Considering that RSA, the algorithm, was published and fully described in 1978, several years before RSA, the company, was actually founded (in 1982), your assertion is dubious. It would imply that not only NSA paid the company to modify the algorithm, but also gave them access to some time travel technology so that they may get back to 1978 to enact the said modification. (I guess I am in denial of the NSA time travelling powers. Shame on me.) – Thomas Pornin Dec 6 '14 at 13:08

Hardness

As to the hardness of solving factoring, this question (and answers and comments) provides an interesting discussion. As long as you follow recommended key sizes, either cryptosystem is sufficiently secure.

Use Cases

The one use case where I see ElGamal being used over RSA is when a multiplicatively homomorphic cryptosystem is needed (noe that both ElGamal and RSA are multiplicatively homomorphic). The reason ElGamal is preferred is that it is semantically secure "out-of-the-box" (i.e., without modifications (this question and my answer there might provide more insight into what I'm talking about).

• Why RSA is not semantically secure? – curious Jan 17 '12 at 15:21
• First, remember that I am talking "textbook RSA" or RSA w/o modifications. Adding good padding (OAEP) will make RSA semantically secure, but then you lose the homomorphic property. An easy definition of semantic security is being able to distinguish between the encryption of $m_0$ and the encryption of $m_1$ with better than 50% chance. So, you have the public key and know the messages, the challenger gives you $c_b$ and you must say whether $b=0$ or $b=1$. With textbook RSA, you simply encrypt $m_1$ and $m_0$ and compare with $c_b$ to get your answer (encryption is deterministic). – mikeazo Jan 17 '12 at 15:34
• The other case is, when you don’t want to be spied on by the NSA terrorists. – Evi1M4chine Dec 6 '14 at 9:28
• @EviM4chine, do you have proof they can break RSA in general or are you just paranoid? – mikeazo Dec 6 '14 at 10:55
• @Ragnagord, right, but a break in RSA does not imply that P=NP. In other words, you could break RSA and still not know if P=NP. Your first comment says that breaking RSA involves proving that P=NP. That is not true. – mikeazo May 22 '15 at 18:11