In the ElGamal cryptosystem, I was wondering whether the $m$ (message) should be less than $p$ (large prime). Because on decryption, we are getting $m \bmod p$. For $m \bmod p$ to be equal to $m$, shouldn't $m$ be less than $p$? So what should be the size of $p$? Should it be a very very large prime number if I need to encrypt a file of 5 GB or something?


2 Answers 2


As your message treated as one element in the finite field defined by $p$, it must be smaller than this $p$.

There are other reasons, but you mention one about why to use hybrid systems. When you encrypt using public key, the process starts by generate a random symmetric key used to encrypt your data. What is encrypted using the public key is this symmetric key.

Another reason is to encrypt to more than one recipient. The data itself is encrypted once for all, and is this symmetric key the one encrypted for each target.

Note that the size of a symmetric key is much smaller than the size of its equivalent in security in public key.


no.. just have only a very large prime $p$, then break your file into chunks less than $p$..

use Cipher Block Chaining (CBC) or Cipher Feedback (CFB) to get the work done.

For more concrete references on them, see Modes of Operation. this Wiki is pretty cool to begin with. Maybe you can look at here after that :)

  • $\begingroup$ How, and why, would you possibly use ElGamal encryption in a chaining mode? It is not a block cipher and the cipher text is always greater than the plain text. $\endgroup$ May 8, 2014 at 17:53
  • $\begingroup$ Theoretically it can be done, right? :) but yes, I agree with you.. ElGamal is certainly not the best way to do it!! $\endgroup$
    – Subhayan
    May 8, 2014 at 18:00
  • $\begingroup$ No, it is theoretically impossible, unless you alter either the modes or the ElGamal encryption algorithm beyond recognition. I am curious about if you had any such alterations in mind, and if you can point to a security analysis of the result. $\endgroup$ May 8, 2014 at 18:07
  • $\begingroup$ i still want to say it can be done.. i'll do something, i will have a blog post or something similar (next week, sorry for delay) and give you a link :) $\endgroup$
    – Subhayan
    May 8, 2014 at 18:24
  • 2
    $\begingroup$ Can it be done? Probably. Just use one half of the ciphertext in the chaining, or apply some hash function to the chaining, or anything similar; XOR can also be replaced with addition in the field or another operation, it doesn't matter. Is it proven? No. Is it any good? Absolutely not. $\endgroup$
    – tylo
    May 9, 2014 at 10:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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