2
$\begingroup$

Assume we have 2 prime numbers in form p = 2q + 1.

Is it safe to use the cyclic group of order p-1 instead of one with order q in ElGamal encryption? I couldn't find any suitable source to explain why we should use q as order of our group and avoid p-1.

Most websites and sources just say:

use cyclic group of order q

without any explanation.

What have I tried? I assumed p = 11 and therefore q = 5. I did all calculations of ElGamal-Encryption by considering 10 as my group order($Z_{p}^{*}$):

  • Group(G) = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
  • Group Order(q): 10
  • *Generator(g): 7
  • Message(m): 9

and there was no problem in decrypting the message. So I think there is something wrong with its security!

I thinks there is no need to mention the calculations using q = 10 But if you need them, just comment below the question to bring them into the question as an update.

$\endgroup$
1
  • $\begingroup$ Pohlig-Hellman? $\endgroup$
    – kelalaka
    Mar 1 at 8:33
2
$\begingroup$

Is it safe to use the cyclic group of order $p-1$ instead of one with order $q$ in ElGamal encryption?

  1. No, for small values of $p$. This is the only security issue in the question's example. For modern security, $p$ should be at least in the order of $2048$‑bit (rather than $4$‑bit for $p=11$ in the question), and not close to a prime power. Anything below says $512$‑bit ($\approx155$ decimal digits) is quite vulnerable to the recovery of the private key from the public key

  2. No, if «use» refers to the plaintext set. Problem is: from the ciphertext of ElGamal encryption, an adversary can find if the plaintext $m$ is a quadratic residue modulo $p$ or not (that is, if $m^{(p-1)/2}\bmod p$ is $1$ or $p-1$). How is left as an exercise to the reader. Reference: Dan Boneh, Antoine Joux, and Phong Q. Nguyen's Why Textbook ElGamal and RSA Encryption Are Insecure (in proceedings of AsiaCrypt 2000), recommended in Yehuda Lindell's answer.

    This property breaks security under Chosen Plaintext Attack, and even weaker notions. It can be a practical weakness: if it was enciphered a name on the public class roll (using a large $p$), we could rule out about half the names given the ciphertext. If it was a coin toss with fixed public values for head and tail, for about 50% of the choices of these values, the coin toss would leak.

    The safe and usual option is to restrict the plaintext to the group of quadratic residues, that is to $m$ with $m^{(p-1)/2}\bmod p=1$. That happens (perhaps by chance) to be the case in the question's example, since $9^5\bmod11=1$.

  3. Yes, if «use» refers to the set for $g$ and the issues above are taken care of: it is safe to use $g$ that generates the whole cyclic group. That's the case in the question's example, since $7^5\bmod11=11-1$.

    However that's unusual because we must restrict the plaintext (per 2), and customarily we restrict $g$ to the same group, so as to be back to ElGamal encryption (re‑)stated in a generic group. That's what sources do when they just say: «use a cyclic group of prime order $q$».


As stated, the textbook solution to the problem in (2) is to restrict the plaintext to the subgroup of quadratic residues. When we encipher a small discrete set, that's fine: we can handpick the $m_i$ representing the set elements.

But when we encipher arbitrary data, like a name on the class roll, that won't do. In practice that's solved using hybrid encryption. But if we want to remain closer to straight ElGamal encryption in $\mathbb Z_p^*$, a workable method goes:

  • The plaintext $m$ is restricted to an interval $[0,m_{\text{max}}]$ with $m_{\text{max}}<(p-1)/2$
  • To encipher $m$ in that interval, the sender computes $m'\gets(m+1)^2\bmod p$ and encrypts that using normal ElGamal encryption. Note that $m'$ is a quadratic residue, thwarting the attack.
  • After the receiver deciphers $m'$, they find the smallest of the two modular square roots of $m'$ (modulo $p$) using e.g. Tonelli-Shanks, then subtract one to find $m$.

Beware of side channels in the implementation!

$\endgroup$
3
$\begingroup$

The answer to your question can be found in the paper Why Textbook ElGamal and RSA Encryption Are Insecure by Boneh et al. It is an easy paper to read and worthwhile going through the details there.

$\endgroup$

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.