Breaking ElGamal with Baby-Step Giant-Step

Breaking ElGamal with Baby-Step Giant-Step

Introduction

ElGamal builds public-key encryption directly on top of Diffie-Hellman’s own math. Its public key, y = g^x mod p, has exactly the same shape as a Diffie-Hellman public value. That’s not a coincidence. The baby-step giant-step breaker built for Diffie-Hellman needs no new theory here. It points at ElGamal just as easily. This post reuses that exact technique. It recovers ElGamal’s private key from a small prime, then decrypts a captured ciphertext.

Table of Contents

• Why ElGamal Inherits DH’s Weakness
• The Attack: Same Algorithm, Different Target
• A Worked Example
• Python Implementation
• Interactive Visualizer
• ElGamal vs. Diffie-Hellman: One Breaker, Two Targets
• Limitations of This Attack
• FAQ
• References

Why ElGamal Inherits DH’s Weakness

The base ElGamal guide generates a key pair the same way Diffie-Hellman does. Pick a private x, publish y = g^x mod p. Encryption and decryption build on that key. But the key itself is just a discrete logarithm instance. It’s identical in shape to the one Diffie-Hellman exposes. Whatever recovers a Diffie-Hellman exponent from a public value recovers an ElGamal key too. No changes to the underlying math are needed.

That’s exactly what makes this post short. The DH breaker already built, explained, and verified baby-step giant-step in detail. Here, the only new work runs that same algorithm against y instead of A. The recovered private key then feeds into ElGamal’s own decryption formula. The base guide already documents it. Breaking the key and breaking the ciphertext are two separate steps. This post covers both.

One assumption carries over too. The search recovers a discrete log inside the subgroup g generates. It needs y to actually sit in ⟨g⟩. That’s true whenever g is a full generator. It’s exactly the setup this post and the DH breaker both use.

The Attack: Same Algorithm, Different Target

Given a prime p, a generator g, a public key y = g^x mod p, and a captured (c₁, c₂):

1. Run baby-step giant-step against y. This is exactly the DH breaker’s algorithm, substituting y for A. The same algorithm works against any public value shaped like g^secret. Build a baby-step table of gʲ mod p. Then take giant steps from y until one lands in that table. The match gives x = i·m + j.
2. Recompute the shared secret ElGamal used to mask the message. s = c₁ˣ mod p. This is the exact value the sender’s yᵏ produced, now rebuilt from the recovered x instead.
3. Invert s. s⁻¹ mod p, via the Extended Euclidean Algorithm.
4. Recover the message. m = c₂ · s⁻¹ mod p. That’s the base guide’s formula, run here by an attacker, not the key’s owner.

Nothing here is new cryptanalysis. It’s the DH breaker’s discrete-log attack, followed by the base ElGamal guide’s own decryption steps. The only thing that changed is who’s running them.

A Worked Example

The visualizer’s defaults reuse p = 104729 and g = 12 from the DH breaker’s worked example. This time there’s a fresh ElGamal key pair: x = 33333, y = 21016.

1. Baby-step giant-step recovers x. Same table, same search as the DH breaker, just pointed at y instead of A. It converges on x = 33333.
2. A ciphertext was captured in transit: (c₁, c₂) = (2583, 73313). It was built the ordinary way: c₁ = gᵏ mod p, c₂ = m · yᵏ mod p. The one-time k = 7777 is something the attacker never needs to know.
3. Recompute the shared secret. s = c₁ˣ mod p = 2583³³³³³ mod 104729. Working that out gives s = 61997. That’s the same value yᵏ produced during encryption, since yᵏ = (gˣ)ᵏ = (gᵏ)ˣ = c₁ˣ. Recomputing it from x erases k just as cleanly as knowing k would have.
4. Invert it. s⁻¹ mod 104729 = 43392.
5. Recover the message. m = c₂ · s⁻¹ mod p = 73313 × 43392 mod 104729 = 54321.

The private key and the message both fall out. Nothing was used beyond what’s already public: p, g, y, and the intercepted ciphertext.

Recovering x isn’t a one-shot trick either. The same private key decrypts every ciphertext anyone ever sends to y. Recovering x is a one-time, offline cost. Decrypting further traffic is free from then on.

Python Implementation

The interactive visualizer above runs this exact two-stage attack in JavaScript. Baby-step giant-step, then ordinary ElGamal decryption. Here’s the same attack in Python.

Key Features

• bsgs is copied verbatim from the DH breaker’s own implementation. No adaptation was needed. A discrete logarithm stays a discrete logarithm, no matter which protocol built the key.
• The baby-step table keeps the smallest j on a collision, via if e not in table. With g a full generator, no two baby steps ever collide anyway. A non-generator g would need the search scoped to its actual subgroup order instead.
• Decryption reuses the base ElGamal guide’s formula, fed x from the attack, not the owner.
• Never needs k, the sender’s one-time random value. The attack recovers the message without ever learning what k was.
• Raises instead of failing silently, if either bsgs or mod_inverse comes back empty. That beats letting a stray None propagate into later arithmetic and fail somewhere confusing.

Code

# elgamal_breaker.py
#
# Breaks ElGamal by treating its public key y = g^x mod p as exactly
# what it is: a Diffie-Hellman-style discrete logarithm instance. Baby-
# step giant-step recovers x, and ordinary ElGamal decryption, run by
# the attacker, finishes the job on any captured ciphertext.

import math


def egcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = egcd(b, a % b)
    return g, y, x - (a // b) * y


def mod_inverse(a, m):
    g, x, _ = egcd(a % m, m)
    if g != 1:
        return None
    return x % m


def bsgs(g, target, p):
    m = math.isqrt(p - 1) + 1
    table = {}
    e = 1
    for j in range(m):
        if e not in table:  # smallest j wins on a collision; g is a generator here, so none occur
            table[e] = j
        e = (e * g) % p

    g_inv_m = mod_inverse(pow(g, m, p), p)
    gamma = target
    for i in range(m):
        if gamma in table:
            return i * m + table[gamma]
        gamma = (gamma * g_inv_m) % p
    return None


def elgamal_decrypt(c1, c2, x, p):
    s = pow(c1, x, p)
    s_inv = mod_inverse(s, p)
    if s_inv is None:
        raise ValueError("no modular inverse for s: c1 and p must be coprime")
    return (c2 * s_inv) % p


if __name__ == '__main__':
    p, g, y = 104729, 12, 21016
    c1, c2 = 2583, 73313

    x = bsgs(g, y, p)
    if x is None:
        raise ValueError("discrete log not found: is y actually a power of g mod p?")
    print(f"Recovered private key x = {x}")
    assert pow(g, x, p) == y

    message = elgamal_decrypt(c1, c2, x, p)
    print(f"Decrypted message: {message}")

Running this against the same values as the visualizer produces:

Recovered private key x = 33333
Decrypted message: 54321

This matches the visualizer’s own result exactly. It matches the worked example above, step for step.

For Fun: The Whole Attack in 5 Lines

Same spirit as this site’s other golfed bonus sections. Not for learning the algorithm from. This version finds x and decrypts inside one generator expression. A walrus operator keeps the giant-step value alive across it.

import math
p,g,y,c1,c2=104729,12,21016,2583,73313
m=math.isqrt(p-1)+1; T={pow(g,j,p):j for j in range(m)}; inv=pow(g,-m,p); x=next(i*m+T[G] for i in range(m) if (G:=y if i==0 else G*inv%p) in T)
print(f"Recovered private key x = {x}"); assert pow(g,x,p)==y
print(f"Decrypted message: {(c2*pow(pow(c1,x,p),-1,p))%p}")

Verified to produce the identical Recovered private key x = 33333 and Decrypted message: 54321. The walrus assignment G := y if i==0 else G*inv%p rebuilds the giant-step chain on every call. A generator expression can’t hold a separate mutable variable, unlike the readable version’s loop.

Both tricks need Python 3.8 or later. The walrus operator (:=) is one. pow()’s negative-exponent support is the other. Both are the same features the DH breaker’s golfed section leans on. Pasted into an older interpreter, this version simply won’t parse.

Interactive Visualizer

Try it above. Enter any prime, generator, and public key, plus a captured ciphertext. Watch the same baby-step giant-step search from the DH breaker run against y. Then watch the recovered private key decrypt the ciphertext directly.

ElGamal vs. Diffie-Hellman: One Breaker, Two Targets

The comparison here isn’t really about two different attacks. It’s one attack, discrete-log recovery, wired into two protocols with the same public-key shape.

Limitations of This Attack

Every limitation the DH breaker already documents applies here unchanged. The O(√p) time and memory cost is one. So is the ceiling around 40-50 bit primes, and faster structured-case methods like Pollard’s rho. This post adds nothing new on the discrete-log side.

What it does add is specific to ElGamal’s decryption step. This attack needs a captured ciphertext to actually decrypt anything. Recovering x alone, without a ciphertext, just proves the key is broken. It reveals nothing about what any message said. It also needs the same p and g the public key was generated under. Implementations that vary domain parameters per key need this attack re-run against each one.

Finally, recovering one private key x doesn’t help decrypt messages under a different key pair. The common modulus attack and Håstad’s broadcast attack exploit relationships between multiple keys or ciphertexts. This one doesn’t. It’s a single-key break, no other pairs involved.

The worked example’s p = 104729 is only 17 bits. Its baby-step table holds a few hundred entries. At 40-50 bits, that same table already needs gigabytes. That’s well past what this attack can realistically use. Modern deployments avoid this class of break entirely. They favor safe primes, prime-order subgroups, or elliptic curves instead. At those sizes, the discrete logarithm problem is believed to be genuinely hard. This toy prime exists purely to make the arithmetic checkable by hand.

FAQ

Does this attack need to know k, the sender’s random value?

No. The attack never learns k, and doesn’t need to. Recovering x, then applying ElGamal’s own decryption formula, sidesteps k entirely. That’s exactly what a legitimate recipient’s decryption also does.

Why does the DH breaker’s code work on ElGamal without any changes?

Because ElGamal’s key generation is Diffie-Hellman’s key generation, reused verbatim. Both produce the identical algebraic form: g^secret mod p.

Does encrypting the same message twice help this attack?

Not directly, unlike some RSA broadcast attacks on this site. ElGamal’s probabilistic encryption already makes two encryptions of one message look different. A fresh k does that each time. This attack doesn’t rely on message reuse at all. It goes straight after the private key instead.

Is real-world ElGamal vulnerable to baby-step giant-step?

No, for the same reason real Diffie-Hellman isn’t. A 2048-bit or larger prime makes √p astronomically large, far beyond this algorithm’s reach.

How does this compare to attacking RSA instead of ElGamal?

They’re unrelated attack surfaces. RSA’s security rests on factoring. The Fermat and Wiener breakers on this site exploit factoring-adjacent weaknesses. ElGamal’s security rests on the discrete logarithm instead. That’s exactly what this attack, and the DH breaker it’s built on, both target.

References

1. Shanks, D. “Class Number, a Theory of Factorization, and Genera.” Symposium in Pure Mathematics, 1971 (the original baby-step giant-step source).

2. ElGamal, T. “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms.” IEEE Transactions on Information Theory, 1985.

3. Menezes, A., van Oorschot, P., and Vanstone, S. “Handbook of Applied Cryptography.” CRC Press, 1996 (Chapter 3, discrete logarithm algorithms).