ElGamal Encryption

ElGamal Encryption

The ElGamal cryptosystem (Taher ElGamal, 1985) is a public-key scheme based on the Discrete Logarithm Problem, like Diffie-Hellman. Unlike RSA, ElGamal encryption is probabilistic — the same plaintext encrypted twice produces different ciphertexts (due to the random $k$), which is a security advantage.

Key Generation

Choose a prime $p$, generator $g$, and private key $x$. The public key is:

$y = g^x \bmod p$

Encryption

To encrypt message $m$ with public key $y$, choose a random session key $k$:

$c_1 = g^k \bmod p$ $c_2 = m \cdot y^k \bmod p$

The ciphertext is the pair $(c_1, c_2)$.

Decryption

Using private key $x$:

$m = c_2 \cdot c_1^{-x} \bmod p$

Since $c_1 = g^k$ and $y = g^x$:

$c_1^x = g^{kx} = y^k$

So $c_2 \cdot c_1^{-x} = m \cdot y^k \cdot y^{-k} = m$. ✓

Computing $c_1^{-x} \bmod p$

By Fermat's Little Theorem, $c_1^{p-1} \equiv 1 \pmod{p}$, so $c_1^{-x} \equiv c_1^{p-1-x} \pmod{p}$.

Example

$p=23$, $g=5$, private key $x=6$, public key $y = 5^6 \bmod 23 = 8$.

Encrypt $m=10$ with session key $k=3$:

• $c_1 = 5^3 \bmod 23 = 10$ · $c_2 = 10 \cdot 8^3 \bmod 23 = 10 \cdot 6 \bmod 23 = 14$

Decrypt $(10, 14)$: $14 \cdot 10^{23-1-6} \bmod 23 = 14 \cdot 10^{16} \bmod 23 = 10$ ✓

Your Task

Implement:

• elgamal_encrypt(m, g, pub_key, k, p) → (c1, c2)
• elgamal_decrypt(c1, c2, priv_key, p) → m