ElGamal Encryption

In 1976, Whitfield Diffie and Martin Hellman showed that two people who have never met can agree on a shared secret over a public channel — an idea so surprising it rewrote cryptography. What they described was a key exchange, not yet a full encryption scheme.

Nine years later, Taher ElGamal turned that handshake into a complete public-key encryption system. The paper he published at CRYPTO 1985 is only a few pages, yet it introduced two things that remain central to modern cryptography: a public-key cipher and a digital signature scheme, both resting on the hardness of the discrete logarithm problem.

What makes ElGamal unusual — and important — is that it is probabilistic: encrypt the same message twice and you get two completely different ciphertexts. That randomness is not a quirk; it is the mechanism that gives the scheme its formal security guarantee. Understanding ElGamal means understanding why randomness and hardness together create privacy.

Choose a message number, then encrypt it. Hit Encrypt again and watch a different ciphertext appear for the same message — because a fresh random $k$ is picked every time. Decryption always recovers the original.

<p class="hint">
  {{hint}}
</p>
<div class="param-row">
  <span class="param">p = 23</span>
  <span class="param">g = 5</span>
  <span class="param">x = 6 ({{private_lbl}})</span>
  <span class="param">h = g<sup>x</sup> mod p = 8 ({{public_lbl}})</span>
</div>
<div class="controls">
  <label for="msg">{{msg_label}}</label>
  <input id="msg" type="number" min="1" max="22" value="7">
  <button id="btnEncrypt" type="button">{{btn_encrypt}}</button>
  <button id="btnAgain" type="button">{{btn_again}}</button>
</div>
<div id="steps" class="steps"></div>
<div id="status" class="status"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.param-row { display: flex; flex-wrap: wrap; gap: .4rem .9rem; margin: 0 0 .9rem; }
.param { font: 600 .82rem ui-monospace, monospace; background: #e8eef3;
         color: #1d3557; border: 1px solid #cdd9e3; padding: .15rem .45rem;
         border-radius: 5px; }
.controls { display: flex; flex-wrap: wrap; align-items: center; gap: .5rem; margin-bottom: .9rem; }
label { font-size: .9rem; }
input[type=number] { width: 5rem; padding: .35rem .5rem; font-size: .9rem;
                     border: 1px solid #adb1b8; border-radius: 6px; }
button { font: 600 14px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button:hover { background: #16294a; }
.steps { display: flex; flex-direction: column; gap: .4rem; margin-bottom: .7rem; min-height: 3.5rem; }
.step { background: #f4f7fa; border: 1px solid #cdd9e3; border-radius: 8px;
        padding: .45rem .7rem; font-size: .88rem; line-height: 1.55; }
.step b { color: #1d3557; }
.step.hi { background: #fff8e1; border-color: #f0c040; }
.step.ok { background: #e6f4ea; border-color: #5cb85c; }
.step.diff { background: #fde8ec; border-color: #e63946; }
.status { font-size: 1rem; font-weight: 600; min-height: 1.4em; }
.status.ok { color: #0a7d33; }

// Code not found

Notice the key asymmetry. Encrypting is fast: two modular exponentiations. Decrypting is equally fast: one exponentiation with the private key. But recovering the private key from the public key requires solving the discrete logarithm — a problem for which no efficient classical algorithm is known, related to the hardness explored in Diffie-Hellman. The random $k$ ensures that even an attacker who intercepts every ciphertext learns nothing about the message or about future encryptions.

How hard is it to break ElGamal, really?

• Breaking the private key directly means computing $x$ from $g^x \bmod p$ — the discrete logarithm problem. For carefully chosen primes $p$ of 2048 bits or more, the best known classical algorithms (General Number Field Sieve) run in sub-exponential but super-polynomial time: hard enough to be practical today, but not proven impossible.
• Distinguishing ciphertexts is the formal target. An attacker who can tell apart encryptions of two chosen messages breaks IND-CPA security (indistinguishability under chosen-plaintext attack). Proving ElGamal is IND-CPA secure reduces to the Decisional Diffie-Hellman (DDH) assumption: given $(g, g^a, g^b, g^c)$, can you tell whether $c = ab$? This reduction was made precise by Tsiounis and Yung (1998).
• The probabilistic guarantee: because $k$ is freshly random per encryption, two encryptions of the same message are computationally indistinguishable — a property deterministic schemes like textbook RSA completely lack.
• Quantum threat: Shor's algorithm (1994) breaks the discrete logarithm in polynomial time on a quantum computer, which would render ElGamal insecure. This is why post-quantum cryptography is an active research area.

The status of ElGamal's security: proven secure under DDH (Tsiounis-Yung, 1998) in the classical setting. DDH itself is believed hard but not proven so — it falls in the same philosophical territory as P vs NP: we strongly expect hardness, but cannot yet rule out an efficient algorithm.

ElGamal's design choices — public-key setup, randomized encryption, algebraic structure — echo through nearly every corner of applied cryptography:

• OpenPGP / GnuPG: the ElGamal encryption variant (Elgamal-E) has been a standard option in the OpenPGP format since RFC 2440. Millions of encrypted emails sent over decades relied on it.
• Threshold cryptography: ElGamal's homomorphic property ($\text{Enc}(m_1) \cdot \text{Enc}(m_2) = \text{Enc}(m_1 m_2)$) lets multiple parties jointly decrypt without any single party holding the full key. This underlies electronic voting systems used in real elections (Helios, Belenios).
• Elliptic-curve variant (ECIES): replacing the multiplicative group $\mathbb{Z}_p^*$ with an elliptic-curve group gives the same security at much smaller key sizes. ECIES is used in TLS, Signal, and many mobile protocols.
• Teaching formal security: ElGamal is the canonical textbook example of a scheme with a provable security reduction, making it the entry point to understanding IND-CPA, semantic security, and the DDH assumption.

Understand ElGamal and you hold the blueprint for modern public-key cryptography — the same pattern of hardness + randomness appears in Cramer-Shoup, in lattice-based schemes, and in the zero-knowledge proofs powering blockchains.

ElGamal's 1985 paper took a clever key-exchange protocol and made it into a full encryption scheme — and in doing so, introduced the world to provable security: the idea that a cryptosystem's safety can be formally reduced to a well-studied mathematical assumption.

The scheme's defining feature is randomness. Every encryption uses a fresh random $k$, so ciphertexts carry no fingerprint of the message or of past encryptions. That single design choice is the difference between a scheme that looks secure and one that can be proven secure under DDH.

Today, ElGamal lives on in OpenPGP, in electronic voting, in elliptic-curve form inside every TLS handshake. And it sits at the root of a deeper question: the hardness of the discrete logarithm, and through it the open boundary between what computation can and cannot efficiently solve — the same frontier as P vs NP.