ElGamal encryption

ElGamal encryption turns the Diffie-Hellman key exchange into a way of sending a message. Taher Elgamal described it in 1985. To encrypt, the sender runs a fresh Diffie-Hellman exchange with the recipient's public key and uses the shared secret to scramble the message by multiplying. It was one of the first public-key encryption schemes after RSA, and its design lives on in schemes used in practice, including the one in OpenPGP.

How it works

The setting is the same as in Diffie-Hellman: a public prime p and generator g. With p = 23 and g = 5:

1. Key generation. The recipient picks a private number x = 6 and publishes h = g^x mod p = 5⁶ mod 23 = 8. The public key is (p, g, h) and the private key is x.
2. Encryption. To send the message m = 10, the sender picks a fresh random number k = 3. The sender computes c₁ = g^k = 5³ mod 23 = 10, which is the sender's half of a Diffie-Hellman exchange. The shared secret is s = h^k = 8³ mod 23 = 6, and the sender hides the message with it: c₂ = m · s = 10 × 6 mod 23 = 14. The ciphertext is the pair (10, 14).
3. Decryption. The recipient computes the same shared secret from the sender's half: s = c₁^x = 10⁶ mod 23 = 6. Dividing it out, m = c₂ · s⁻¹ = 14 × 4 mod 23 = 10, because 6 × 4 = 24 ≡ 1 modulo 23.

The shared secret works as a one-time pad for one message, since k is new each time. Nobody who lacks x or k can compute it from the public values, because that would mean solving a Diffie-Hellman problem. This site's tests run these numbers, and a larger example with random 30-bit primes works the same way.

Properties, good and bad

• Randomized. The same message encrypts differently every time, because k is new, and textbook RSA can't do that. If k is ever reused, a known plaintext gives away the shared secret, and with it the other message.
• Twice the size. The ciphertext is a pair, so it takes two group elements for one message element, an expansion of 1 to 2.
• Malleable. Anyone can turn a valid ciphertext (c₁, c₂) into a valid ciphertext of a related message, without knowing the key. Doubling c₂ gives (10, 28 mod 23 = 5), which decrypts to 5 × 4 mod 23 = 20, twice the original 10. That makes plain ElGamal unsafe against attackers who can watch how a recipient reacts to modified ciphertexts. The Cramer–Shoup scheme repairs that.
• Security. If the computational Diffie-Hellman problem is hard, the message can't be recovered. If the decisional version is hard, the scheme is semantically secure, meaning ciphertexts reveal nothing about the message to someone who can't decrypt.

One bit leaks unless you choose the group with care

There's a subtle trap in the numbers above. With p = 23 and g = 5, the generator reaches every number from 1 to 22, and half of them are squares modulo 23 (1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18) while half aren't. You can tell whether a number is a square without knowing any secret, and you can work out whether s is a square from public values (h and the parity of k, which c₁ gives away). So whether the message is a square leaks through c₂. Here 10 isn't a square, 8 is, s = 6 is, and c₂ = 14 isn't. Real systems avoid this by working in a subgroup of prime order, or by encoding the message so it's always a square. It's one reason the decisional Diffie-Hellman assumption has to hold for the group in use, and one of many reasons to use a well-reviewed library instead of the code on this page.

The ElGamal signature

The same paper gave a way to sign. The signer's key is again x (private) and h = g^x (public). To sign a message whose hash is H, pick a fresh k that shares no factor with p − 1, and send the pair (r, s) with r = g^k mod p and s = (H − xr)·k⁻¹ mod (p − 1). Anyone can check that h^r·r^s equals g^H modulo p. With x = 6 (so h = 8), a pretend hash H = 7 and k = 5, we get r = 20 and s = 17, and 8²⁰·20¹⁷ mod 23 = 17 = 5⁷ mod 23, so the signature verifies. As with encryption, a repeated k is fatal. Two signatures with the same k give two equations from which the private key falls out. The Digital Signature Algorithm (DSA) in the US standard is a variant of this scheme, and its elliptic-curve form, ECDSA, has the same weakness about k.

Where it's used

ElGamal is used in GnuPG and OpenPGP in a hybrid arrangement. A symmetric cipher such as AES encrypts the message, and ElGamal encrypts only the short key. Its more important legacy is the signature scheme that grew from it and led to the Digital Signature Algorithm (DSA). And the idea of "make a Diffie-Hellman exchange, use the shared secret to protect the message" is the basis of ECIES and of modern public-key encryption standards, applied on elliptic curves.

The code

// ElGamal encryption in the group of numbers modulo a prime p. The private key is x; the public key is h = g^x.
function modPow(base, exp, mod) {
  var result = 1n;
  base %= mod;
  while (exp > 0n) { if (exp & 1n) result = result * base % mod; base = base * base % mod; exp >>= 1n; }
  return result;
}
function modInverse(a, p) { return modPow(a, p - 2n, p); }       // Fermat: for a prime p, a^(p-2) is the inverse of a

// k must be fresh and random for every message. Knowing one plaintext and its ciphertext gives away the shared secret s.
function elgamalEncrypt(m, h, g, p, k) {
  var s = modPow(h, k, p);               // shared secret g^(xk), which only the sender (via k) and receiver (via x) can compute
  return { c1: modPow(g, k, p), c2: m * s % p };
}
function elgamalDecrypt(c, x, p) {
  var s = modPow(c.c1, x, p);            // the same secret, from the other side
  return c.c2 * modInverse(s, p) % p;
}

Common questions