# ElGamal Encryption: The Forgotten Public-Key Scheme **Source**: https://quantumsequrity.com/blog/elgamal-encryption-explained **Category**: Cryptography Foundations --- [← Back to Blog](../../blog.html) Cryptography Foundations # ElGamal Encryption: The Forgotten Public-Key Scheme 10 min read When most people think of public-key cryptography, they think of RSA. When they think a little harder, they think of elliptic curves. Almost nobody outside of cryptography classes thinks of ElGamal, even though it predates many widely deployed schemes and has interesting properties that show up in subtle places throughout modern cryptosystems. ElGamal encryption was published by Taher Elgamal in 1985 in a paper titled "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms." Elgamal was a doctoral student of Martin Hellman at Stanford. The scheme is the simplest example of a public-key encryption system whose security rests on the discrete logarithm problem rather than integer factorization. This article walks through what ElGamal is, why it matters even if it is rarely used directly, where it lives in OpenPGP and other legacy systems, and what its post-quantum status looks like. ## The Math in One Page ElGamal works in a finite cyclic group G of prime order q with generator g. In the original 1985 formulation, G is a subgroup of the multiplicative group of integers modulo a prime p. Modern variants can use elliptic curve groups, in which case the scheme is called Elliptic Curve ElGamal. The key generation: 1. Pick a random private key x in the range 1 to q-1. 2. Compute the public key y equal to g raised to the x. 3. Public parameters: (G, q, g, y). Private key: x. To encrypt a message m (where m is an element of G): 1. Pick a random ephemeral scalar k in the range 1 to q-1. 2. Compute c1 equals g raised to the k. 3. Compute c2 equals m times y raised to the k. 4. The ciphertext is the pair (c1, c2). To decrypt with private key x: 1. Compute m equals c2 divided by c1 raised to the x. The math works because c1 raised to the x equals g raised to (k times x) equals (g raised to the x) raised to the k equals y raised to the k. So c2 divided by c1 raised to the x equals m times y raised to the k divided by y raised to the k equals m. The security argument: recovering m from (c1, c2) without x requires either solving the discrete log problem (find x given g and y, which is hard for large groups) or solving the Diffie-Hellman problem (compute g raised to (a times b) given g raised to the a and g raised to the b, which is also hard). ## Why ElGamal Was Important ElGamal was the first published scheme that demonstrated a clean, practical public-key encryption system based on the discrete logarithm problem. Diffie and Hellman had introduced the concept of public-key cryptography in 1976 with their key-exchange protocol, but the original Diffie-Hellman is a key agreement, not an encryption scheme. RSA (1977) was an encryption scheme but rests on integer factorization, a different hard problem. ElGamal connected the dots: take Diffie-Hellman, add an extra multiplication, and you get a working encryption system. The construction influenced almost every subsequent discrete-log-based encryption scheme, including elliptic curve variants and signature schemes derived from the same technique. The companion signature scheme in Elgamal's 1985 paper directly inspired DSA, which was standardized by NIST in 1994. Read more in [DSA Legacy Status](dsa-legacy-status). ## ElGamal in OpenPGP ElGamal lived its longest practical life inside OpenPGP. PGP and GnuPG use ElGamal as one of the supported public-key encryption algorithms, alongside RSA. When you generate a PGP key with the default settings, you might get a primary signing key (DSA or RSA) and a separate ElGamal subkey for encryption. The combination "DSA primary + ElGamal subkey" was popular in the 2000s and early 2010s because both schemes have classical security based on discrete logs and were free of patent encumbrances during the era when RSA was patented (the patent expired in 2000). OpenPGP key types as defined in RFC 9580 (2024) and earlier RFCs include: - 1: RSA (encrypt and sign). - 2: RSA (encrypt only). - 3: RSA (sign only). - 16: ElGamal (encrypt only). - 17: DSA (sign only). - 18: ECDH on a named curve. - 19: ECDSA on a named curve. - 22: EdDSA (Ed25519 in legacy, Ed25519/Ed448 in modern). By 2026, most new OpenPGP keys are ECDH+EdDSA pairs (curve25519-based). Legacy ElGamal keys remain valid for decrypting old messages but new keys should be elliptic-curve based. ## The Ciphertext Expansion Problem ElGamal has a notable inefficiency: the ciphertext is twice as long as the plaintext (well, twice the group element size). RSA-OAEP produces ciphertexts the same size as the modulus. ElGamal-2048 produces ciphertexts that are 4096 bits long for a 2048-bit modulus. This is why ElGamal in practice almost always operates on a small symmetric key, not on the actual plaintext. The hybrid pattern is: 1. Generate a random 256-bit symmetric key K. 2. Encrypt the actual plaintext under K with a symmetric cipher (typically AES-256-GCM). 3. Encrypt K with ElGamal. 4. The ciphertext is the ElGamal-encrypted K plus the symmetric ciphertext. The same hybrid pattern applies to RSA, X25519, ML-KEM, and almost every public-key encryption scheme in deployed systems. Read more in [Hybrid Encryption](hybrid-encryption) and [AES-256-GCM Explained](aes-256-gcm-explained). ## The Multiplicative Homomorphism ElGamal has an interesting property: it is multiplicatively homomorphic. If c1, c2 is the encryption of m1 and c3, c4 is the encryption of m2, then (c1 times c3, c2 times c4) is a valid encryption of m1 times m2. This property is sometimes useful in privacy-preserving protocols. For example, voting systems can encrypt vote tallies, multiply them homomorphically, and reveal only the final sum without revealing individual votes. The property is also a vulnerability if not handled carefully. ElGamal in raw form is malleable: an attacker can modify a ciphertext to produce a related plaintext without knowing the key. To fix this, modern ElGamal variants like Cramer-Shoup add additional structure to make the encryption non-malleable (IND-CCA2 secure). The Cramer-Shoup cryptosystem (1998) is essentially ElGamal with an integrity check that makes it resistant to chosen-ciphertext attacks. ## Why ElGamal Faded By the 2010s, ElGamal was a legacy choice. Three main reasons: First, RSA-OAEP is faster for the same security level on most hardware, and RSA also serves as a signature algorithm with PSS padding. A single RSA key can do both encryption and signatures (with appropriate padding), which is operationally simpler than maintaining a DSA primary plus an ElGamal subkey. Second, elliptic-curve cryptography (ECDH and ECDSA) is much faster and produces much smaller keys. A 2048-bit ElGamal key gives roughly 112 bits of classical security. A 256-bit ECDH key gives 128 bits of classical security with 8x smaller keys. The arithmetic is cleaner. Third, the academic community moved on. Most modern protocol designs use elliptic curves or post-quantum primitives. New publications about ElGamal are rare; new publications about lattice-based encryption appear weekly. By 2026, ElGamal is mostly a teaching example for cryptography courses and a legacy bullet in OpenPGP key formats. ## ElGamal vs RSA: A Quick Comparison For the same security level (say, 112 bits classical): - RSA-2048: 2048-bit modulus, 256-byte signatures and ciphertexts, fast verification (small e), slower signing. - ElGamal in finite field: 2048-bit prime, ciphertext is 512 bytes (twice the modulus size), comparable signing/decryption speed. - ECDH P-256: 256-bit curve, 32-byte keys, much faster. - X25519: 256-bit curve, 32-byte keys, even faster. ElGamal's ciphertext expansion is the killer in size-constrained protocols. Smartcards, embedded devices, and high-volume TLS connections cannot afford to send 512 bytes when 256 will do. ## Quantum Vulnerability ElGamal is broken by Shor's algorithm on a sufficiently large quantum computer. The discrete log problem in finite fields is no harder than integer factorization for quantum attackers. A 2048-bit ElGamal prime is roughly equivalent to RSA-2048 against Shor's: both fall to a quantum computer with a few thousand logical qubits. The harvest-now-decrypt-later threat applies to ElGamal just as it does to RSA. Anything encrypted with ElGamal today can be recorded by an adversary and decrypted in the 2030s when quantum computers come online. Read more in [Harvest Now Decrypt Later](harvest-now-decrypt-later). OpenPGP has been gradually phasing out ElGamal in favor of post-quantum primitives. The OpenPGP working group has been discussing post-quantum extensions since 2022, with ML-KEM-based encryption subkeys appearing in draft specifications. The NIST PQC standardization (FIPS 203 for ML-KEM, finalized 2024) gives the working group an algorithm to standardize on. ## Elliptic Curve ElGamal A natural variant of ElGamal replaces the multiplicative group of integers modulo p with an elliptic curve group. The construction is conceptually identical: pick a random scalar k, compute c1 equals k times G (where G is the curve generator), compute c2 equals M plus k times Y (where Y is the public point and M is the message encoded as a curve point), and the ciphertext is the pair. Elliptic Curve ElGamal has the same multiplicative homomorphism as the original (it becomes additive in the elliptic curve group). It is sometimes used in privacy-preserving voting and anonymous credentials. The size advantage over finite-field ElGamal is significant: a 256-bit elliptic curve gives 128-bit security with 32-byte keys, versus a 2048-bit finite field that gives only 112-bit security with 256-byte keys. But Elliptic Curve ElGamal is rarely used directly in modern protocols. For elliptic-curve key encapsulation, ECIES (RFC 9180 HPKE in modern form) and ECDH-based hybrid schemes have replaced it. ## Cramer-Shoup and IND-CCA2 Security The original ElGamal is malleable (a chosen-ciphertext attacker can modify ciphertexts to produce related plaintexts). For provable security against adaptive chosen-ciphertext attacks (IND-CCA2), the Cramer-Shoup cryptosystem (1998) extends ElGamal with additional verification. Cramer-Shoup uses two extra public-key elements and adds a hash-based check during decryption. The result is a scheme that is provably secure under standard assumptions, without requiring random oracles. It is one of the few public-key schemes with an IND-CCA2 proof in the standard model. In practice, Cramer-Shoup is rarely deployed because RSA-OAEP and modern post-quantum schemes provide IND-CCA2 with simpler constructions and better performance. But the existence of Cramer-Shoup demonstrates that ElGamal's structural weaknesses can be patched with extra machinery. ## What QNSQY Uses QNSQY does not use ElGamal in any role. The encryption pipeline is: 1. Hybrid key encapsulation: ML-KEM (post-quantum) plus X25519 (classical) produce a shared secret. 2. The shared secret is used as a 256-bit AEAD key. 3. AEAD encryption with AES-256-GCM protects the plaintext. This avoids the ciphertext expansion of ElGamal and provides post-quantum security at the same time. Read more in [Hybrid Encryption](hybrid-encryption) and [ML-KEM Explained](ml-kem-explained). ## Recommendations for Today For new systems: do not use ElGamal. Use ML-KEM (post-quantum) combined with X25519 (classical) for key encapsulation, and AES-256-GCM or ChaCha20-Poly1305 for the symmetric layer. For interoperability with legacy OpenPGP: ElGamal subkeys remain valid for decryption of old messages. New keys should be Curve25519-based (ECDH plus EdDSA). Future versions will support ML-KEM hybrid encryption when the working group standardizes the format. For academic study: ElGamal remains an excellent teaching tool. The math is clean, the security argument is straightforward, and the homomorphic property leads naturally to advanced topics like Paillier and lattice-based encryption. For long-term confidential data: ElGamal alone is not safe. Anything encrypted today must assume an eventual quantum adversary. Hybrid post-quantum is the only safe choice. ## FAQ **Is ElGamal still used in 2026?** Mostly in legacy OpenPGP keys. Not used in new TLS, SSH, or VPN deployments. Some academic and research systems still use ElGamal for its homomorphic properties. **What is the difference between ElGamal encryption and the ElGamal signature scheme?** The encryption scheme uses a fresh random scalar to mask the plaintext. The signature scheme uses a similar structure to bind a hash of the message to the signer's identity. Both are based on discrete logs but produce different output shapes. DSA is essentially the ElGamal signature scheme with optimizations. **Can ElGamal be used for digital signatures?** The original ElGamal signature scheme is rarely used directly. DSA, which is a refinement of the ElGamal signature, was standardized by NIST in 1994 and is itself now deprecated as of FIPS 186-5. Modern signature schemes are ECDSA, EdDSA, and ML-DSA. Read more in [DSA Legacy Status](dsa-legacy-status). **Why is ElGamal ciphertext twice the size of the plaintext?** Because the ciphertext is a pair of group elements (c1, c2), each the size of a group element. The first element communicates the ephemeral public key; the second element communicates the masked plaintext. **Is ElGamal quantum-safe?** No. Like RSA and ECDH, ElGamal is broken by Shor's algorithm on a sufficiently large quantum computer. Quantum-safe alternatives are ML-KEM and post-quantum lattice schemes. ## Sources 1. Taher Elgamal, "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms" (IEEE Trans. on Inf. Theory, 1985). 2. IETF RFC 9580: OpenPGP. https://www.rfc-editor.org/rfc/rfc9580 3. NIST FIPS 186-5: Digital Signature Standard (DSS). https://csrc.nist.gov/pubs/fips/186-5/final 4. NIST FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard. https://csrc.nist.gov/pubs/fips/203/final 5. Cramer and Shoup, "A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack" (Crypto 1998). https://www.iacr.org/archive/crypto1998/14620013/14620013.pdf 6. Diffie and Hellman, "New Directions in Cryptography" (IEEE Trans. on Inf. Theory, 1976). https://ee.stanford.edu/~hellman/publications/24.pdf ## Related Articles - [DSA Legacy Status](dsa-legacy-status) - [Why RSA-2048 Will Break](why-rsa-2048-will-break) - [What Is Post-Quantum Cryptography](what-is-post-quantum-cryptography) - [Hybrid Encryption](hybrid-encryption) - [ML-KEM Explained](ml-kem-explained) --- ### Protect Your Data Before Q-Day Arrives QNSQY's NIST-standardized post-quantum encryption protects files against both current and quantum-era threats. [Try QNSQY](../../pricing.html)