ElGamal Encryption — when the key is a discrete log, not a factored modulus

ElGamal is public-key encryption built directly on Diffie-Hellman: public key y = g^x mod p, and encrypting m with a fresh ephemeral k produces the pair (c1, c2) = (g^k, m * y^k mod p).

The signal that betrays it

A ciphertext that is two values, not one (c1, c2), alongside a generator g, a modulus p, and a public key y = g^x. The name "ElGamal" itself is usually stated outright in the challenge. Unlike RSA, there is no e/n pair to inspect — the entire attack surface is the discrete-log structure of (p, g, y) and the ephemeral k.

The decryption key is not a factorization at all: it is either the discrete log x of the public key y, or — cheaper, and worth checking first — the per-message ephemeral k if it is ever known, reused, or predictable.

How it works, and how it's exploited

Decryption recovers the DH shared secret and divides it back out of c2:

``python s = pow(c1, x, p) # s = c1^x = g^(kx) = y^k, the shared secret m = (c2 * pow(s, -1, p)) % p ``

An attacker reaches the same s two ways — either recovers x, or recovers k directly:

```python # Path A: x recovered via a weak DLP s = pow(c1, x, p) m = (c2 * pow(s, -1, p)) % p

# Path B: k known or reused (never re-derive x) s = pow(y, k, p) m = (c2 * pow(s, -1, p)) % p ```

Because ElGamal's hardness reduces to the same discrete-log/DDH problem as any Diffie-Hellman Fundamentals — what to audit first in any DH challenge exchange, the actual work is auditing the group and the exponents before reaching for a generic solver — the same checklist Key-Exchange Methodology — triage any DH/ECDH challenge before reaching for heavy DLP machinery applies to raw DH applies here verbatim:

- Smooth `p-1`: the strongest, most common signal. If p-1 factors into small primes, x (or k) is recoverable per-prime-factor and CRT-recombined — go straight to Pohlig-Hellman — solving the discrete log when the group order is smooth rather than a generic algorithm. This is usually the fastest win in a CTF instance of ElGamal, because challenge authors who don't deliberately pick a safe prime leave p-1 smooth by accident. - Small or structured `x`: if the private exponent is bounded to a small range, brute-force or baby-step-giant-step-style search over that range beats a full Discrete Logarithm — the factorization of the group order picks your algorithm solve. - Reused or biased `k`: an ephemeral that repeats across messages, or leaks partial bits, turns into a Hidden Number Problem — recovering a secret from many small-bounded-error samples-style key-recovery leak rather than a DLP — solve for k (or x) from the linear/lattice relation instead of attacking the group directly. - Malleability as a side door: even without recovering x or k at all, ElGamal's multiplicative homomorphism ((c1, c2*t) decrypts to m*t) lets you scale or re-randomize a ciphertext without the private key — see ElGamal Malleability — scaling plaintext by a known factor without the private key for the blocklist-bypass and oracle-chaining use of this.

Once the group is confirmed weak, compute the discrete log directly (Pohlig-Hellman, baby-step-giant-step, or whatever the order's factorization dictates) rather than guessing — x and k are both just discrete logs of known base/target pairs, so the Discrete Logarithm — the factorization of the group order picks your algorithm triage (factor the group order first, let the factorization pick the algorithm) is the entire strategy.

What does NOT work

- Treating ElGamal like RSA. There is no modulus to factor and no e to invert — reaching for factorization tools (Fermat, Pollard rho) on p wastes time; p is public and typically prime by design. The lever is always the *group structure* (order of g, smoothness of p-1), not p itself. - Brute-forcing a full-size `x` or `k` without first checking the group order. If p-1 is smooth, a naive brute force or a generic O(sqrt(n)) search over the full exponent range is needlessly slow — Pohlig-Hellman collapses it to roughly O(√p_max), the square root of the *largest* prime factor of the order, not the factor itself. Always factor the order before picking an algorithm. - Assuming semantic security implies tamper-resistance. ElGamal can be semantically secure under DDH and still be completely malleable — the two properties are independent. A working decrypt-recovery attack on x/k and a working malleability attack on c2 are separate techniques; don't discard the malleability route just because the group looks strong (large prime order, no smooth p-1) — malleability needs no DLP break at all. - Re-deriving `x` when `k` is already known (or vice versa). They unlock the same shared secret s = c1^x = y^k; whichever is exposed by the challenge is the cheaper path. Don't do the harder DLP if the easier exponent is sitting in a log, a repeated nonce, or a predictable PRNG.

Related

ElGamal Malleability — scaling plaintext by a known factor without the private key Discrete Logarithm — the factorization of the group order picks your algorithm Pohlig-Hellman — solving the discrete log when the group order is smooth Diffie-Hellman Fundamentals — what to audit first in any DH challenge Key-Exchange Methodology — triage any DH/ECDH challenge before reaching for heavy DLP machinery Hidden Number Problem — recovering a secret from many small-bounded-error samples