Quiz Entry - updated: 2026.07.10
What is the fundamental limitation of Diffie-Hellman that ElGamal solves?
With DH, neither Alice nor Bob can choose the resulting shared key — it's randomly determined. ElGamal extends DH to allow sending a specific chosen message by multiplying it with the DH-derived key.
The shift in thinking is from agreeing on a random secret to sending a chosen secret. DH can only hand both parties an unpredictable $K$; ElGamal reuses that very same $K$ as a one-time mask, so Alice can push a message of her own choosing through it instead of being stuck with whatever random key the exchange produced.
The DH limitation:
- After DH, both parties have $K = g^{ab} \mod p$
- This $K$ is random — neither party chose it
- DH is only useful for establishing a session key for symmetric encryption
- You cannot use DH to encrypt or sign a specific message
ElGamal's solution (1985, Taher Elgamal):
- Perform a DH-like exchange to get a shared "masking key" $K$
- Multiply the actual message $m$ by $K$: ciphertext $y = K \cdot m \mod p$
- Bob recovers $m$ by computing $K^{-1} \cdot y \mod p$
- The key $K$ is ephemeral (temporary, used once) — hence called a KEK (Key Encryption Key) or ephemeral key
Go deeper:
ElGamal encryption — Wikipedia — how ElGamal turns DH into a message-encryption scheme.