Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
up vote 4 down vote accepted

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.

share|improve this answer

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 :)

share|improve this answer
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. – Henrick Hellström May 8 '14 at 17:53
Theoretically it can be done, right? :) but yes, I agree with you.. ElGamal is certainly not the best way to do it!! – Subhayan May 8 '14 at 18:00
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. – Henrick Hellström May 8 '14 at 18:07
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 :) – Subhayan May 8 '14 at 18:24
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. – tylo May 9 '14 at 10:49

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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