# ElGamal: Discrete Logarithm Encryption
> [!Note]
> **ElGamal** extends the Diffie–Hellman idea into a full **public-key cryptosystem**, securing confidentiality by tying every operation to the hardness of the **discrete logarithm problem** in a large prime field.
In the **key-generation phase** a large prime **p** is fixed together with a generator **α** of a subgroup of **ℤ*_p**. A secret integer **d**—the **private key**—is drawn uniformly from the interval $[2, p − 2]$ and the public component **β = αᵈ mod p** is computed. The tuple **(p, α, β)** can circulate openly, yet recovering **d** from it would require solving a discrete logarithm, which is assumed computationally infeasible.
During **encryption** the sender samples a fresh random exponent **v**, derives **c₁ = αᵛ mod p** and blinds the plaintext **m** by the shared-secret factor **βᵛ**, yielding **c₂ = m · βᵛ mod p**. The ciphertext is therefore the pair **(c₁, c₂)**, and because the random value **v** changes every run, the same message encrypts to many different ciphertexts; this **probabilistic** nature thwarts pattern matching at the cost of doubling the message length.
On reception, the owner of **d** recovers the plaintext by computing **m = c₂ · c₁^{−d} mod p**, since **c₁^{d} ≡ α^{vd} ≡ βᵛ (mod p)**. The algebra guarantees that decryption inverts encryption exactly, yet no information about **d** leaks to an eavesdropper.
> [!Example]
> With the slide’s toy parameters **p = 3725468 627**, **α = 1500839 12** and **d = 80787807**, the public value becomes **β = αᵈ mod p = 3398986020**. Encrypting **m = 424242** with the random **v = 1052400195** produces **c₁ = αᵛ mod p = 434020969** and **c₂ = m · βᵛ mod p = 278723740**; Bob later recovers the original message by evaluating **m = c₂ · c₁^{−d} mod p = 424242**, illustrating both correctness and the probabilistic disguise that ElGamal provides.
Although modern implementations often swap finite-field arithmetic for elliptic-curve groups, the principles remain identical: **randomized encryption**, reliance on the **discrete logarithm problem**, and simple algebraic operations that make ElGamal attractive for hybrid schemes and threshold cryptography.
```mermaid
sequenceDiagram
participant KG as Key Generation
participant Alice
participant Bob
%% ---------- KEY GENERATION ----------
KG->>KG: choose prime p, generator α
KG->>KG: select secret d
KG->>KG: β = α^d mod p
KG-->>Alice: k_pub = (p, α, β)
KG-->>Bob: k_priv = d (secret)
%% ---------- ENCRYPTION ----------
Alice->>Alice: pick random v
Alice->>Alice: c1 = α^v mod p
Alice->>Alice: c2 = m · β^v mod p
Alice-->>Bob: ciphertext (c1, c2)
%% ---------- DECRYPTION ----------
Bob->>Bob: m = c2 · c1^{-d} mod p
```
### Python Code
```python
import random
from math import gcd
def is_prime(n: int) -> bool:
"""Naïve primality test appropriate only for small demo primes."""
if n < 2:
return False
if n % 2 == 0:
return n == 2
r = int(n ** 0.5) + 1
for i in range(3, r, 2):
if n % i == 0:
return False
return True
def generate_prime(low: int = 10_000, high: int = 20_000) -> int:
"""Return a random prime in [low, high]."""
while True:
candidate = random.randint(low, high)
if is_prime(candidate):
return candidate
def find_generator(p: int) -> int:
"""
Find a primitive root (generator) modulo prime p.
Very slow—but fine for small p in demos.
"""
phi = p - 1
# factorize phi
factors = []
n = phi
i = 2
while i * i <= n:
if n % i == 0:
factors.append(i)
while n % i == 0:
n //= i
i += 1
if n > 1:
factors.append(n)
# search for generator
for g in range(2, p):
ok = True
for q in factors:
if pow(g, phi // q, p) == 1:
ok = False
break
if ok:
return g
raise RuntimeError("No generator found")
def elgamal_keygen():
"""Generate a toy ElGamal key pair."""
p = generate_prime()
g = find_generator(p)
d = random.randint(2, p - 2) # private key
beta = pow(g, d, p) # public part
return {"p": p, "g": g, "d": d, "beta": beta}
def elgamal_encrypt(m: int, p: int, g: int, beta: int):
"""Encrypt integer plaintext m with public key (p, g, beta)."""
if not 0 < m < p:
raise ValueError("Plaintext must be in range 1..p-1")
v = random.randint(2, p - 2)
c1 = pow(g, v, p)
s = pow(beta, v, p) # shared secret
c2 = (m * s) % p
return (c1, c2, v)
def elgamal_decrypt(c1: int, c2: int, p: int, d: int):
"""Decrypt ciphertext pair (c1, c2) with private key d."""
s = pow(c1, d, p) # shared secret
# modular inverse of s
s_inv = pow(s, -1, p)
m = (c2 * s_inv) % p
return m
# -------------------- DEMO -----------------------------
keypair = elgamal_keygen()
p = keypair["p"]
g = keypair["g"]
d = keypair["d"]
beta = keypair["beta"]
# choose plaintext
m_plain = random.randint(1, p - 1)
c1, c2, v = elgamal_encrypt(m_plain, p, g, beta)
m_rec = elgamal_decrypt(c1, c2, p, d)
print("=== ELGAMAL DEMONSTRATION (toy parameters) ===")
print(f"Prime p = {p}")
print(f"Generator g = {g}")
print(f"Private key d = {d}")
print(f"Public beta = {beta}")
print(f"Random v = {v}")
print("\n--- Encryption ---")
print(f"Plaintext m = {m_plain}")
print(f"Ciphertext c1 = {c1}")
print(f"Ciphertext c2 = {c2}")
print("\n--- Decryption ---")
print(f"Recovered m = {m_rec}")
print("\nSuccess:", m_plain == m_rec)
```
---
## References