How does ElGamal encryption work in detail?
Bob publishes his public key $\beta = g^d \mod p$. Alice picks random $i$, computes masking key $K = \beta^i$, sends $(g^i, m \cdot K)$. Bob recovers $m$ using his secret $d$.
* Bob's secret d rebuilds the same mask K_M = beta^i that hides Alice's message. *
The whole scheme is really one DH exchange with the message multiplied in: Bob's published $\beta$ plays one DH half, Alice's ephemeral $i$ the other, and their shared mask is $K_M = \beta^i = g^{id}$. Bob can rebuild that same mask from the $g^i$ Alice sends, because $(g^i)^d = g^{id}$ — so only his secret exponent $d$ unlocks the message, which is what makes this asymmetric encryption rather than just key agreement.
Key Generation (Bob):
- Choose prime $p$ and generator $g$
- Choose secret exponent $d$
- Compute public key: $\beta = g^d \mod p$
- Publish: $(p, g, \beta)$
Encryption (Alice wants to send $m$ to Bob):
- Choose random ephemeral exponent $i$
- Compute $K_E = g^i \mod p$ (ephemeral public value)
- Compute masking key $K_M = \beta^i \mod p$
- Compute ciphertext: $y = m \cdot K_M \mod p$
- Send $(K_E, y) = (g^i, m \cdot \beta^i)$ to Bob
Decryption (Bob):
- Compute masking key: $K_M = K_E^d = (g^i)^d = g^{id} = \beta^i \mod p$
- Compute $K_M^{-1} \mod p$
- Recover: $m = y \cdot K_M^{-1} \mod p$
Example: $p = 23$, $g = 7$, $d = 6$, $\beta = 7^6 \mod 23 = 4$
- Alice sends $m = 8$, picks $i = 3$
- $K_E = 7^3 \mod 23 = 21$, $K_M = 4^3 \mod 23 = 18$
- $y = 8 \cdot 18 \mod 23 = 6$
- Sends $(21, 6)$. Bob: $K_M = 21^6 \mod 23 = 18$, $18^{-1} \mod 23 = 9$, $m = 6 \cdot 9 \mod 23 = 8$ ✓
Go deeper:
ElGamal encryption — Wikipedia — full key-generation, encryption and decryption steps.