Diffie-Hellman, turned into encryption
Diffie-Hellman (previous module) needs both parties online at once, each contributing a public value in real time. ElGamal, published by Taher Elgamal in 1985, restructures the same discrete-log idea so a sender can encrypt to a recipient's already-published public key with no live interaction at all — the sender simply plays both roles of a DH exchange themselves.
The recipient publishes a public key A = gᵃ mod p exactly as in DH, keeping the private key a secret. To encrypt a message m, the sender generates a fresh, one-time secret k (never reused), computes c₁ = gᵏ mod p — their own "DH public value" — and combines it with A to derive a shared secret s = Aᵏ mod p = g^(ak) mod p, exactly the DH shared-secret computation, done unilaterally by the sender alone. That shared value s masks the message: c₂ = m·s mod p. The ciphertext is the pair (c₁, c₂).
ElGamal encryption and decryption
- 1
Recipient publishes A
A = gᵃ mod p, computed once and reused for every message anyone ever sends them.
- 2
Sender picks a fresh k
A brand-new random value, generated separately for every single message — never reused.
- 3
Sender computes c₁ and the mask
c₁ = gᵏ mod p, and the shared value s = Aᵏ mod p = g^(ak) mod p — the same value the recipient will independently derive.
- 4
Sender masks the message
c₂ = m·s mod p. The ciphertext (c₁, c₂) is sent — s itself never crosses the wire.
- 5
Recipient recovers s
Using their private key: s = c₁ᵃ mod p = (gᵏ)ᵃ = g^(ak) mod p — identical to the sender's s, without any further communication.
- 6
Recipient unmasks m
m = c₂ · s⁻¹ mod p, using the modular inverse of s.
Published in advance, exactly as in Diffie-Hellman.
The sender's one-time secret k plays the role of the sender's "half" of a DH exchange.
A worked example, reusing Alice's Diffie-Hellman keypair
Take the exact p = 23, g = 5, and Alice's secret a = 6 from the Diffie-Hellman module's worked example — her public key there was A = 5⁶ mod 23 = 8. Now Bob wants to send Alice the message m = 10 using ElGamal, encrypting to that same public key.
Bob generates a fresh one-time secret k = 15 (reusing the numeral from the DH module's "Bob" purely for familiarity — in a real exchange this has nothing to do with any DH session). He computes c₁ = 5¹⁵ mod 23 = 19, and the shared mask s = 8¹⁵ mod 23 = 2. The ciphertext's second half is c₂ = 10 × 2 mod 23 = 20. Bob sends the pair (19, 20).
Alice decrypts using her private key: s = 19⁶ mod 23 = 2 — the identical mask Bob computed, recovered without Bob ever having sent it. The modular inverse of 2 mod 23 is 12 (2×12 = 24 ≡ 1), so m = 20 × 12 mod 23 = 240 mod 23 = 10 — the original message, recovered exactly.
Practice
Using the same p = 23, g = 5, and Alice's public key A = 8, Bob encrypts message m = 17 with a fresh one-time secret k = 9. Compute the ciphertext pair (c₁, c₂).
Why ElGamal ciphertexts are always different, even for the same message
Encrypting the identical message m = 10 to Alice's public key twice, with two different one-time secrets k, produces two completely different ciphertexts — because every encryption draws a fresh k, and c₁ and the mask s both depend on it. This is exactly the randomized-encryption property that raw RSA (covered in the RSA padding module) lacks without OAEP: an eavesdropper who sees two ElGamal ciphertexts to the same public key can't tell whether they encrypt the same message or different ones, which is essential for semantic security.
The trade-off is size: an ElGamal ciphertext is always twice the length of the plaintext (the pair c₁, c₂, each roughly the size of the modulus), where RSA's ciphertext is the same size as its modulus regardless. This is one reason ElGamal-family encryption (and its elliptic-curve variants) shows up more often for key transport and hybrid encryption than for encrypting bulk data directly — the same design choice RSA makes for the same reason.
Go deeperSchnorr signatures: the same idea, turned into signing⌄
ElGamal's discrete-log structure also produces signatures directly — DSA (the Digital Signature Algorithm) is essentially ElGamal signing standardized by NIST, and the Schnorr signature scheme (patented until 2008, now the basis of Bitcoin's Taproot upgrade) is a cleaner, more efficient variant of the same idea. The core move: sign by committing to a fresh random value, then blend that commitment with the message hash and the private key so that only the private key's holder could have produced a value the public key verifies.
Signing: pick a fresh one-time secret k, compute the commitment r = gᵏ mod p, derive a challenge e from hashing r and the message together, then compute s = (k − a·e) mod q, where q is the order of the group (here, the same q = p−1 = 22 used throughout this toy example, since g = 5 generates the full group). The signature is the pair (r, e) or (s, e), depending on the convention. Verification recomputes r′ = gˢ·Aᵉ mod p and checks it matches the original r (or that hashing r′ reproduces e) — succeeding only for a signature actually produced with the matching private key a.
Practice
Using a = 6 and q = 22 (as above), a signer picks a fresh secret k = 17 and a challenge e = 5 (derived from hashing the commitment and the message). Compute s = (k − a·e) mod q.