# ElGamal with weak public key

Assuming this setup: A prime $p$, a generator $\alpha$ in $\mathbb{Z}_p^\ast$. Alice chooses her private exponent $d$ from $[2, p-2]$ and calculates her public key $\beta$ = $\alpha^d$.

Bob then chooses his private key $i$. The resulting masking key $k_M$ used to encrypt the message is then calculated as $k_M = \beta^î$.

I wondered if the following attack is mathematically possible:

If $\beta$ turns out to be $p-1$, there will be only two possible results from the $k_M$ exponentiation being $1$ and $p-1$. This is because the element $p-1$ in a cyclic multiplicative group always has $ord(p-1) = 2$, so only those two elements can be generated by $\beta$. This in turn means that only two masking keys $k_M$ exist. The attacker can then easily try those two keys and will immediately be able to decrypt the message.

Can you confirm whether this attack will work and, if yes, if real-world ElGamal implementations are vulnerable against it?

We'll have $\beta = p - 1$ iff $d$ just happens to be the value $(p-1)/2$; this happens with probability $1 / (p-2)$.
For El Gamal to be secure at all, $p$ needs to be large, say, at least 2048 bits. This means that this has a probability circa $2^{-2048}$ of happening. We typically don't sit around worrying that we'll be hit by a meteor in the next 10 seconds; that has a much higher probability of happening than us picking the bad $d$.