ElGamal 101

ElGamal turns a Diffie–Hellman shared group element into a mask for a message. This post covers encryption, why decryption works, and what its algebra lets us do to ciphertexts.

The group and the keys

Use a cyclic group $G$ of prime order $q$, written multiplicatively, with generator $g$. Every element is a power of $g$, and exponents are taken modulo $q$. A concrete example is a prime-order subgroup of the nonzero integers modulo a prime $p$; group multiplication is then multiplication modulo $p$.

Alice chooses a secret exponent $x$ uniformly from $1,\dots ,q-1$ and computes

$$h=g^x.$$

Her public key is $(G,q,g,h)$; her private key is $x$. Bob needs an authentic copy of her public key, or an attacker could substitute a different one.

The plaintext $m$ must be an element of $G$. Arbitrary text or files are not automatically valid group elements. Message encoding or a hybrid encryption construction is a separate part of a complete system.

Encryption and decryption

Bob chooses a fresh, unpredictable exponent $y$ uniformly from $1,\dots ,q-1$, computes $s=h^y$, and sends

$$(c_1,c_2)=(g^y,m{h}^y).$$

Alice computes $s^{\prime }=c_1^x$ and recovers the message with the group inverse:

$$m=c_2(s^{\prime }{)}^{-1}.$$

This works because both sides obtain the same mask:

$$s^{\prime }=c_1^x=(g^y{)}^x=g^{xy}=(g^x{)}^y=h^y=s.$$

Thus $c_2(s^{\prime }{)}^{-1}=m{h}^y(h^y{)}^{-1}=m$. In a modular group, the inverse is a modular inverse, not ordinary division. This is the generalized group form of the algorithm described in the Handbook of Applied Cryptography, §8.4.

A small worked example

Take $p=23$, $q=11$, and $g=2$. The powers of 2 modulo 23 form the order-11 subgroup

$$G=1,2,3,4,6,8,9,12,13,16,18.$$

Choose Alice’s private key $x=6$, so $h=2^{6}mod23=18$. Bob wants to encrypt $m=9$ with $y=7$:

$$c_1=2^{7}mod23=13,s={18}^{7}mod23=6,c_2=9\cdot 6mod23=8.$$

The ciphertext is $(13,8)$. Alice computes ${13}^{6}mod23=6$. Since $6\cdot 4\equiv 1(\mathrm{mod}23)$, she recovers $8\cdot 4mod23=9$.

Here is the calculation in Python 3.8 or later. The tiny group and fixed exponents are for checking arithmetic only; they provide no security.

copy 1p, q, g = 23, 11, 2
 2x, y, message = 6, 7, 9
 3assert pow(g, q, p) == 1 and g != 1
 4assert pow(message, q, p) == 1
 5
 6public_key = pow(g, x, p)
 7c1 = pow(g, y, p)
 8c2 = message * pow(public_key, y, p) % p
 9shared = pow(c1, x, p)
10recovered = c2 * pow(shared, -1, p) % p
11
12print(public_key, (c1, c2), recovered)
13assert recovered == message

Output:

copy118 (13, 8) 9

Multiplicative homomorphism

Write $E(m;y)=(g^y,m{h}^y)$. Multiplying two ciphertexts component by component, under the same public key, gives

$$E(m_1;y_1)E(m_2;y_2)=(g^{y_1+y_2},m_1{m}_2{h}^{y_1+y_2})=E(m_1{m}_2;y_1+y_2).$$

The resulting ciphertext decrypts to the product of the messages. The exponent sum is reduced modulo $q$, and can be zero even though the original encryption exponents were nonzero. This identity concerns algebraic correctness, not a guarantee that combined ciphertexts have the same randomness distribution as fresh encryptions.

It also exposes malleability: anyone can replace $(c_1,c_2)$ by $(c_1,t{c}_2)$ for a group element $t$, causing decryption to return $tm$. An attacker can change the plaintext without learning it. Plain ElGamal therefore does not authenticate messages or provide chosen-ciphertext security.

What does root extraction mean here?

This property is about roots inside the chosen group, not ordinary real-number roots or recovery of the secret exponent.

Let $r$ be an integer relatively prime to $q$. There is an exponent $d$ satisfying $rd\equiv 1(\mathrm{mod}q)$. For any $m\in G$, the element $u=m^d$ is its unique $r$-th root, because

$$u^r=m^{dr}=m^{1+\ell q}=m$$

for some integer $\ell$, using $m^q=1$. Raising both ciphertext components to $d$ therefore produces

$$(c_1^d,c_2^d)=E(m^d;yd).$$

For our group, the inverse of 2 modulo 11 is 6. Squaring’s inverse is therefore raising to the sixth power. The square root of $9$ in this subgroup is $9^{6}mod23=3$, and $3^{2}mod23=9$. Raising the example ciphertext $(13,8)$ to the sixth power componentwise gives $(6,13)$, which decrypts to 3.

This transformation reveals neither the plaintext nor the private key; it produces a ciphertext of a related plaintext. If $gcd(r,q)\ne 1$, the inverse exponent does not exist and the argument fails. For example, every element of this order-11 group has eleventh power 1, so an arbitrary message cannot have a unique eleventh root.

Security assumptions and randomness

Efficiently computing discrete logarithms would reveal $x$, but discrete-log hardness alone is not the full confidentiality claim. The usual proof of ElGamal’s security against chosen-plaintext attacks relies on the Decisional Diffie–Hellman (DDH) assumption in the selected group: a Diffie–Hellman mask should be computationally indistinguishable from a random group element. See the ElGamal discussion in Boneh and Shoup’s A Graduate Course in Applied Cryptography. Prime order alone does not establish that DDH holds.

Never reuse $y$ to encrypt different messages. Reuse gives the same mask and exposes

$$c_{2,1}{c}_{2,2}^{-1}=m_1{m}_2^{-1}.$$

Knowing one message then reveals the other. With the worked example’s mask 6, encrypting 3 as well as 9 produces second components 18 and 8. Knowing the first message 9 recovers the mask as $8\cdot 9^{-1}mod23=6$, and then recovers the other message as $18\cdot 6^{-1}mod23=3$.

A deployable encryption protocol needs suitable group parameters, validation of received elements, secure randomness, authenticated public keys, and protection against ciphertext tampering. The arithmetic above explains the primitive; it is not a complete protocol for encrypting files or sending authenticated messages.