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