Chapter 29: The ElGamal Cryptosystem

Chapter 29: The ElGamal Cryptosystem#

29.1 Introduction: From Key Exchange to Public-Key Encryption#

In 1985, Taher ElGamal, an Egyptian-American cryptographer working at Hewlett-Packard, published a paper titled “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms” in the proceedings of CRYPTO ‘84. This paper demonstrated that the Diffie–Hellman key exchange (Chapter 28) could be transformed into a full public-key encryption scheme and a digital signature scheme.

The insight was elegant: if computing discrete logarithms in a cyclic group \(G = \langle g \rangle\) of order \(q\) is hard, then the tuple \((g, g^x, g^k)\) reveals nothing useful about \(g^{xk}\) to a passive adversary. This decisional Diffie–Hellman assumption (DDH) underpins the semantic security of ElGamal encryption.

The ElGamal cryptosystem has had enormous practical impact:

PGP/GPG: Phil Zimmermann’s Pretty Good Privacy adopted ElGamal encryption as one of its core public-key algorithms, making it a cornerstone of email encryption worldwide.
DSA: The Digital Signature Algorithm, standardized by NIST in 1991 (FIPS 186), is a variant of ElGamal’s signature scheme. DSA was the first digital signature standard adopted by the US government.
Homomorphic properties: ElGamal’s multiplicative homomorphism makes it useful in electronic voting protocols, mix-nets, and zero-knowledge proofs.
Randomized encryption: Unlike RSA (which is deterministic in its textbook form), ElGamal is inherently randomized – the same plaintext encrypts to different ciphertexts each time. This property is essential for achieving semantic security.

Tip

From key exchange to encryption. The conceptual leap from Diffie–Hellman to ElGamal is this: instead of both parties contributing ephemeral secrets, the sender chooses a random ephemeral key \(k\), computes a shared secret \(s = h^k\) (where \(h = g^x\) is the recipient’s public key), and uses \(s\) to mask the message. The recipient recovers \(s\) using their private key \(x\). This “one-sided Diffie–Hellman” is the heart of ElGamal.

29.2 Formal Definitions#

We work in the multiplicative group \(\mathbb{Z}_p^*\) where \(p\) is a large prime. In practice, one often works in a prime-order subgroup of \(\mathbb{Z}_p^*\) for security reasons, but the basic scheme operates as follows.

Definition 29.1 (ElGamal Key Generation)

Choose a large prime \(p\) and a generator \(g\) of the cyclic group \(\mathbb{Z}_p^* = \{1, 2, \ldots, p-1\}\) (or a generator of a prime-order subgroup of order \(q\)).
Choose a private key \(x\) uniformly at random from \(\{1, 2, \ldots, p-2\}\).
Compute the public key component \(h = g^x \bmod p\).
Public key: \((p, g, h)\). Private key: \(x\).

Definition 29.2 (ElGamal Encryption)

To encrypt a message \(m \in \{1, 2, \ldots, p-1\}\) using the recipient’s public key \((p, g, h)\):

Choose a random ephemeral key \(k\) uniformly from \(\{1, 2, \ldots, p-2\}\).
Compute:

\[ c_1 = g^k \bmod p \]

\[ c_2 = m \cdot h^k \bmod p\]
The ciphertext is the pair \((c_1, c_2)\).

The value \(s = h^k \bmod p\) is the shared secret (an ephemeral Diffie–Hellman shared value). The message is masked by multiplying with \(s\).

Definition 29.3 (ElGamal Decryption)

To decrypt a ciphertext \((c_1, c_2)\) using the private key \(x\):

Compute the shared secret: \(s = c_1^x \bmod p\).
Compute the modular inverse: \(s^{-1} \bmod p\).
Recover the message: \(m = c_2 \cdot s^{-1} \bmod p\).

Alternatively, one can compute \(s^{-1} = c_1^{p-1-x} \bmod p\) using Fermat’s little theorem, avoiding an explicit inverse computation.

Definition 29.4 (ElGamal Signature Scheme)

To sign a message \(m\) using the private key \(x\) and public parameters \((p, g, h)\):

Choose a random \(k\) with \(\gcd(k, p-1) = 1\).
Compute \(r = g^k \bmod p\).
Compute \(s = (m - x \cdot r) \cdot k^{-1} \bmod (p-1)\).
The signature is \((r, s)\).

Verification: Accept the signature if \(g^m \equiv h^r \cdot r^s \pmod{p}\).

Theorem 29.1 (ElGamal Correctness)

Encryption correctness. For any message \(m\), if \((c_1, c_2)\) is a valid ElGamal ciphertext, then decryption recovers \(m\):

\[ c_2 \cdot (c_1^x)^{-1} = m \cdot h^k \cdot (g^{kx})^{-1} = m \cdot g^{xk} \cdot g^{-xk} = m \pmod{p}\]

Signature correctness. For a valid signature \((r, s)\) on message \(m\):

\[ h^r \cdot r^s = g^{xr} \cdot g^{k \cdot (m - xr) \cdot k^{-1}} = g^{xr} \cdot g^{m - xr} = g^m \pmod{p}\]

Proof

Encryption: We have \(c_1 = g^k\) and \(c_2 = m \cdot h^k = m \cdot g^{xk}\). The decryptor computes \(s = c_1^x = g^{kx}\) and then \(c_2 \cdot s^{-1} = m \cdot g^{xk} \cdot g^{-xk} = m\). \(\blacksquare\)

Signature: We have \(r = g^k\) and \(s = (m - xr)k^{-1} \bmod (p-1)\), so \(ks = m - xr \bmod (p-1)\). Therefore \(h^r \cdot r^s = g^{xr} \cdot g^{ks} = g^{xr + ks} = g^{xr + m - xr} = g^m \pmod{p}\) by Fermat’s little theorem. \(\blacksquare\)

