ElGamal Encryption: A Comprehensive Guide
Introduced in 1985 by Taher ElGamal, ElGamal encryption is an asymmetric cryptosystem built on the Discrete Logarithm Problem (DLP) — an extension of the Diffie-Hellman key exchange. It is probabilistic: encrypting the same plaintext twice with the same public key always produces different ciphertexts, providing strong resistance to chosen-plaintext attacks.
Key Components
| Component | Description |
|---|
| Public Parameters | p (large prime), g (generator mod p) |
| Public Key | h = gx mod p |
| Private Key | x (secret exponent, 1 < x < p-1) |
| Ciphertext size | 2× plaintext size (probabilistic overhead) |
Security Parameters (2025)
| Key length | Security level | Status |
|---|
| 1024-bit | ~80-bit | Deprecated — do not use |
| 2048-bit | ~112-bit | Acceptable until 2030 |
| 3072-bit | ~128-bit | Recommended |
| 4096-bit | ~140-bit | High security |
Encryption Process
- Pick a random ephemeral key k (1 < k < p-1)
- Compute c1 = gk mod p
- Compute c2 = m × hk mod p
- Ciphertext is the pair (c1, c2)
Decryption Process
- Compute s = c1x mod p (shared secret)
- Recover message: m = c2 × s-1 mod p
ElGamal vs RSA
| Property | ElGamal | RSA |
|---|
| Security basis | Discrete logarithm | Integer factorization |
| Deterministic? | No (probabilistic) | Yes (with PKCS padding) |
| Ciphertext size | 2× plaintext | Same as key size |
| Speed | Slower (two exponentiations) | Faster decryption |
| Quantum resistance | No (Shor's algorithm) | No (Shor's algorithm) |
References
- T. ElGamal, "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms" (1985)
- NIST SP 800-57: Recommendation for Key Management
- ElGamal encryption on Wikipedia
