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 encrypted: 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 od 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
In 99,9% of books in cryptography when your refer to symmetric you refer to applications in which encryption and decryption share the same key which is achieved with DH and when you refer to asymmetric you indicate a cryptosystem in which encyption and decryption use different keys. According upon the aforementioned assumptions that's why i am asking why did you put in the discussion the DH.In your initial answer you said: "You can imagine Diffie-Hellman as a kind of asymmetric encryption" and then at the comment : But Diffie-Hellman does not belong to the family of asymmetric cryptography ??? –  curious Jan 18 '12 at 9:53
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
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