Introduction

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.

Try It

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

<p class="hint">
  ElGamal encryption uses small toy numbers here (p=23, g=5, private key x=6, public key h=g<sup>x</sup>=8). Pick a message (1–22), encrypt it, then encrypt again — you get a <b>different ciphertext</b> each time because a fresh random k is chosen. Decryption always recovers the original.
</p>
<div class="param-row">
  <span class="param">p = 23</span>
  <span class="param">g = 5</span>
  <span class="param">x = 6 (private)</span>
  <span class="param">h = g<sup>x</sup> mod p = 8 (public)</span>
</div>
<div class="controls">
  <label for="msg">Message m (1–22):</label>
  <input id="msg" type="number" min="1" max="22" value="7">
  <button id="btnEncrypt" type="button">Encrypt</button>
  <button id="btnAgain" type="button">Encrypt 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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// ElGamal encryption demo (toy group: p=23, g=5, x=6, h=8).
// Security relies on the discrete log problem: given g and h=g^x mod p,
// find x. For real primes (2048-bit) this is computationally infeasible.
// Probabilistic: fresh random k each encryption => different (c1,c2) every time.

const P = 23, G = 5, X = 6;   // prime, generator, private key
const H = modpow(G, X, P);    // public key h = g^x mod p = 8

function modpow(base, exp, mod) {
  let result = 1n;
  base = BigInt(base) % BigInt(mod);
  exp = BigInt(exp);
  mod = BigInt(mod);
  while (exp > 0n) {
    if (exp % 2n === 1n) result = result * base % mod;
    exp = exp >> 1n;
    base = base * base % mod;
  }
  return Number(result);
}

function modinv(a, m) {
  // Extended Euclidean algorithm for modular inverse
  let [old_r, r] = [a, m], [old_s, s] = [1, 0];
  while (r !== 0) {
    const q = Math.floor(old_r / r);
    [old_r, r] = [r, old_r - q * r];
    [old_s, s] = [s, old_s - q * s];
  }
  return ((old_s % m) + m) % m;
}

function encrypt(m, k) {
  const c1 = modpow(G, k, P);             // c1 = g^k mod p
  const s  = modpow(H, k, P);             // s  = h^k mod p  (shared secret)
  const c2 = (m * s) % P;                 // c2 = m * s mod p
  return { c1, c2, s, k };
}

function decrypt(c1, c2) {
  const s  = modpow(c1, X, P);            // s  = c1^x mod p = g^(kx) mod p
  const si = modinv(s, P);                // s^{-1} mod p
  const m  = (c2 * si) % P;              // m  = c2 * s^{-1} mod p
  return { s, si, m };
}

let lastC1 = null, lastC2 = null;

function doEncrypt() {
  const mVal = parseInt(document.getElementById('msg').value, 10);
  if (isNaN(mVal) || mVal < 1 || mVal > 22) {
    setStatus(`Choose m between 1 and 22.`, ''); return;
  }
  // random k in [1, p-2]
  const k = 1 + Math.floor(Math.random() * (P - 2));
  const { c1, c2, s } = encrypt(mVal, k);
  const stepsEl = document.getElementById('steps');
  const isRepeat = lastC1 !== null;

  const prevC1 = lastC1, prevC2 = lastC2;
  lastC1 = c1; lastC2 = c2;

  const dec = decrypt(c1, c2);

  stepsEl.innerHTML = '';

  function addStep(html, cls) {
    const d = document.createElement('div');
    d.className = 'step' + (cls ? ' ' + cls : '');
    d.innerHTML = html;
    stepsEl.appendChild(d);
  }

  addStep(fmt(`<b>Random k</b> = %k% (chosen freshly at random each time)`, { k: k }));
  addStep(`<b>c<sub>1</sub></b> = g<sup>k</sup> mod p = ${G}<sup>${k}</sup> mod ${P} = <b>${c1}</b>`);
  addStep(fmt(`<b>Shared secret s</b> = h<sup>k</sup> mod p = %H%<sup>%k%</sup> mod %P% = <b>%s%</b>`, { H: H, k: k, P: P, s: s }));
  addStep(`<b>c<sub>2</sub></b> = m · s mod p = ${mVal} · ${s} mod ${P} = <b>${c2}</b>`);

  if (isRepeat) {
    const changed = (c1 !== prevC1 || c2 !== prevC2);
    addStep(
      fmt(`Previous ciphertext: (<b>%prevC1%, %prevC2%</b>)<br>
       New ciphertext:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(<b>%c1%, %c2%</b>)`, { prevC1: prevC1, prevC2: prevC2, c1: c1, c2: c2 }),
      changed ? 'diff' : 'hi'
    );
    if (changed) {
      setStatus(`Different ciphertext for the same message!`, 'ok');
    } else {
      setStatus(`Same k happened by chance — try again!`, '');
    }
  }

  addStep(
    fmt(`<b>Decrypt:</b> s = c<sub>1</sub><sup>x</sup> mod p = %c1%<sup>%X%</sup> mod %P% = %s%,
     s<sup>-1</sup> mod p = %si%,
     m = c<sub>2</sub> · s<sup>-1</sup> mod p = %c2% · %si% mod %P% = <b>%m%</b>`, { c1: c1, X: X, P: P, s: dec.s, si: dec.si, c2: c2, m: dec.m }),
    'ok'
  );

  if (dec.m !== mVal) {
    setStatus(`Decryption mismatch — bug!`, 'bad');
  } else if (!isRepeat) {
    setStatus(fmt(`Encrypted! Ciphertext = (%c1%, %c2%). Decrypted back to %m%.`, { c1: c1, c2: c2, m: dec.m }), 'ok');
  }

  // Log to console for verification
  console.log(`ElGamal | m=${mVal} k=${k} => (c1=${c1},c2=${c2}) dec=${dec.m} ok=${dec.m===mVal}`);
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status ' + cls;
}

document.getElementById('btnEncrypt').addEventListener('click', () => {
  lastC1 = null; lastC2 = null;
  document.getElementById('steps').innerHTML = '';
  setStatus('', '');
  doEncrypt();
});
document.getElementById('btnAgain').addEventListener('click', doEncrypt);
Result
Console

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 kk ensures that even an attacker who intercepts every ciphertext learns nothing about the message or about future encryptions.

The Real Complexity

How hard is it to break ElGamal, really?

  • Breaking the private key directly means computing xx from gx mod pg^x \bmod p — the discrete logarithm problem. For carefully chosen primes pp 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,ga,gb,gc)(g, g^a, g^b, g^c), can you tell whether c=abc = ab? This reduction was made precise by Tsiounis and Yung (1998).
  • The probabilistic guarantee: because kk 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.

Where It Matters

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 (Enc(m1)⋅Enc(m2)=Enc(m1m2)\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 Zp∗\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.

Conclusion

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 kk, 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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/elgamal-encryption/Content licensed under CC BY-NC 4.0.