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](http://seclists.org/oss-sec/2012/q2/410)