Course contentsShow
← Computer Science
Lesson 2413 of 2,87254. Cryptography FundamentalsFree lesson

ElGamal Encryption System

Asymmetric encryption scheme based on Diffie-Hellman that provides semantic security properties.

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)

  1. Key Generation: Alice picks a prime p, generator g, and private key x. She publishes p, g, and h = g^x mod p as her public key.
  2. Encryption: Bob picks a random number y, computes c₁ = g^y mod p and c₂ = (message × h^y) mod p. He sends both c₁ and c₂.
  3. Decryption: Alice uses her private key x to compute c₁^x, then recovers the message by calculating c₂ / 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.