ElGamal Encryption System
What you'll learn: How ElGamal builds on Diffie-Hellman to create a complete asymmetric encryption scheme with strong semantic security.
The Core Idea
While Diffie-Hellman lets two parties agree on a shared secret, ElGamal transforms that concept into a full public-key encryption system. Instead of both parties contributing to a shared key, one party (the receiver) publishes their public key, and anyone can use it to encrypt messages that only the receiver can decrypt.
ElGamal leverages the same discrete logarithm problem that makes Diffie-Hellman secure. The receiver generates a private key (a random number) and computes a public key using modular exponentiation. When encrypting, the sender introduces randomness by generating a temporary key for each message—this is crucial because it means encrypting the same message twice produces different ciphertexts, a property called semantic security.
How It Works (Conceptually)
- Key Generation: Alice picks a prime
p, generatorg, and private keyx. She publishesp,g, andh = g^x mod pas her public key. - Encryption: Bob picks a random number
y, computesc₁ = g^y mod pandc₂ = (message × h^y) mod p. He sends bothc₁andc₂. - Decryption: Alice uses her private key
xto computec₁^x, then recovers the message by calculatingc₂ / c₁^x mod p.
The randomness from y ensures that identical messages yield different ciphertexts, preventing pattern analysis—a significant security advantage.
Key Takeaway: ElGamal extends Diffie-Hellman into a complete public-key encryption system where each message is encrypted with fresh randomness, providing semantic security against adversaries who analyze patterns in ciphertexts.