I have some notes that claim that ElGamal is worse than RSA in the sense that ElGamal is length-increasing. Do anybody know what this means and why is a bad property?


For completeness I show you the model of RSA I'm working on (the very basic one)enter image description here

and also the ElGamal model I'm working on: enter image description here

In fact ElGamal advantages are also pointed out. First generation of parameters is more efficient and second ElGammal works in various types of groups while the setup for RSA is $\mathbb{Z}_{n}$. So the comparison should be done over $\mathbb{Z}_{n}$.

  • 3
    $\begingroup$ The question is under-specified. Are you interested in encryption or signature? ElGamal in the multiplicative group modulo a prime number, or some other form? Insecure textbook RSA, RSA with proper padding like OAEP, or hybrid encryption? Comparison for messages of what length? $\endgroup$
    – fgrieu
    Oct 26 '16 at 15:04
  • 2
    $\begingroup$ If you've a lot of message length-increasement you're gonna need more storage / bandwidth which also means increased cost. $\endgroup$
    – SEJPM
    Oct 26 '16 at 15:08
  • $\begingroup$ @SEJM and why is it ElGamal worse than RSA in this sense? $\endgroup$
    – Rodrigo
    Oct 26 '16 at 15:36
  • 2
    $\begingroup$ As a general claim, I would reject this. Minor performance differences between RSA and ElGamal are either irrelevant, or I can't think of a situation where it would be acceptable to use textbook-RSA (RSA-OAEP also comes with a length increase). $\endgroup$
    – tylo
    Oct 26 '16 at 15:49

What the notes remark is that the ciphertext in ElGamal encryption in $\mathbb Z_p^*$ is about twice as large as the ciphertext in RSA, when working with $p$ and $N$ of about equal size; that's because the ciphertext $(u,v)$ in ElGamal has 2 integers, when $y$ in RSA has 1; and $u$, $v$, $y$ are about the same size (also the size of $p$ and $N$). Making $p$ and $N$ of about same size makes sense, because that give comparable security (for proper other choices).

Larger ciphertext is bad in some sense, because that makes ciphertext transmission even so slightly longer, and requiring extra resources. That fact is not very relevant in practice:

  • A factor of 2 in size there maters in only some applications (and almost not on anything where the message goes thru a modern network), because practice does not use either ElGamal or RSA for bulk data encryption; its uses hybrid encryption, in which the bandwidth used for asymmetric encryption is small in absolute value, and most often in proportion.
  • ElGamal encryption can be done in groups (like, elliptic curve groups) with much more compact representations of elements, and then the balance of ciphertext size shifts straight in the other direction, with ElGamal the winner by a factor of more than 2; so in the rares cases where ciphertext size matters, we want to use this ElGamal variant.
  • There are a lot of other often more important appreciation criteria than ciphertext size for an asymmetric cipher; including
    • public key size (ElGamal wins by an inch in the race condition of the question's drawing, but RSA can pull a provably safe technique and win comfortably, unless ElGamal pulls the other group card),
    • key generation speed (ElGamal wins, assuming the practice of reusing the same group for multiple keys),
    • encryption speed (RSA as usually practiced wins, by a comfortable margin; and its main competitors in this category are cousins like Rabin encryption),
    • decryption speed (ElGamal as usually practiced wins),
    • combined encryption and decryption speed on same hardware (ElGamal as usually practiced wins),
    • simplicity of a safe message padding for non-random message (ElGamal wins by acclamation of the jury)...
  • As an aside, RSA can not safely encrypt arbitrary messages (for $b$-bit security we need to sacrifice at least $b$ bits out of $\lfloor\log_2(N)\rfloor$, and then in RSA OAEP practice we sacrifice about $2b+15$ bits); when ElGamal in $\mathbb Z_p^*$ can encipher any $m$ in that set, including $\lfloor\log_2(p)\rfloor$ bits.
  • That aside itself is moot, since in practice we very often encipher messages much shorter than $\lfloor\log_2(N)\rfloor$ or $\lfloor\log_2(p)\rfloor$ anyway, because the messages really are keys to other cryptosystems.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.