Using bad generator in ElGamal Encryption 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
The attacker can distinguish $\langle C_1, C_2 \rangle$ from a random pair if the attacker knows a value $q &lt; 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.