Elgamal Encryption

Introduction

In the realm of modern cryptography, ElGamal encryption stands as one of the cornerstone public-key cryptosystems. Introduced in 1985 by Taher ElGamal, this algorithm marked a significant advancement in asymmetric cryptography by building upon the foundational Diffie-Hellman key exchange protocol. Unlike symmetric ciphers such as AES, ElGamal enables secure communication without prior shared secrets, making it ideal for open networks like the internet.

ElGamal is probabilistic—meaning the same plaintext encrypted multiple times with the same public key produces different ciphertexts. This property provides strong resistance against chosen-plaintext attacks and adds an extra layer of security through randomness.

While not as widely deployed in its original form as RSA, ElGamal remains highly influential. It powers digital signature schemes (e.g., DSA – Digital Signature Algorithm), hybrid encryption systems, and is a key component in secure voting protocols and blockchain technologies.

Mathematical Foundation: The Discrete Logarithm Problem

The security of ElGamal relies on the Discrete Logarithm Problem (DLP), which is believed to be computationally infeasible for large prime fields.

No efficient algorithm exists to solve DLP in properly chosen groups (e.g., large prime fields or elliptic curves), making it a solid foundation for cryptographic security.

Key Components of ElGamal

Step-by-Step: Key Generation

1. Choose a large safe prime p such that p = 2q + 1 and q is also prime (optional but recommended).
2. Select a generator g of ℤ_p* (or a subgroup of high order).
3. Pick a random private key x ∈ {2, 3, …, p-2}.
4. Compute public key:
   h = g^x mod p
5. Publish: (p, g, h) | Keep secret: x

Encryption Process

To encrypt a message m (where 0 ≤ m < p):

1. Select a random ephemeral key k such that 1 ≤ k ≤ p-2 and gcd(k, p-1) = 1 (or simply k ∈ [1, p-2] in practice).
2. Compute:
   c₁ = gᵏ mod p
   c₂ = m · hᵏ mod p
3. Output ciphertext: (c₁, c₂)

This is a Diffie-Hellman-like masking: c₂ hides m using the shared secret hᵏ = (gˣ)ᵏ = gˣᵏ.

Decryption Process

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

1. Reconstruct the shared secret:
   s = c₁ˣ mod p = (gᵏ)ˣ = gᵏˣ = (gˣ)ᵏ = hᵏ mod p
2. Compute the modular inverse of s:
   s⁻¹ mod p   (using Extended Euclidean Algorithm)
3. Recover plaintext:
   m = c₂ · s⁻¹ mod p

Full Example (Educational – Small Numbers)

Let’s walk through a complete example using small (insecure) values:

• p = 23 (prime)
• g = 5 (generator)
• Private key: x = 6
• Public key: h = 5⁶ mod 23 = 15,625 mod 23 = 8

Public Key: (23, 5, 8)

Encrypt m = 10:

• Choose k = 7
• c₁ = 5⁷ mod 23 = 78,125 mod 23 = 10
• hᵏ = 8⁷ mod 23 = 2,097,152 mod 23 = 18
• c₂ = 10 · 18 mod 23 = 180 mod 23 = 19

Ciphertext: (10, 19)

Decrypt:

• s = 10⁶ mod 23 = 1,000,000 mod 23 = 18
• s⁻¹ mod 23: Find y such that 18y ≡ 1 (mod 23) → y = 9
• m = 19 · 9 mod 23 = 171 mod 23 = 10

Recovered! m = 10

Pseudocode Implementation

import random
from sympy import mod_inverse  # Or implement Extended Euclidean

# Key Generation
def generate_keys(p, g):
    x = random.randint(2, p-2)
    h = pow(g, x, p)
    return (p, g, h), x  # public, private

# Encryption
def elgamal_encrypt(public_key, m):
    p, g, h = public_key
    k = random.randint(2, p-2)
    c1 = pow(g, k, p)
    c2 = (m * pow(h, k, p)) % p
    return (c1, c2)

# Decryption
def elgamal_decrypt(private_key, ciphertext, p):
    x = private_key
    c1, c2 = ciphertext
    s = pow(c1, x, p)
    s_inv = mod_inverse(s, p)
    m = (c2 * s_inv) % p
    return m

Practical Considerations

Message Size Limitation

• Plaintext m must satisfy 0 ≤ m < p
• For large messages:
  • Split into blocks
  • Or use hybrid encryption: Encrypt symmetric key with ElGamal, data with AES

Performance

Security Parameters (2025 Recommendations)

Use elliptic curve variant (EC-ElGamal) for better efficiency at equivalent security.

Variants and Extensions

1. ElGamal Digital Signature Scheme

Used in DSA and GOST R 34.10

Sign: (r, s) where r = gᵏ mod p, s = k⁻¹(H(m) + x r) mod (p-1)

2. Elliptic Curve ElGamal (EC-ElGamal)

• Operates over elliptic curve groups
• Much smaller keys (256-bit curve ≈ 3072-bit RSA)
• Basis for ECIES (Elliptic Curve Integrated Encryption Scheme)

3. Threshold ElGamal

Private key split among n parties; t needed to decrypt. Used in secure multiparty computation.

Security Analysis

Applications

Advantages vs Disadvantages

Conclusion

ElGamal encryption remains a fundamental algorithm in cryptographic education and research. Its elegant combination of number theory, randomness, and public-key principles makes it both powerful and instructive.

While pure ElGamal is rarely used directly in modern systems due to performance and malleability concerns, its ideas live on in DSA, ECIES, and post-quantum KEMs.

For developers and security engineers:

• Use EC-ElGamal or ECIES for real-world asymmetric encryption
• Prefer hybrid schemes (ElGamal + AES-GCM)
• Always validate inputs and use constant-time operations

References & Further Reading

1. Taher ElGamal, "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms", IEEE Transactions on Information Theory, 1985.
2. NIST Special Publication 800-56A: Recommendation for Pair-Wise Key Establishment Schemes
3. Handbook of Applied Cryptography – Menezes, van Oorschot, Vanstone (Chapter 8)