I find ElGamal a fascinating counterpart to RSA, because it takes a completely different mathematical path to achieve the same goal of public-key encryption. Instead of relying on the difficulty of factoring large numbers, ElGamal relies on the difficulty of the discrete logarithm problem within a finite cyclic group. It also has a distinctive property: even encrypting the exact same message twice with the same public key produces different ciphertexts each time, because it introduces randomness into every encryption operation.
History and Background
I learned that Taher Elgamal, an Egyptian-American cryptographer, introduced this algorithm in 1985 in a paper titled “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms.” He built it directly on the Diffie-Hellman key exchange protocol that Whitfield Diffie and Martin Hellman had published in 1976, extending the idea from just exchanging a shared secret to actually encrypting arbitrary messages. ElGamal’s scheme was never patented, unlike RSA was for a time in the United States, which made it attractive for open-source and government use, and it went on to form the basis of the U.S. government’s Digital Signature Algorithm (DSA), as well as later influencing elliptic-curve variants used widely today.
Problem Statement
ElGamal addresses the same fundamental challenge as RSA: enabling secure communication between parties who have not previously shared a secret key. It specifically builds a public-key encryption scheme around the discrete logarithm problem, which states that given a cyclic group, a generator $g$, and a value $g^x$, it is computationally very difficult to recover $x$, even though computing $g^x$ from $x$ is easy. This asymmetry, similar in spirit to RSA’s factoring asymmetry but based on entirely different mathematics, is what I rely on to build a secure encryption scheme.
Core Concepts
Terms I use throughout my explanation:
- Cyclic group: a mathematical group generated by repeatedly applying an operation to a single element (the generator); ElGamal traditionally works within the multiplicative group of integers modulo a large prime $p$.
- Generator $g$: an element of the group such that repeatedly multiplying $g$ by itself generates all (or most) of the group’s elements.
- Discrete logarithm problem: given $g$ and $g^x \bmod p$, finding $x$ is computationally infeasible for well-chosen large primes.
- Private key $x$: a randomly chosen secret integer.
- Public key $y$: computed as $y = g^x \bmod p$, shared openly.
- Ephemeral key $k$: a fresh random value chosen for each individual encryption, which is what makes ElGamal ciphertexts non-deterministic.
How It Works
I break ElGamal into key generation, encryption, and decryption.
- Key generation: I choose a large prime $p$ and a generator $g$ of the multiplicative group modulo $p$. I choose a random private key $x$ where $1 < x < p – 1$. I compute the public key $y = g^x \bmod p$. My public key is $(p, g, y)$ and my private key is $x$.
- Encryption: to encrypt a message $M$ (represented as a number less than $p$), the sender picks a random ephemeral integer $k$ for this specific message, computes $C_1 = g^k \bmod p$, and computes $C_2 = M \times y^k \bmod p$. The ciphertext is the pair $(C_1, C_2)$.
- Decryption: I compute the shared secret $s = C_1^x \bmod p$, then recover the message as $M = C_2 \times s^{-1} \bmod p$, where $s^{-1}$ is the modular multiplicative inverse of $s$.
Working Principle
I think of ElGamal as essentially Diffie-Hellman key exchange combined with a simple multiplicative masking step. The sender and I effectively perform a Diffie-Hellman exchange for every single message: the sender’s ephemeral value $k$ plays the role of a temporary private key, producing $C_1 = g^k \bmod p$ as the corresponding temporary public value, while my long-term public key $y = g^x \bmod p$ lets the sender compute the same shared secret $s = y^k \bmod p = g^{xk} \bmod p$ that I can independently compute as $s = C_1^x \bmod p = g^{kx} \bmod p$, since exponentiation is commutative in the exponent. Once both sides share this secret $s$, the sender uses it to mask the message through multiplication, and I unmask it by multiplying by the modular inverse of $s$. Because a fresh $k$ is chosen for every encryption, the same plaintext encrypted twice yields different ciphertexts, giving ElGamal semantic security that plain textbook RSA lacks.
Mathematical Foundation
Key generation:
$$y = g^x \bmod p$$
Encryption of message $M$ using fresh random $k$:
$$C_1 = g^k \bmod p$$ $$C_2 = M \cdot y^k \bmod p$$
Decryption:
$$s = C_1^x \bmod p$$ $$M = C_2 \cdot s^{-1} \bmod p$$
I can verify correctness by substitution:
$$s = C_1^x = (g^k)^x = g^{kx} \bmod p$$ $$C_2 \cdot s^{-1} = M \cdot y^k \cdot (g^{kx})^{-1} = M \cdot (g^x)^k \cdot g^{-kx} = M \cdot g^{xk} \cdot g^{-kx} = M \bmod p$$
since $g^{xk} \cdot g^{-kx} = g^0 = 1$. This confirms that decryption always recovers the original message when using the correct private key.
Diagrams
flowchart TD
A["Choose prime p and generator g"] --> B["Choose private key x"]
B --> C["Compute public key y = g^x mod p"]
C --> D["Public key: (p, g, y)"]
C --> E["Private key: x"]flowchart LR
M[Message M] --> Pick["Pick random k"]
Pick --> C1["C1 = g^k mod p"]
Pick --> C2["C2 = M times y^k mod p"]
C1 --> CT["Ciphertext (C1, C2)"]
C2 --> CT
CT --> S["s = C1^x mod p"]
S --> Dec["M = C2 times s inverse mod p"]Pseudocode
function ELGAMAL_KEYGEN(bit_length):
p = generate_large_prime(bit_length)
g = find_generator(p)
x = random_integer(1, p - 2)
y = modular_exponentiation(g, x, p)
return public_key(p, g, y), private_key(x)
function ELGAMAL_ENCRYPT(message, p, g, y):
k = random_integer(1, p - 2)
C1 = modular_exponentiation(g, k, p)
s = modular_exponentiation(y, k, p)
C2 = (message * s) mod p
return (C1, C2)
function ELGAMAL_DECRYPT(C1, C2, p, x):
s = modular_exponentiation(C1, x, p)
s_inverse = modular_inverse(s, p)
message = (C2 * s_inverse) mod p
return message
Step-by-Step Example
I will use small numbers to keep the arithmetic traceable by hand.
- I choose the prime $p = 23$ and generator $g = 5$.
- I choose my private key $x = 6$.
- I compute my public key $y = 5^6 \bmod 23 = 8$.
- My public key is $(23, 5, 8)$, and my private key is $6$.
- Suppose a sender wants to encrypt the message $M = 10$. They pick a random ephemeral key $k = 3$.
- They compute $C_1 = 5^3 \bmod 23 = 10$.
- They compute $s = y^k \bmod p = 8^3 \bmod 23 = 6$.
- They compute $C_2 = M \times s \bmod p = 10 \times 6 \bmod 23 = 14$.
- The ciphertext sent to me is $(C_1, C_2) = (10, 14)$.
- To decrypt, I compute $s = C_1^x \bmod p = 10^6 \bmod 23 = 6$.
- I compute the modular inverse of $6$ modulo $23$, which is $4$, since $6 \times 4 = 24 \equiv 1 \pmod{23}$.
- I compute $M = C_2 \times s^{-1} \bmod p = 14 \times 4 \bmod 23 = 56 \bmod 23 = 10$, recovering the original message.
Time Complexity
Key generation requires finding a large prime, generally the dominant cost, similar to RSA’s key generation. Both encryption and decryption require modular exponentiation, which using repeated squaring costs $O(\log k)$ or $O(\log x)$ multiplications respectively, each multiplication on $b$-bit numbers costing roughly $O(b^2)$ with basic methods, giving encryption and decryption costs on the order of $O(b^2 \log p)$. I note that ElGamal encryption is somewhat more expensive than RSA encryption with a small public exponent, since ElGamal requires two full modular exponentiations (for $C_1$ and $C_2$’s masking factor) rather than one, and ciphertext is also twice the size of the plaintext, since it consists of the pair $(C_1, C_2)$.
Space Complexity
ElGamal requires storing the prime $p$, generator $g$, and public/private key values, each roughly $b$ bits for a $b$-bit key, giving $O(b)$ space for key material. Because each ciphertext consists of two group elements rather than one, ElGamal ciphertexts require $O(b)$ space per encrypted value, but with double the size of the equivalent RSA ciphertext for the same security level, which I consider a meaningful tradeoff when storage or bandwidth is constrained.
Correctness Analysis
I proved above through direct algebraic substitution that decryption recovers the original message: the shared secret $s = g^{xk} \bmod p$ can be computed by either party using their respective private values ($x$ for me, $k$ for the sender), and multiplying by $s$ during encryption and then by $s^{-1}$ during decryption exactly cancels out, leaving the original message. This relies only on standard properties of modular arithmetic and group theory (associativity, existence of inverses in the multiplicative group modulo a prime), so it holds universally for any valid key pair and any message in the appropriate range, not just for specific chosen numbers.
Advantages
- I get semantic security from the randomized ephemeral key, meaning encrypting the same message twice produces different ciphertexts, which prevents an attacker from noticing repeated messages simply by comparing ciphertexts.
- ElGamal’s security rests on the discrete logarithm problem, a different mathematical foundation than RSA’s factoring problem, which is useful for cryptographic diversity.
- It was never patented, making it freely available for any use, unlike RSA during its patent period in the United States.
- The same underlying mathematical ideas extend naturally to elliptic curve variants, which offer equivalent security with much smaller key sizes.
Disadvantages
- Ciphertext expansion: every encrypted message doubles in size compared to the plaintext, since the ciphertext consists of two values instead of one.
- ElGamal is generally slower than RSA for encryption given equivalent security levels, due to the two modular exponentiations required.
- Careless reuse of the ephemeral key $k$ across multiple encryptions catastrophically breaks security, allowing an attacker to recover the private key or plaintexts, so implementations must guarantee true randomness for every single encryption.
- Textbook ElGamal, like textbook RSA, is vulnerable to certain structural attacks (such as malleability, where an attacker can transform a ciphertext into a different valid ciphertext without knowing the plaintext) unless combined with proper padding or hybrid encryption schemes.
Applications
I have seen ElGamal’s principles applied in GNU Privacy Guard (GPG) as one of the supported public-key encryption algorithms, in the Digital Signature Algorithm (DSA) which adapts ElGamal’s ideas for signatures rather than encryption, and in various academic and research cryptosystems exploring discrete-logarithm-based security. Its elliptic-curve descendants, such as ECIES (Elliptic Curve Integrated Encryption Scheme), are used far more widely today in modern protocols because they achieve equivalent security with much smaller keys and faster operations.
Implementation in C
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <time.h>
/* Small-number ElGamal demonstration for educational purposes.
Real ElGamal requires big-integer arithmetic since keys are
hundreds or thousands of bits long; this uses standard integer
types to keep the demonstration self-contained. */
long long modular_exponentiation(long long base, long long exponent, long long modulus) {
long long result = 1;
base = base % modulus;
while (exponent > 0) {
if (exponent & 1) {
result = (result * base) % modulus;
}
exponent >>= 1;
base = (base * base) % modulus;
}
return result;
}
long long modular_inverse(long long a, long long m) {
/* Extended Euclidean algorithm */
long long m0 = m, t, q;
long long x0 = 0, x1 = 1;
if (m == 1) return 0;
while (a > 1) {
q = a / m;
t = m;
m = a % m; a = t;
t = x0;
x0 = x1 - q * x0;
x1 = t;
}
if (x1 < 0) x1 += m0;
return x1;
}
int main() {
long long p = 23, g = 5;
long long x = 6; /* private key */
long long y = modular_exponentiation(g, x, p); /* public key */
long long message = 10;
long long k = 3; /* ephemeral key, must be random per encryption */
long long C1 = modular_exponentiation(g, k, p);
long long s = modular_exponentiation(y, k, p);
long long C2 = (message * s) % p;
printf("Ciphertext: (C1=%lld, C2=%lld)\n", C1, C2);
long long s_dec = modular_exponentiation(C1, x, p);
long long s_inv = modular_inverse(s_dec, p);
long long decrypted = (C2 * s_inv) % p;
printf("Decrypted message: %lld\n", decrypted);
return 0;
}
Sample Input and Output
Using the small example values, $p = 23$, $g = 5$, private key $x = 6$, public key $y = 8$, message $M = 10$, and ephemeral key $k = 3$, the program produces the ciphertext $(C_1, C_2) = (10, 14)$, and decrypting it recovers the original message, $10$, confirming the round trip works correctly. Running the program again with a different randomly chosen $k$ for the same message would produce a completely different ciphertext pair, illustrating ElGamal’s randomized, non-deterministic encryption property.
Optimization Techniques
I rely on a few practical techniques when using ElGamal:
- Precomputing $g^k \bmod p$ for several candidate values of $k$ ahead of time when I know I will need to encrypt multiple messages soon, reducing the perceived latency of each individual encryption.
- Using fixed-base exponentiation optimizations, since the generator $g$ is constant across many encryptions, allowing precomputed tables to speed up repeated exponentiation with the same base.
- Switching to elliptic curve variants (like ECIES) for equivalent security with dramatically smaller key sizes and faster computation, which is what most modern systems do instead of using classical multiplicative-group ElGamal directly.
- Ensuring the random number generator used for the ephemeral key $k$ is cryptographically secure, since weak randomness here is the single most damaging implementation flaw for ElGamal.
Common Mistakes
I most often see the catastrophic mistake of reusing the ephemeral key $k$ across two different messages, which allows an attacker who obtains both ciphertexts to solve for both plaintexts through simple algebra, since the mathematics reduces to solving a linear equation once $k$ is shared. I also see mistakes in choosing $g$ or $p$ poorly, such as using a generator of only a small subgroup rather than the full group, which weakens security; failing to use cryptographically secure randomness for $k$; and using textbook ElGamal directly on sensitive data without any padding or integrity protection, exposing it to malleability attacks where an adversary can manipulate the ciphertext in predictable ways without detection.
Further Reading
- Elgamal, T. “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms.” IEEE Transactions on Information Theory, 1985. https://ieeexplore.ieee.org/document/1057074
- “Handbook of Applied Cryptography” by Menezes, van Oorschot, and Vanstone. https://cacr.uwaterloo.ca/hac/
- NIST FIPS 186-5, Digital Signature Standard (DSS), which documents DSA’s relation to ElGamal. https://csrc.nist.gov/publications/detail/fips/186/5/final
- Diffie, W., and Hellman, M. “New Directions in Cryptography.” https://ee.stanford.edu/~hellman/publications/24.pdf
