ElGamal Encryption

ElGamal Encryption

Taher ElGamal published this scheme in 1985, building directly on Diffie-Hellman key exchange. Diffie-Hellman only lets two parties agree on a shared secret. ElGamal uses that same math to encrypt an actual message. Its security rests on the discrete logarithm problem. With a large enough prime, recovering the private key from the public key is infeasible.

Unlike RSA, ElGamal is probabilistic: encrypting the same message twice produces two different ciphertexts. It’s also patent-free, which helped it spread into tools like GNU Privacy Guard. The related ElGamal signature scheme later became the direct ancestor of the Digital Signature Algorithm.

Table of Contents

• Keys and Parameters
• Encrypting a Message
• Decrypting a Message
• A Worked Example
• Python Implementation
• Limitations
• ElGamal vs. RSA vs. ECC
• Real-World Applications
• Security Considerations
• FAQ
• References

Keys and Parameters

ElGamal uses the same setup as Diffie-Hellman. A large prime p, and a generator g of the multiplicative group mod p.

1. Choose a random private key x, where 1 < x < p − 1.
2. Compute the public key: y = gˣ mod p.
3. Publish (p, g, y). Keep x secret.

Encrypting a Message

To encrypt a message m (represented as a number less than p):

1. Choose a fresh random value k, where 1 < k < p − 1. This must never be reused across messages.
2. Compute c₁ = gᵏ mod p.
3. Compute c₂ = m · yᵏ mod p.
4. The ciphertext is the pair (c₁, c₂).

Decrypting a Message

Given the ciphertext (c₁, c₂) and private key x:

1. Recompute the shared secret: s = c₁ˣ mod p. This equals the sender’s yᵏ, since yᵏ = (gˣ)ᵏ = (gᵏ)ˣ = c₁ˣ.
2. Compute the modular inverse of s: s⁻¹ mod p.
3. Recover the message: m = c₂ · s⁻¹ mod p.

Interactive Visualizer

The visualizer above runs this exact encryption and decryption with small demonstration numbers. Encrypt the same message twice with a different random k each time. Notice the two ciphertexts look completely different, even though they decrypt to the same plaintext.

A Worked Example

• Parameters: p = 23, g = 5
• Private key: x = 6 → Public key: y = 5⁶ mod 23 = 8
• Encrypting m = 10 with k = 3: c₁ = 5³ mod 23 = 10, c₂ = 10 · 8³ mod 23 = 14
• Ciphertext: (10, 14)
• Decrypting: s = 10⁶ mod 23 = 18, s⁻¹ mod 23 = 9, m = 14 · 9 mod 23 = 10

Python Implementation

The key generation, encryption, and decryption steps above translate directly into code. It uses the same small numbers as the worked example:

def generate_keypair(p: int, g: int, x: int):
    y = pow(g, x, p)
    return (p, g, y), x  # public key, private key

def encrypt(m: int, k: int, public_key):
    p, g, y = public_key
    c1 = pow(g, k, p)
    c2 = (m * pow(y, k, p)) % p
    return c1, c2

def decrypt(ciphertext, x: int, p: int):
    c1, c2 = ciphertext
    s = pow(c1, x, p)
    s_inv = pow(s, -1, p)
    return (c2 * s_inv) % p

if __name__ == "__main__":
    p, g = 23, 5
    public_key, private_key = generate_keypair(p, g, x=6)

    message = 10
    ciphertext = encrypt(message, k=3, public_key=public_key)
    recovered = decrypt(ciphertext, private_key, p)

    print(f"Public key:  {public_key}")
    print(f"Ciphertext:  {ciphertext}")
    print(f"Recovered:   {recovered}")

This reproduces the worked example exactly: public key (23, 5, 8), ciphertext (10, 14), and the recovered message 10.

Limitations

This is a genuine, complete implementation of the real algorithm, not a simplified stand-in:

• Toy-sized prime. Real ElGamal needs a prime matching modern discrete-log security recommendations, discussed below. Here, p = 23 is trivially breakable. It was chosen purely to keep the arithmetic checkable by hand.
• No random k generation. The code takes k as an explicit argument for reproducibility. A real implementation must generate it fresh for every encryption. It needs a cryptographically secure random source.
• Messages must fit in a single value less than p. Real deployments take one of two paths. They restrict ElGamal to encrypting a symmetric key, or encode messages as elliptic curve points.
• No input validation. Neither function checks that m < p, or that a supplied ciphertext is well-formed.
• Never use this, or hand-rolled ElGamal of any size, in production. Real applications should use a vetted library’s implementation, or an equivalent construction built on ECC.

ElGamal vs. RSA vs. ECC

Feature	ElGamal	RSA	ECC
Security basis	Discrete logarithm problem	Integer factorization	Elliptic curve discrete logarithm
Key size (equivalent security)	1024-4096 bits	1024-4096 bits	160-512 bits
Ciphertext size	~2x message size	~1x message size	~1x message size
Deterministic	No (probabilistic)	Yes	Depends on scheme
Patent history	Always free	Patented until 2000	Mostly free

Real-World Applications

• GNU Privacy Guard (GPG) and OpenPGP, which support ElGamal as an encryption option.
• Hybrid cryptosystems, where ElGamal encrypts a short symmetric key. That key then encrypts the actual data, avoiding ElGamal’s own ciphertext expansion.
• The ElGamal signature scheme, a separate construction from the same 1985 paper. It’s the direct ancestor of DSA.
• Elliptic-curve variants (EC-ElGamal), used in some confidential-transaction schemes on blockchains. ElGamal’s homomorphic properties let encrypted amounts be added together directly.

Security Considerations

ElGamal’s security depends entirely on getting a few details right:

• k must never repeat. Reusing k for two messages under the same key exposes the private key. The two ciphertexts can be combined algebraically to isolate it.
• The prime should be safe: (p − 1) / 2 should also be prime. This avoids small-subgroup attacks that leak bits of the private key.
• Like RSA and ECC, ElGamal isn’t quantum-resistant. Shor’s algorithm breaks the discrete logarithm problem, the same way it breaks factorization.

FAQ

How does ElGamal differ from RSA?

ElGamal is probabilistic: the same message encrypted twice produces different ciphertexts, while RSA is deterministic. ElGamal relies on the discrete logarithm problem; RSA relies on factorization. ElGamal ciphertexts are also roughly twice the size of the plaintext.

Why is the random value k so important?

Each encryption needs its own fresh k. Reusing it across two messages exposes the private key to simple algebra.

Is ElGamal secure against quantum computers?

No. Like RSA and standard ECC, ElGamal’s security collapses against Shor’s algorithm. It offers no post-quantum protection on its own.

Why is ElGamal less common than RSA in practice?

RSA arrived earlier, has simpler mathematics for most implementers, and produces smaller ciphertexts. ElGamal’s main advantages mattered less once RSA’s own patent expired in 2000.

Can ElGamal be adapted to elliptic curves?

Yes. EC-ElGamal replaces the modular exponentiation with elliptic curve point multiplication. It keeps the same structure while shrinking key sizes considerably.

References

1. ElGamal, T. (1985). “A public key cryptosystem and a signature scheme based on discrete logarithms.” IEEE Transactions on Information Theory, 31(4), 469-472.
2. Menezes, A., van Oorschot, P., & Vanstone, S. (1996). Handbook of Applied Cryptography. CRC Press. cacr.uwaterloo.ca/hac
3. Diffie, W., & Hellman, M. (1976). “New directions in cryptography.” IEEE Transactions on Information Theory, 22(6), 644-654.
4. GNU Privacy Guard Project. “The GNU Privacy Guard.” gnupg.org
5. Wikipedia. “ElGamal encryption.” en.wikipedia.org/wiki/ElGamal_encryption