Suppose Alice chooses a random Prime $p$ and a random private Key $a \in \mathbb{Z}^*_p$. By accident, she also chooses a random number $g \in \mathbb{Z}^*_p$, which is not a generator of $\mathbb{Z}^*_p$ and therefore

$$\langle g\rangle \subset \mathbb{Z}^*_p$$

as opposed to $\langle g\rangle = \mathbb{Z}^*_p$, which would yield a valid key. Alice then computes $A \equiv g^a \pmod{p} $ and publishes the Tuple $(p,g,A)$ as her public key.

Bob now encrypts a message $M$ using Alices public key by computing

$$C_1 = g^b \pmod{p}$$ $$C_2 = M \cdot A^b \pmod{p}$$

Is it possible for an attacker (Eve) to distinguish a “real” ciphertext $(C_1,C_2)$ from a random ciphertext $(Z_1,Z_2) \stackrel{$}{\longleftarrow} \mathbb{Z}^*_p$ with significant advantage (say $Adv \geq \frac12$)?

Edit: I guess it should be enough to show, that the ciphertext cannot be random, if

$$\langle g \rangle \neq \langle C_1 \rangle \quad(\text{or $Z_1$, respectively})$$

But how can Eve check for this property efficiently? Can someone point me in the right direction here?

Edit: A real-world situation where this flaw occurred was recently found in the PyCrypto Library

  • $\begingroup$ As a trivial starting point, we know that the order of $g$ divides the order of $\mathbb{Z}^*_p$. From that, perhaps a non-negligible set of potential $g$s have a small order that can be brute-forced to look for $C_1$? $\endgroup$
    – B-Con
    Jun 29, 2012 at 17:02

2 Answers 2


The attacker can distinguish $\langle C_1, C_2 \rangle$ from a random pair if the attacker knows a value $q < p-1$ such that $g^q = 1 \mod p$.

Here's how the distinguisher would work: he simply computes $C_1 ^ q$ and checks to see if that value is 1. If this $C_1$ corresponds to a valid ciphertext, then that value will always be 1. If this $C_1$ is part of a random pair, then the value will be 1 with probability $q/(p-1) \le 1/2$ (remember, $q$ will always be a divisor of $p-1$).

On the other hand, just because we show distinguishability against a particular random source doesn't mean that we have shown that it is insecure. In this case, that would depend on what is the order of $g$ (and whether it is "smooth", that is, has no large prime factors). If the order of $g$ is smooth, then solving the discrete log problem is easy, and hence the system is insecure. On the other hand, if the order of $g$ has a large prime factor $q$, I believe that it is still safe.

  • $\begingroup$ Isn't finding such a $q$ with $g^q \equiv 1 \pmod{p}$ equivalent to solving the discrete logarithm problem? $\endgroup$ Jun 30, 2012 at 15:33
  • $\begingroup$ @padde: no, it is not. It is quite easy if you know the factorization of $p-1$, as q will always be a divisor of that. Even if you don't know the complete factorization, well, you can easily find all the factors under, say, $2^{64}$; unless $g$ was specifically chosen so that $(p-1)/q$ had no small prime factors, it will almost certainly be the case that you can find an appropriate value of $q$. $\endgroup$
    – poncho
    Jul 1, 2012 at 1:27

Actually, you don't want $g$ to generate $\mathbb{Z}^*_p$ for Elgamal. The order of $\mathbb{Z}^*_p$ is $p-1$ (an even non-prime number). Instead, $g$ should generate a multiplicative subgroup of prime order. With Elgamal specifically , message encoding generally requires choosing a value $p$ such that $p=2q+1$ for a smaller prime $q$. Then $g$ should be chosen to have order $q$.

If you use all of $Z^*_p$, one can efficiently test if the plaintext of an encrypted message is a quadratic residue or not, which leaks one bit of information about the plaintext. For CPA-security, you ask the oracle to encrypt a plaintext that is a QR. If the challenge ciphertext encrypts a NQR, you know it is a randomly generated tuple and not an actual encryption of your message.

If I am reading the bug report you posted correctly, it seems the "bug fix" is not correct (possibly the code was correct to begin with, but I can't determine that from the bug report as it has mistakes -- order of 107 in $\mathbb{Z}_{211}$ is not 42; and since 107 is not a safe prime, maybe the code is doing something weird).

  • $\begingroup$ interesting, i didn't know that. but what happens when $g$ isn't a valid generator at all? $\endgroup$ Jun 29, 2012 at 20:16
  • $\begingroup$ If $g$ generates a prime-ordered group that is small (e.g., less than 160 bits), then discrete logs become feasible. If $g$ has composite order, the discrete log will not generally (always) not be hard (there are ways to setup composite groups that are). If $g$ has large prime order, then it is secure even if it is not the order that was intended (but you may have trouble encoding $M$ into $\mathbb{G}_q$). $\endgroup$
    – PulpSpy
    Jun 29, 2012 at 20:28
  • $\begingroup$ Typo: should be "not generally (always) be hard". Also FWIW, if you try and encrypt an $M$ that is not in the group generated by $g$, then you can end up with a different set of problems. $\endgroup$
    – PulpSpy
    Jun 29, 2012 at 20:47
  • $\begingroup$ If the generator has not order p, you don't have Elgamal, but a variant of it I would say. Apart from that, leakage of the Jacobi symbol applies to RSA as well. Using an appropriate plaintext encoding is the correct solution in both cases. $\endgroup$ Jun 30, 2012 at 8:32
  • $\begingroup$ Your first point is semantics, but all modern crypto textbooks do not consider the secure version (order q instead of p-1) a variant. Elgamal with order p-1 leaks Legrange, not Jacobi, but it is true both Elgamal and RSA leak a bit. Padding is necessary for RSA to have CPA (and likely CCA) security, but Elgamal is CPA secure in prime order subgroups without padding. Padding is essentially never used with Elgamal, either because you want the homomorphic properties or you use a hybrid variant (e.g., hash Elgamal). $\endgroup$
    – PulpSpy
    Jun 30, 2012 at 19:04

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.