# 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?

## 1 Answer

Can you confirm whether this attack will work

It depends on a situation which is mind boggingly unlikely to happen, but if it is does happen, yes, it will work.

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$.

• The usual verb here and its participle is boggle/boggling. 'bong' means to ring like a bell, or as a slang backformation, to smoke marijuana. I don't think either of those is what you want :) – dave_thompson_085 May 1 '18 at 5:16