29.3 Security Foundations#

Semantic Security and Randomized Encryption

A public-key encryption scheme is semantically secure (IND-CPA) if no efficient adversary, given a public key and a ciphertext, can determine any partial information about the plaintext beyond its length.

ElGamal achieves semantic security under the Decisional Diffie–Hellman (DDH) assumption: given \((g, g^a, g^b, Z)\), it is computationally hard to determine whether \(Z = g^{ab}\) or \(Z\) is a random group element.

The crucial feature enabling semantic security is randomized encryption: each encryption uses a fresh random \(k\), so the same plaintext \(m\) produces a different ciphertext \((g^k, m \cdot h^k)\) each time. This is in stark contrast to textbook RSA, where \(\text{Enc}(m) = m^e \bmod n\) is deterministic.

Danger

Never reuse the ephemeral key \(k\). If two messages \(m_1, m_2\) are encrypted with the same \(k\), an attacker who knows \(m_1\) can recover \(m_2\):

\[ \frac{c_2'}{c_2} = \frac{m_2 \cdot h^k}{m_1 \cdot h^k} = \frac{m_2}{m_1} \pmod{p}\]

This is exactly the vulnerability that led to the PlayStation 3 ECDSA key compromise in 2010 – Sony reused the random nonce \(k\) in their signature scheme.

Ciphertext expansion. ElGamal has a 2:1 ciphertext expansion ratio: each message element \(m\) produces a ciphertext pair \((c_1, c_2)\), doubling the data size. This is the price paid for randomized encryption and is an inherent cost of any IND-CPA-secure scheme.

29.4 Implementation in NumPy#

We implement a complete ElGamal class supporting key generation, encryption, decryption, digital signatures, and signature verification. Since we work with modular arithmetic on integers that fit in 64 bits, we use Python’s built-in pow(base, exp, mod) for modular exponentiation (which uses fast binary exponentiation internally) and NumPy for array operations and random number generation.

import numpy as np
import math


def is_prime(n):
    """Deterministic primality test (trial division, sufficient for demo sizes)."""
    if n < 2:
        return False
    if n < 4:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True


def factor_trivial(n):
    """Return the prime factorization of n as a list of (prime, exponent) pairs."""
    factors = []
    d = 2
    while d * d <= n:
        if n % d == 0:
            exp = 0
            while n % d == 0:
                exp += 1
                n //= d
            factors.append((d, exp))
        d += 1
    if n > 1:
        factors.append((n, 1))
    return factors


def find_generator(p, rng=None):
    """
    Find a generator (primitive root) of Z_p^* for prime p.
    
    Uses the standard criterion: g is a generator of Z_p^* iff
    g^((p-1)/q) != 1 mod p for every prime factor q of p-1.
    """
    if rng is None:
        rng = np.random.default_rng()
    phi = p - 1
    prime_factors = [f[0] for f in factor_trivial(phi)]
    
    while True:
        g = int(rng.integers(2, p))
        if all(pow(g, phi // q, p) != 1 for q in prime_factors):
            return g


def extended_gcd(a, b):
    """Extended Euclidean algorithm: returns (gcd, x, y) s.t. a*x + b*y = gcd."""
    if a == 0:
        return b, 0, 1
    gcd, x1, y1 = extended_gcd(b % a, a)
    return gcd, y1 - (b // a) * x1, x1


def mod_inverse(a, m):
    """Compute modular inverse of a modulo m."""
    gcd, x, _ = extended_gcd(a % m, m)
    if gcd != 1:
        raise ValueError(f"No inverse: gcd({a}, {m}) = {gcd}")
    return x % m


class ElGamal:
    """
    ElGamal public-key cryptosystem over Z_p^*.
    
    Supports encryption, decryption, digital signatures, and verification.
    
    Parameters
    ----------
    bits : int
        Approximate bit-length of the prime p (for key generation).
    p : int, optional
        Use a specific prime instead of generating one.
    g : int, optional
        Use a specific generator.
    seed : int, optional
        Random seed for reproducibility.
    """
    
    def __init__(self, bits=32, p=None, g=None, seed=None):
        self.rng = np.random.default_rng(seed)
        
        if p is not None:
            assert is_prime(p), f"{p} is not prime"
            self.p = p
        else:
            self.p = self._generate_prime(bits)
        
        if g is not None:
            self.g = g
        else:
            self.g = find_generator(self.p, self.rng)
        
        # Key generation
        self.x = int(self.rng.integers(2, self.p - 1))  # private key
        self.h = pow(self.g, self.x, self.p)             # public key component
    
    def _generate_prime(self, bits):
        """Generate a random prime of approximately `bits` bits."""
        while True:
            # Generate odd candidate in the right range
            candidate = int(self.rng.integers(2**(bits-1), 2**bits))
            candidate |= 1  # make odd
            if is_prime(candidate):
                return candidate
    
    @property
    def public_key(self):
        """Return the public key tuple (p, g, h)."""
        return (self.p, self.g, self.h)
    
    @property
    def private_key(self):
        """Return the private key x."""
        return self.x
    
    def encrypt(self, m, k=None):
        """
        Encrypt a message m in {1, ..., p-1}.
        
        Parameters
        ----------
        m : int
            The plaintext message (must be in {1, ..., p-1}).
        k : int, optional
            Ephemeral key (random if not specified). WARNING: never reuse k.
        
        Returns
        -------
        tuple (c1, c2)
            The ciphertext pair.
        """
        assert 1 <= m < self.p, f"Message must be in [1, {self.p - 1}]"
        if k is None:
            k = int(self.rng.integers(2, self.p - 1))
        c1 = pow(self.g, k, self.p)
        s = pow(self.h, k, self.p)        # shared secret
        c2 = (m * s) % self.p
        return (c1, c2)
    
    def decrypt(self, c1, c2):
        """
        Decrypt a ciphertext (c1, c2) using the private key.
        
        Returns
        -------
        int
            The decrypted message.
        """
        s = pow(c1, self.x, self.p)                    # shared secret
        s_inv = pow(c1, self.p - 1 - self.x, self.p)  # s^(-1) via Fermat
        m = (c2 * s_inv) % self.p
        return m
    
    def sign(self, m):
        """
        Sign a message m using the ElGamal signature scheme.
        
        Parameters
        ----------
        m : int
            The message to sign (an integer mod p-1).
        
        Returns
        -------
        tuple (r, s)
            The signature.
        """
        p1 = self.p - 1
        while True:
            k = int(self.rng.integers(2, p1))
            if math.gcd(k, p1) == 1:
                break
        r = pow(self.g, k, self.p)
        k_inv = mod_inverse(k, p1)
        s = ((m - self.x * r) * k_inv) % p1
        return (r, s)
    
    def verify(self, m, r, s):
        """
        Verify an ElGamal signature.
        
        Returns True if g^m = h^r * r^s (mod p).
        """
        if not (0 < r < self.p):
            return False
        lhs = pow(self.g, m, self.p)
        rhs = (pow(self.h, r, self.p) * pow(r, s, self.p)) % self.p
        return lhs == rhs
    
    def __repr__(self):
        bits = self.p.bit_length()
        return f"ElGamal(p={self.p} [{bits}-bit], g={self.g}, h={self.h})"


# --- Quick demo ---
eg = ElGamal(bits=20, seed=42)
print(f"System:      {eg}")
print(f"Public key:  (p={eg.p}, g={eg.g}, h={eg.h})")
print(f"Private key: x={eg.x}")
print(f"Prime bits:  {eg.p.bit_length()}")

System:      ElGamal(p=889909 [20-bit], g=638490, h=767179)
Public key:  (p=889909, g=638490, h=767179)
Private key: x=699525
Prime bits:  20

29.5 Encryption and Decryption Demo#

We demonstrate the basic encrypt-decrypt cycle, verifying correctness on multiple messages.

import numpy as np

# Set up the ElGamal system
eg = ElGamal(bits=20, seed=42)
print(f"ElGamal system: p={eg.p}, g={eg.g}, h={eg.h}")
print(f"Private key: x={eg.x}")
print("=" * 70)

# Encrypt and decrypt several messages
rng = np.random.default_rng(123)
test_messages = [42, 1, eg.p - 1, 12345, int(rng.integers(2, eg.p - 1))]

print(f"{'Message':>10}  {'c1':>10}  {'c2':>10}  {'Decrypted':>10}  {'Correct':>8}")
print("-" * 58)

all_correct = True
for m in test_messages:
    c1, c2 = eg.encrypt(m)
    m_dec = eg.decrypt(c1, c2)
    ok = (m_dec == m)
    all_correct &= ok
    print(f"{m:>10}  {c1:>10}  {c2:>10}  {m_dec:>10}  {'YES' if ok else 'NO':>8}")

print("=" * 58)
print(f"All decryptions correct: {all_correct}")

ElGamal system: p=889909, g=638490, h=767179
Private key: x=699525
======================================================================
   Message          c1          c2   Decrypted   Correct
----------------------------------------------------------
        42      884781      804338          42       YES
         1      793008      857864           1       YES
    889908      491817      379038      889908       YES
     12345      105358      295850       12345       YES
     13742      328218      239283       13742       YES
==========================================================
All decryptions correct: True

29.6 Randomized Encryption: Same Plaintext, Different Ciphertexts#

A defining feature of ElGamal is that encryption is randomized: each call to encrypt uses a fresh ephemeral key \(k\), so the same plaintext maps to a different ciphertext every time. This contrasts sharply with textbook RSA, where \(\text{Enc}(m) = m^e \bmod n\) is deterministic.

Note

Randomized encryption is necessary for semantic security (IND-CPA). If an encryption scheme is deterministic, an attacker can encrypt candidate messages under the public key and compare with the target ciphertext – immediately breaking IND-CPA.

<>:35: SyntaxWarning: invalid escape sequence '\m'
<>:36: SyntaxWarning: invalid escape sequence '\m'
<>:35: SyntaxWarning: invalid escape sequence '\m'
<>:36: SyntaxWarning: invalid escape sequence '\m'
/var/folders/z7/wp7m8p7x1250jzvklw5z24mm0000gn/T/ipykernel_12332/4159638197.py:35: SyntaxWarning: invalid escape sequence '\m'
  ax.set_xlabel('$c_1 = g^k \\;\mathrm{mod}\; p$', fontsize=12)
/var/folders/z7/wp7m8p7x1250jzvklw5z24mm0000gn/T/ipykernel_12332/4159638197.py:36: SyntaxWarning: invalid escape sequence '\m'
  ax.set_ylabel('$c_2 = m \\cdot h^k \\;\mathrm{mod}\; p$', fontsize=12)

Encrypting the SAME message m=7777 twenty times:
  #          c1          c2   Decrypts to
------------------------------------------
    884781       25147          7777
    793008      850464          7777
    491817      489991          7777
    105358      165472          7777
    328218      741620          7777
    692088      683521          7777
    752900      127164          7777
    409574      294035          7777
    652893      809266          7777
    780255      389231          7777
    687349      151298          7777
    467614       90839          7777
    281198      647586          7777
    883385       14927          7777
    787364      162699          7777
    337426      208323          7777
    494099      402746          7777
    694310      830695          7777
    221506      663893          7777
    412530       12414          7777

Unique ciphertext pairs: 20 / 20
All decrypt correctly: True

../_images/8b258fe707dc911fd9231931767979ffcce340649f04cb05b860080c6f6f6570.png

29.7 Ciphertext Expansion#

ElGamal has a 2:1 ciphertext expansion ratio: each plaintext element \(m\) produces a ciphertext pair \((c_1, c_2)\) consisting of two group elements. This means the ciphertext is exactly twice the size of the plaintext (measured in group elements).

This expansion is an inherent cost of achieving randomized encryption in a group-based scheme. Let us visualize this ratio across different parameter sizes.

  Prime bits             p    msg bits     ct bits   Ratio
--------------------------------------------------------
          16         36451          16          32     2.0
          20        554209          20          40     2.0
          24      16264543          24          48     2.0
          28     222691277          28          56     2.0
          32    3984826973          32          64     2.0

../_images/ea3d586508562e306a5cb4cb434269bd60b2475d605f8b6e3a9825f037c13b46.png

29.8 Ciphertext Malleability: The Homomorphic Property#

ElGamal has a remarkable algebraic property: it is multiplicatively homomorphic. Given two ciphertexts that encrypt \(m_1\) and \(m_2\) respectively, one can compute a ciphertext that encrypts \(m_1 \cdot m_2\) without knowing the private key or the individual plaintexts.

Specifically, if \((c_1, c_2) = (g^{k_1}, m_1 \cdot h^{k_1})\) and \((c_1', c_2') = (g^{k_2}, m_2 \cdot h^{k_2})\), then:

\[ \big(c_1 \cdot c_1' \bmod p,\; c_2 \cdot c_2' \bmod p\big) = \big(g^{k_1+k_2},\; m_1 m_2 \cdot h^{k_1+k_2}\big)\]

This is a valid encryption of \(m_1 \cdot m_2\) under ephemeral key \(k_1 + k_2\).

Warning

Malleability is a double-edged sword. While the homomorphic property enables useful applications (electronic voting, secure computation), it also means that ElGamal is not CCA-secure (IND-CCA2). An attacker can manipulate ciphertexts in meaningful ways without detection. Real-world systems must add integrity checks (e.g., the Cramer–Shoup cryptosystem).

import numpy as np

# Demonstrate the multiplicative homomorphic property
eg = ElGamal(bits=20, seed=42)
p = eg.p

m1 = 123
m2 = 456
m_product = (m1 * m2) % p

print(f"ElGamal system: p={p}")
print(f"m1 = {m1}")
print(f"m2 = {m2}")
print(f"m1 * m2 mod p = {m_product}")
print("=" * 50)

# Encrypt m1 and m2 separately
(c1_a, c2_a) = eg.encrypt(m1)
(c1_b, c2_b) = eg.encrypt(m2)

print(f"Enc(m1) = ({c1_a}, {c2_a})")
print(f"Enc(m2) = ({c1_b}, {c2_b})")

# Homomorphic multiplication: multiply ciphertexts component-wise
c1_prod = (c1_a * c1_b) % p
c2_prod = (c2_a * c2_b) % p

print(f"\nHomomorphic product: ({c1_prod}, {c2_prod})")

# Decrypt the product ciphertext
m_dec_product = eg.decrypt(c1_prod, c2_prod)
print(f"Decrypted product:  {m_dec_product}")
print(f"Expected (m1*m2 mod p): {m_product}")
print(f"Homomorphic property holds: {m_dec_product == m_product}")

# Extended demo: chain of multiplications
print("\n" + "=" * 50)
print("Chained homomorphic operations:")
messages = [7, 11, 13, 17]
running_product = 1
running_c1 = 1
running_c2 = 1

for i, m in enumerate(messages):
    c1, c2 = eg.encrypt(m)
    running_c1 = (running_c1 * c1) % p
    running_c2 = (running_c2 * c2) % p
    running_product = (running_product * m) % p
    dec = eg.decrypt(running_c1, running_c2)
    print(f"  After m={m:>3}: product={running_product:>8}, "
          f"decrypted={dec:>8}, match={dec == running_product}")

ElGamal system: p=889909
m1 = 123
m2 = 456
m1 * m2 mod p = 56088
==================================================
Enc(m1) = (884781, 830003)
Enc(m2) = (793008, 515933)

Homomorphic product: (339106, 837090)
Decrypted product:  56088
Expected (m1*m2 mod p): 56088
Homomorphic property holds: True

==================================================
Chained homomorphic operations:
  After m=  7: product=       7, decrypted=       7, match=True
  After m= 11: product=      77, decrypted=      77, match=True
  After m= 13: product=    1001, decrypted=    1001, match=True
  After m= 17: product=   17017, decrypted=   17017, match=True

29.9 Re-Randomization#

Because ElGamal is randomized, we can re-randomize a ciphertext: given an encryption of \(m\), produce a fresh-looking encryption of the same \(m\) without knowing \(m\) or the private key.

To re-randomize \((c_1, c_2) = (g^k, m \cdot h^k)\), choose a fresh random \(k'\) and compute:

\[ \big(c_1 \cdot g^{k'} \bmod p,\; c_2 \cdot h^{k'} \bmod p\big) = \big(g^{k+k'},\; m \cdot h^{k+k'}\big)\]

This is a valid encryption of the same \(m\) under a new ephemeral key \(k + k'\). Re-randomization is essential in mix-nets and electronic voting protocols.

import numpy as np

eg = ElGamal(bits=20, seed=42)
p, g, h = eg.public_key
rng = np.random.default_rng(999)

message = 31415
c1_orig, c2_orig = eg.encrypt(message)

print(f"Original message: {message}")
print(f"Original ciphertext: ({c1_orig}, {c2_orig})")
print(f"Decrypts to: {eg.decrypt(c1_orig, c2_orig)}")
print("\nRe-randomizing 10 times (without knowing the message):")
print(f"{'#':>3}  {'c1':>10}  {'c2':>10}  {'Decrypted':>10}  {'Correct':>8}")
print("-" * 48)

for i in range(10):
    k_prime = int(rng.integers(2, p - 1))
    c1_new = (c1_orig * pow(g, k_prime, p)) % p
    c2_new = (c2_orig * pow(h, k_prime, p)) % p
    m_dec = eg.decrypt(c1_new, c2_new)
    print(f"{i+1:>3}  {c1_new:>10}  {c2_new:>10}  {m_dec:>10}  "
          f"{'YES' if m_dec == message else 'NO':>8}")

print(f"\nAll re-randomized ciphertexts decrypt to the original message.")

Original message: 31415
Original ciphertext: (884781, 725215)
Decrypts to: 31415

Re-randomizing 10 times (without knowing the message):
  #          c1          c2   Decrypted   Correct
------------------------------------------------
  1      734011      167940       31415       YES
  2      282138      445032       31415       YES
  3       35665      236873       31415       YES
  4      247876      609647       31415       YES
  5      501328      373154       31415       YES
  6      298202       21634       31415       YES
  7      100846      720140       31415       YES
  8      733964      791750       31415       YES
  9      247659      120564       31415       YES
 10      418882      397806       31415       YES

All re-randomized ciphertexts decrypt to the original message.

29.10 Digital Signatures#

ElGamal’s signature scheme provides authentication and non-repudiation. The signer uses their private key \(x\) to produce a signature \((r, s)\) that anyone can verify using the public key \((p, g, h)\).

import numpy as np

eg = ElGamal(bits=20, seed=42)
print(f"ElGamal system: p={eg.p}, g={eg.g}, h={eg.h}")
print(f"Private key: x={eg.x}")
print("=" * 60)

# Sign several messages
messages_to_sign = [42, 1000, 99999, 7, 314]

print(f"\n{'Message':>10}  {'r':>10}  {'s':>10}  {'Valid':>6}")
print("-" * 42)

signatures = []
for m in messages_to_sign:
    r, s = eg.sign(m)
    valid = eg.verify(m, r, s)
    signatures.append((m, r, s))
    print(f"{m:>10}  {r:>10}  {s:>10}  {'YES' if valid else 'NO':>6}")

# Demonstrate that a tampered message fails verification
print("\n--- Tampered message verification ---")
m_orig, r_orig, s_orig = signatures[0]
m_tampered = m_orig + 1
valid_tampered = eg.verify(m_tampered, r_orig, s_orig)
print(f"Original message: {m_orig}, Signature valid: {eg.verify(m_orig, r_orig, s_orig)}")
print(f"Tampered message: {m_tampered}, Signature valid: {valid_tampered}")

# Demonstrate that a forged signature fails
print("\n--- Forged signature verification ---")
r_forged = (r_orig + 1) % eg.p
valid_forged = eg.verify(m_orig, r_forged, s_orig)
print(f"Original r={r_orig}: valid={eg.verify(m_orig, r_orig, s_orig)}")
print(f"Forged   r={r_forged}: valid={valid_forged}")

ElGamal system: p=889909, g=638490, h=767179
Private key: x=699525
============================================================

   Message           r           s   Valid
------------------------------------------
        42      884781       73761     YES
      1000      793008      579248     YES
     99999      692088      754167     YES
         7      409574      438455     YES
       314      780255      639235     YES

--- Tampered message verification ---
Original message: 42, Signature valid: True
Tampered message: 43, Signature valid: False

--- Forged signature verification ---
Original r=884781: valid=True
Forged   r=884782: valid=False

29.11 Timing Comparison: ElGamal vs. RSA#

We compare the computational cost of ElGamal encryption/decryption against a simple textbook RSA implementation. Both schemes rely on modular exponentiation, but ElGamal requires two exponentiations per encryption (computing \(g^k\) and \(h^k\)) plus a multiplication, while RSA requires one exponentiation.

Show code cell source Hide code cell source

import numpy as np
import matplotlib.pyplot as plt
import math
import time


class SimpleRSA:
    """Minimal textbook RSA for timing comparison."""
    def __init__(self, bits=32, seed=None):
        rng = np.random.default_rng(seed)
        # Generate two primes
        self.p = self._gen_prime(bits // 2, rng)
        self.q = self._gen_prime(bits // 2, rng)
        while self.q == self.p:
            self.q = self._gen_prime(bits // 2, rng)
        self.n = self.p * self.q
        phi = (self.p - 1) * (self.q - 1)
        self.e = 65537
        while math.gcd(self.e, phi) != 1:
            self.e += 2
        self.d = pow(self.e, -1, phi)  # Python 3.8+ modular inverse
    
    @staticmethod
    def _gen_prime(bits, rng):
        while True:
            c = int(rng.integers(2**(bits-1), 2**bits)) | 1
            if is_prime(c):
                return c
    
    def encrypt(self, m):
        return pow(m, self.e, self.n)
    
    def decrypt(self, c):
        return pow(c, self.d, self.n)


# Timing comparison across different bit sizes
bit_sizes = [16, 20, 24, 28, 32]
n_trials = 200
rng_timing = np.random.default_rng(777)

eg_enc_times = []
eg_dec_times = []
rsa_enc_times = []
rsa_dec_times = []

for bits in bit_sizes:
    eg_sys = ElGamal(bits=bits, seed=200 + bits)
    rsa_sys = SimpleRSA(bits=bits, seed=300 + bits)
    
    msgs_eg = [int(rng_timing.integers(2, eg_sys.p - 1)) for _ in range(n_trials)]
    msgs_rsa = [int(rng_timing.integers(2, rsa_sys.n - 1)) for _ in range(n_trials)]
    
    # Time ElGamal encryption
    t0 = time.perf_counter()
    cts_eg = [eg_sys.encrypt(m) for m in msgs_eg]
    eg_enc_times.append((time.perf_counter() - t0) / n_trials * 1e6)
    
    # Time ElGamal decryption
    t0 = time.perf_counter()
    _ = [eg_sys.decrypt(c1, c2) for c1, c2 in cts_eg]
    eg_dec_times.append((time.perf_counter() - t0) / n_trials * 1e6)
    
    # Time RSA encryption
    t0 = time.perf_counter()
    cts_rsa = [rsa_sys.encrypt(m) for m in msgs_rsa]
    rsa_enc_times.append((time.perf_counter() - t0) / n_trials * 1e6)
    
    # Time RSA decryption
    t0 = time.perf_counter()
    _ = [rsa_sys.decrypt(c) for c in cts_rsa]
    rsa_dec_times.append((time.perf_counter() - t0) / n_trials * 1e6)

# Print results
print(f"{'Bits':>6}  {'EG Enc (us)':>12}  {'EG Dec (us)':>12}  "
      f"{'RSA Enc (us)':>13}  {'RSA Dec (us)':>13}")
print("-" * 62)
for i, bits in enumerate(bit_sizes):
    print(f"{bits:>6}  {float(eg_enc_times[i]):>12.1f}  {float(eg_dec_times[i]):>12.1f}  "
          f"{float(rsa_enc_times[i]):>13.1f}  {float(rsa_dec_times[i]):>13.1f}")

# Plot
fig, axes = plt.subplots(1, 2, figsize=(14, 5))
x = np.arange(len(bit_sizes))
width = 0.35

# Encryption timing
axes[0].bar(x - width/2, eg_enc_times, width, label='ElGamal', color='steelblue', alpha=0.8)
axes[0].bar(x + width/2, rsa_enc_times, width, label='RSA', color='darkorange', alpha=0.8)
axes[0].set_xlabel('Prime size (bits)', fontsize=12)
axes[0].set_ylabel('Time per operation (\u00b5s)', fontsize=12)
axes[0].set_title('Encryption Time', fontsize=13, fontweight='bold')
axes[0].set_xticks(x)
axes[0].set_xticklabels(bit_sizes)
axes[0].legend(fontsize=11)
axes[0].grid(axis='y', alpha=0.3)

# Decryption timing
axes[1].bar(x - width/2, eg_dec_times, width, label='ElGamal', color='steelblue', alpha=0.8)
axes[1].bar(x + width/2, rsa_dec_times, width, label='RSA', color='darkorange', alpha=0.8)
axes[1].set_xlabel('Prime size (bits)', fontsize=12)
axes[1].set_ylabel('Time per operation (\u00b5s)', fontsize=12)
axes[1].set_title('Decryption Time', fontsize=13, fontweight='bold')
axes[1].set_xticks(x)
axes[1].set_xticklabels(bit_sizes)
axes[1].legend(fontsize=11)
axes[1].grid(axis='y', alpha=0.3)

plt.tight_layout()
plt.savefig('elgamal_vs_rsa_timing.png', dpi=150, bbox_inches='tight')
plt.show()

print("\nNote: ElGamal encryption requires 2 modular exponentiations vs. 1 for RSA.")
print("RSA decryption uses a large private exponent d, making it slower than encryption.")

  Bits   EG Enc (us)   EG Dec (us)   RSA Enc (us)   RSA Dec (us)
--------------------------------------------------------------
         3.0           1.5            0.6            0.8
         3.2           1.6            0.6            0.8
         3.5           2.0            0.6            1.0
         3.8           2.2            0.6            1.2
        10.3           8.9            1.6            3.9

../_images/5e11171d963f36b4c3c86ab7629980adc72dfc354089494aadda751585509c19.png

Note: ElGamal encryption requires 2 modular exponentiations vs. 1 for RSA.
RSA decryption uses a large private exponent d, making it slower than encryption.

29.12 The Danger of Ephemeral Key Reuse#

We now demonstrate concretely why reusing the ephemeral key \(k\) is catastrophic. If two messages \(m_1, m_2\) are encrypted with the same \(k\), the shared secret \(s = h^k\) is identical in both ciphertexts, allowing an attacker who knows one plaintext to recover the other.

import numpy as np
import math

eg = ElGamal(bits=20, seed=42)
p = eg.p

m1 = 12345
m2 = 67890

# DANGEROUS: encrypt both messages with the same k
k_reused = 9999
c1_a, c2_a = eg.encrypt(m1, k=k_reused)
c1_b, c2_b = eg.encrypt(m2, k=k_reused)

print("=== Ephemeral Key Reuse Attack ===")
print(f"p = {p}")
print(f"m1 = {m1}, Enc(m1) = ({c1_a}, {c2_a})")
print(f"m2 = {m2}, Enc(m2) = ({c1_b}, {c2_b})")
print(f"Note: c1 values are identical (same k): c1_a == c1_b = {c1_a == c1_b}")

# Attack: suppose the attacker knows m1 and both ciphertexts
print("\n--- Attacker knows m1 and sees both ciphertexts ---")
# c2_a = m1 * h^k mod p  -->  h^k = c2_a * m1^(-1) mod p
# c2_b = m2 * h^k mod p  -->  m2 = c2_b * (h^k)^(-1) mod p
# Combined: m2 = c2_b * m1 * c2_a^(-1) mod p

c2_a_inv = pow(c2_a, p - 2, p)  # Fermat inverse
m2_recovered = (c2_b * m1 * c2_a_inv) % p

print(f"Recovered m2 = c2_b * m1 * c2_a^(-1) mod p = {m2_recovered}")
print(f"Actual m2 = {m2}")
print(f"Attack successful: {m2_recovered == m2}")

print("\n--- Lesson: NEVER reuse the ephemeral key k ---")

=== Ephemeral Key Reuse Attack ===
p = 889909
m1 = 12345, Enc(m1) = (629737, 257848)
m2 = 67890, Enc(m2) = (629737, 675155)
Note: c1 values are identical (same k): c1_a == c1_b = True

--- Attacker knows m1 and sees both ciphertexts ---
Recovered m2 = c2_b * m1 * c2_a^(-1) mod p = 67890
Actual m2 = 67890
Attack successful: True

--- Lesson: NEVER reuse the ephemeral key k ---

29.13 Visualizing the Group Structure#

To build intuition about why ElGamal works, let us visualize the structure of \(\mathbb{Z}_p^*\) for a small prime \(p\). We plot the discrete powers \(g^0, g^1, g^2, \ldots, g^{p-2}\) to see how the generator cycles through all elements.

<>:17: SyntaxWarning: invalid escape sequence '\%'
<>:17: SyntaxWarning: invalid escape sequence '\%'
/var/folders/z7/wp7m8p7x1250jzvklw5z24mm0000gn/T/ipykernel_12332/3581824236.py:17: SyntaxWarning: invalid escape sequence '\%'
  axes[0].set_ylabel(f'$g^k \% {p_small}$', fontsize=12)

../_images/e230ee5a3a50dc8a2b09f90d00baba70ff14f8814f89bcd973b0e5412eb99703.png

Generator g = 45, prime p = 47, group order = 46
g generates all 46 elements: True

29.14 Distribution of Ciphertext Components#

For a secure ElGamal system, the ciphertext components \((c_1, c_2)\) should appear uniformly distributed over \(\mathbb{Z}_p^*\). Let us verify this empirically by encrypting many random messages and examining the distribution of \(c_1\) and \(c_2\) values.

<>:41: SyntaxWarning: invalid escape sequence '\c'
<>:41: SyntaxWarning: invalid escape sequence '\c'
/var/folders/z7/wp7m8p7x1250jzvklw5z24mm0000gn/T/ipykernel_12332/2855804097.py:41: SyntaxWarning: invalid escape sequence '\c'
  axes[1].set_title('Distribution of $c_2 = m \cdot  h^k$', fontsize=12, fontweight='bold')

../_images/a2bd7a095013edb7cfc8654cd84dd8396bc0ff0e3e6240b93fcfd5b18cbe1469.png

p = 58129, n_samples = 2000
c1 range: [60, 58116] (expected [1, 58128])
c2 range: [62, 58122] (expected [1, 58128])

29.15 Exercises#

Exercise 29.1: Manual ElGamal#

Let \(p = 23\), \(g = 5\), and the private key \(x = 7\). Compute the public key \(h\). Then encrypt the message \(m = 10\) using ephemeral key \(k = 3\). Verify by decrypting.

Hint

\(h = 5^7 \bmod 23 = 78125 \bmod 23 = 17\). Encryption: \(c_1 = 5^3 \bmod 23 = 10\), \(s = 17^3 \bmod 23 = 4913 \bmod 23 = 15\), \(c_2 = 10 \cdot 15 \bmod 23 = 150 \bmod 23 = 12\). Decryption: \(s = c_1^x = 10^7 \bmod 23 = 10000000 \bmod 23 = 15\), \(s^{-1} = 15^{-1} \bmod 23\). Since \(15 \cdot 2 = 30 \equiv 7\) and \(15 \cdot 17 = 255 \equiv 2 \pmod{23}\)… use Fermat: \(s^{-1} = 15^{21} \bmod 23\). Or note \(c_1^{p-1-x} = 10^{15} \bmod 23\). Then \(m = c_2 \cdot s^{-1} \bmod 23 = 10\).

Exercise 29.2: Homomorphic Voting#

Design a simple yes/no voting protocol using ElGamal’s homomorphic property. Encode “yes” as \(g^1\) and “no” as \(g^0 = 1\). If there are \(n\) voters and \(t\) vote yes, what does the product of all ciphertexts decrypt to? How do you recover \(t\) from \(g^t\)?

Hint

Each voter encrypts \(g^{v_i}\) where \(v_i \in \{0, 1\}\). The homomorphic product decrypts to \(g^{v_1} \cdot g^{v_2} \cdots g^{v_n} = g^{v_1 + v_2 + \cdots + v_n} = g^t\). To recover \(t\), compute \(g, g^2, g^3, \ldots\) until finding \(g^t\). This is feasible since \(t \leq n\) and \(n\) is small (number of voters). This approach is called “exponential ElGamal” and is used in real e-voting systems like Helios.

Exercise 29.3: Proving the DDH Separation#

Show that the Computational Diffie–Hellman (CDH) problem does not immediately imply the Decisional Diffie–Hellman (DDH) problem. Give an example of a group where CDH is believed hard but DDH is easy.

Hint

Consider a group equipped with a bilinear pairing \(e: G \times G \to G_T\). Given \((g, g^a, g^b, Z)\), one can check whether \(Z = g^{ab}\) by testing if \(e(g^a, g^b) = e(g, Z)\). This breaks DDH while CDH may still be hard. Supersingular elliptic curves provide concrete examples. This is why ElGamal must be instantiated in groups where DDH holds – typically prime-order subgroups of \(\mathbb{Z}_p^*\) or suitable elliptic curves.

Exercise 29.4: Nonce Reuse Attack on Signatures#

Suppose an ElGamal signer uses the same nonce \(k\) to sign two different messages \(m_1 \neq m_2\), producing signatures \((r, s_1)\) and \((r, s_2)\) (same \(r\) since \(r = g^k\)). Show how to recover the private key \(x\) from these two signatures.

Hint

From the signing equation: \(s_1 = (m_1 - x \cdot r) \cdot k^{-1} \bmod (p-1)\) and \(s_2 = (m_2 - x \cdot r) \cdot k^{-1} \bmod (p-1)\). Subtracting: \(s_1 - s_2 = (m_1 - m_2) \cdot k^{-1} \bmod (p-1)\), so \(k = (m_1 - m_2) \cdot (s_1 - s_2)^{-1} \bmod (p-1)\) (when the inverse exists). Then from the first equation: \(x = (m_1 - k \cdot s_1) \cdot r^{-1} \bmod (p-1)\). This is essentially the attack used against Sony’s PS3 ECDSA implementation.

Exercise 29.5 (Challenge): CCA Attack via Malleability#

An oracle \(\mathcal{O}\) decrypts any ciphertext except the target \((c_1^*, c_2^*)\). Given a target ciphertext \((c_1^*, c_2^*)\) that encrypts an unknown message \(m^*\), use ElGamal’s homomorphic property to construct a different ciphertext that the oracle will decrypt, and use the oracle’s response to recover \(m^*\).

Hint

Choose any known message \(m' \neq 1\) and encrypt it: \((c_1', c_2') = (g^{k'}, m' \cdot h^{k'})\). Compute the modified ciphertext \((c_1^* \cdot c_1', c_2^* \cdot c_2')\). This is different from \((c_1^*, c_2^*)\), so the oracle will decrypt it, returning \(m^* \cdot m' \bmod p\). Then \(m^* = (m^* \cdot m') \cdot (m')^{-1} \bmod p\). This demonstrates that ElGamal is not IND-CCA2 secure.

29.16 Summary and Key Takeaways#

In this chapter, we have studied the ElGamal cryptosystem, a public-key encryption and signature scheme based on the discrete logarithm problem:

From Diffie–Hellman to encryption. ElGamal transforms the DH key exchange into a full public-key cryptosystem by having the sender perform a “one-sided” key exchange with a fresh ephemeral key \(k\) for each message.
Randomized encryption. Each encryption uses a fresh random \(k\), so the same plaintext encrypts to different ciphertexts. This is essential for semantic security (IND-CPA) under the DDH assumption.
Ciphertext expansion. The 2:1 expansion ratio (one plaintext element becomes two ciphertext elements) is the price of randomization.
Multiplicative homomorphism. The component-wise product of two ciphertexts decrypts to the product of the plaintexts. This enables applications in e-voting and secure computation, but also means ElGamal is malleable (not CCA-secure).
Digital signatures. ElGamal’s signature scheme (and its DSA variant) provides authentication via the discrete log problem. Nonce reuse is catastrophic.
Ephemeral key discipline. Reusing \(k\) completely breaks both the encryption scheme (known-plaintext recovery) and the signature scheme (private key recovery).

Tip

The power of randomization. ElGamal demonstrates a fundamental insight in modern cryptography: introducing randomness into the encryption process is not a luxury but a necessity. Deterministic public-key encryption can never be semantically secure, because the attacker can always encrypt candidate messages under the public key and compare. The ephemeral key \(k\) in ElGamal – and analogous randomness in OAEP-padded RSA, lattice-based schemes, etc. – is what makes public-key encryption meaningful.

What comes next: In Chapter 30, we explore elliptic curve cryptography, which instantiates the discrete logarithm framework (and hence ElGamal) over elliptic curve groups, achieving the same security with dramatically smaller key sizes.

29.17 References#

ElGamal, T. (1985). “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms.” IEEE Transactions on Information Theory, 31(4), 469–472. The original paper presenting both the encryption scheme and the signature scheme. Remarkably concise at only 4 pages.
Diffie, W. and Hellman, M. (1976). “New Directions in Cryptography.” IEEE Transactions on Information Theory, 22(6), 644–654. The foundational paper that introduced public-key cryptography and the Diffie–Hellman key exchange, upon which ElGamal is built.
Tsiounis, Y. and Yung, M. (1998). “On the Security of ElGamal Based Encryption.” Public Key Cryptography (PKC ‘98), Springer LNCS 1431, 117–134. Formal security analysis showing ElGamal is IND-CPA secure under the DDH assumption.
Cramer, R. and Shoup, V. (1998). “A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack.” CRYPTO ‘98, Springer LNCS 1462, 13–25. Extends ElGamal to achieve IND-CCA2 security by adding hash-based integrity checks.
Menezes, A., van Oorschot, P., and Vanstone, S. (1996). Handbook of Applied Cryptography. CRC Press. Chapter 8. Comprehensive reference covering ElGamal encryption, signatures, and their variants in practical detail.
NIST FIPS 186-4 (2013). Digital Signature Standard (DSS). The US federal standard for digital signatures, which includes DSA – a variant of ElGamal’s signature scheme.

Chapter 29: The ElGamal Cryptosystem

Contents

Chapter 29: The ElGamal Cryptosystem#

29.1 Introduction: From Key Exchange to Public-Key Encryption#

29.2 Formal Definitions#

29.3 Security Foundations#

29.4 Implementation in NumPy#

29.5 Encryption and Decryption Demo#

29.6 Randomized Encryption: Same Plaintext, Different Ciphertexts#

29.7 Ciphertext Expansion#

29.8 Ciphertext Malleability: The Homomorphic Property#

29.9 Re-Randomization#

29.10 Digital Signatures#

29.11 Timing Comparison: ElGamal vs. RSA#

29.12 The Danger of Ephemeral Key Reuse#

29.13 Visualizing the Group Structure#

29.14 Distribution of Ciphertext Components#

29.15 Exercises#

Exercise 29.1: Manual ElGamal#

Exercise 29.2: Homomorphic Voting#

Exercise 29.3: Proving the DDH Separation#

Exercise 29.4: Nonce Reuse Attack on Signatures#

Exercise 29.5 (Challenge): CCA Attack via Malleability#

29.16 Summary and Key Takeaways#

29.17 References#