I ask about ElGamal algorithm. Is ElGamal algorithm used new key for each encryption process. in other word it should we use new key for each chunk? For example, if we have message that has four block each block less than $P$. Where $P$ is the prime number used in ElGamal. How many keys should be used to encrypt this message?


If you have the setting of $G$ being a prime order $p$ group (written multiplicatively) generated by $g$ and your public-secret key pair is $(pk,sk)=(y=g^x,x)$, then encrypting a single message $m\in Z_p$ amounts to choosing $k\in_R Z_p$ and computing $(c_1,c_2)=(g^k,my^k)$.

If you have a message $m=(m_1,\ldots,m_l) \in Z_p^l$, then the ciphertext would be $((g^{k_1},m_1y^{k_1}),\ldots,(g^{k_l},m_ly^{k_l}))$ with the $k_i$'s being distinct (but the public key $y$ is the same, since it is intended for one receiver).

Observe, that when using the same $k$ for two messages, say $m_1$ and $m_2$, then you can infer non-trivial information about the messages from the ciphertexts $(g^k,m_1y^k)$ and $(g^k,m_2y^k)$, since computing $m_1y^k(m_2y^k)^{-1}$ gives you $m_1(m_2)^{-1}$. Consequently, choosing a fresh randomizer $k_i$ for every block is essential.

Nevertheless, if you have to encrypt multiple blocks in practice, you would use KEM/DEM style hybrid encryption for the sake of more efficiency.

A side note: if you encrypt a message $m\in Z_p$ under distinct public-keys $y_1,\ldots,y_n$, then you can re-use the randomness $k$. This means, that instead of choosing $k_1,\ldots,k_n \in_R Z_p$ and sending $((g^{k_1},my_1^{k_1}),\ldots,(g^{k_n},my_n^{k_n}))$, you can choose $k\in_R Z_p$ and send $(g^k,my_1^k,\ldots,my_n^k)$ which saves you computation and bandwidth. You may look here for a general treatment of this so called randomness re-use in multi-recipient encryption: journal paper or the previous paper versions paper1, paper2 for further details.

| improve this answer | |
  • 2
    $\begingroup$ Efficiency is not the only reason why we don't do that. You should also note that encrypting blocks separately is insecure (according to most natural definitions of security). You can freely replace and reorder blocks in the ciphertext. $\endgroup$ – K.G. Oct 8 '13 at 8:42
  • $\begingroup$ Yes, thats another and from a security point of view more important reason to avoid it. Replacing will still be an issue for a single ciphertext, if you do not use additional measures to guarantee authenticity. Say you sign all ciphertext pairs together or the message prior to encryption, then you eliminate this reordering and replacing issue (although there is still the efficiency issue). But even if you send only one encrypted message per time interval (say one per minute) and even if you authenticate your message, you still have to avoid re-using the randomizers $k$. $\endgroup$ – DrLecter Oct 9 '13 at 6:55

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.