ElGamal

Why decryption works

Bob raises the first component to his exponent, and Alice raised Bob’s public value to hers:

c₁^x = (g^k)^x = g^kx  ·  y^k = (g^x)^k = g^xk  (mod p)

So both hold the same nonzero number s, although neither told the other an exponent. Alice sent c₂ = m·s, and Bob undoes the multiplication: c₂·s⁻¹ = m·s·s⁻¹ = m (mod p).

A ciphertext can be changed without the key

Anyone who sees (c₁, c₂) can replace it by (c₁, t·c₂ mod p) for a nonzero t. Bob will then decrypt t·m mod p. An attacker can change the decrypted message in a predictable algebraic way without knowing the private key, and without knowing the message.

This is called malleability. Textbook ElGamal gives no integrity and no authentication: Bob cannot tell a modified pair from a genuine one, and decrypting with a wrong key raises no error either. It simply gives another number.

Why k must be fresh

If two messages are encrypted under the same key with the same k, they are masked by the same s: c₂ = m₁·s and c₂′ = m₂·s. Dividing one by the other cancels the mask: c₂·(c₂′)⁻¹ = m₁·m₂⁻¹ (mod p). An observer learns how the messages are related, and if one of them becomes known, so does the other.

In a group this small, two exponents drawn independently will sometimes coincide by chance, so two ciphertexts can share a first component even when nothing was reused on purpose. Real systems use groups so large that this does not happen in practice.

What this page is not

• The primes are tiny: Bob’s exponent can be found by trying them all, as the Diffie–Hellman page’s eavesdropper does.
• There is no authentication, no standard message encoding, and no hybrid encryption with a symmetric cipher.
• Working in the whole group (ℤ/pℤ)^× with the message as a group element leaks something even for a large p: from the public values one can tell whether m is a square modulo p. A large prime does not by itself make this scheme secure.

What is ElGamal?

A public-key encryption scheme published by Taher ElGamal in 1985. Anyone can encrypt to Bob with his public key; only Bob’s private exponent undoes it. Its security rests on the difficulty of discrete logarithms in a suitable group.

How are the keys generated?

Bob fixes a prime p and a generator g, picks a private exponent x, and publishes y = g^x mod p. This page asks for a primitive root, a g whose powers reach every nonzero residue.

That requirement is a teaching convention for this page, not a rule of ElGamal. Real constructions usually work in a subgroup of large prime order, with a generator validated for that subgroup. A primitive root and a large prime do not by themselves give modern encryption security.

Why is encryption randomized?

Alice draws a new exponent k for every message, so the same message encrypts to a different pair each time, and the mask s = y^k is used only once. Any k from 1 to p − 2 works; it need not be coprime to p − 1 (that condition belongs to ElGamal signatures, not to encryption). The opening example uses a fixed k only so that its numbers can be checked by hand.

How does it relate to Diffie–Hellman?

It is a Diffie–Hellman exchange put to work. Bob’s public value y = g^x is one half of an exchange, published in advance; Alice’s c₁ = g^k is the other half, sent with the message. Alice computes y^k, Bob computes c₁^x, and both are g^xk mod p: the shared secret. ElGamal multiplies the message by it.

What is the discrete logarithm problem?

The public key contains y = g^x mod p. Computing y from x is quick; going back from y to x is the discrete logarithm problem, believed to be hard in properly chosen groups of cryptographic size. In the groups on this page it is easy: see the eavesdropper on the Diffie–Hellman page, or the Discrete Logarithm calculator.

How does it compare with RSA?

Neither textbook version is safe to use as it stands, and neither is simply “more secure” than the other: what matters is the complete, standardized construction and its parameters.

What are ElGamal’s limitations here?

Everything under “Explore ciphertext security” above. This page is an exact mathematical model, not an encryption tool, and it does not offer a “secure mode”: browsers provide no standard classical ElGamal, and inventing one would be the wrong lesson. Modern systems agree on a key with elliptic-curve Diffie–Hellman and then use authenticated symmetric encryption.