ElGamal signature scheme

The ElGamal signature scheme is a probabilistic digital signature algorithm based on the computational difficulty of the discrete logarithm problem in finite fields, enabling a signer to authenticate messages by producing a pair of values that can be efficiently verified using the signer's public key.^[1] Proposed by Taher ElGamal in 1985 as part of a broader public-key cryptosystem framework, it operates over a large prime modulus p and a generator g of the multiplicative group \mathbb{Z}_p^*, where security relies on the intractability of extracting logarithms without knowledge of the private key.^[1]^[2] In the scheme's key generation phase, the signer selects a private key x randomly from \{1, 2, \dots, p-2\} and computes the corresponding public key y = g^x \mod p, publishing (y, p, g) while keeping x secret.^[3] To sign a message m (typically hashed to an integer in \{0, 1, \dots, p-2\}), the signer chooses a random ephemeral value k coprime to p-1, computes r = g^k \mod p, and solves for s in the equation m \equiv x r + k s \pmod{p-1} using the extended Euclidean algorithm to find s = k^{-1} (m - x r) \mod (p-1), yielding the signature pair (r, s).^[2]^[3] Verification is performed by checking whether y^r r^s \equiv g^m \pmod{p}, which holds if the signature is valid due to the algebraic properties of the discrete logarithm.^[2] The scheme's security, under the assumption that the discrete logarithm problem is hard, ensures existential unforgeability against adaptive chosen-message attacks when parameters are chosen appropriately, though it is vulnerable to certain attacks if the random k is reused across signatures.^[2] Variants, such as those adapted to elliptic curves (EC-ElGamal), extend its applicability to modern cryptographic protocols like DSS precursors.^[1]

Introduction

Overview

The ElGamal signature scheme is a public-key digital signature scheme based on the difficulty of the discrete logarithm problem, enabling message authentication, data integrity, and non-repudiation by allowing a signer to prove ownership of a message without revealing the private key.^[1] At its core, the scheme uses public parameters including a large prime p and a generator g of the multiplicative group modulo p. The signer's private key is a random integer x, from which the public key y is derived as y = g^x \mod p. To sign a message m, the signer produces a pair (r, s) using the private key x; the verifier then uses the public key y, the message m, and the signature pair to confirm its validity without needing the private key.^[1] Unlike symmetric signatures, such as message authentication codes that rely on a shared secret key between parties, the ElGamal scheme's public-key approach eliminates the need for secure key distribution prior to verification, making it suitable for scenarios where parties have not previously exchanged secrets. The scheme serves as a foundational mechanism in cryptography, influencing variants like the Digital Signature Algorithm (DSA) standardized by NIST, which supports applications in digital certificates for entity authentication and secure communication protocols like earlier versions of TLS.^[4]^[5]

Mathematical background

The ElGamal signature scheme relies on foundational concepts from number theory and group theory, particularly in finite fields. Central to its security is the discrete logarithm problem (DLP), which states that given a large prime p, a generator g of the multiplicative group \mathbb{Z}_p^*, and an element y = g^x \mod p for some secret integer x, it is computationally infeasible to recover x when p is sufficiently large (typically on the order of 2048 bits or more). This hardness assumption underpins the difficulty of extracting private keys from public information in discrete logarithm-based cryptosystems.^[6] The multiplicative group \mathbb{Z}_p^* consists of the integers \{1, 2, \dots, p-1\} under multiplication modulo p, where p is prime. This group is cyclic of order p-1, meaning it is generated by a single element g (called a primitive root modulo p) such that the set \{ g^0, g^1, \dots, g^{p-2} \mod p \} includes every nonzero residue modulo p. The cyclicity ensures that every element has a discrete logarithm with respect to g, and the group's structure allows exponentiation to serve as a one-way function in cryptographic protocols.^[7] To incorporate arbitrary-length messages into the scheme, a collision-resistant hash function H is employed, which maps a message m to an integer H(m) in \{0, 1, \dots, p-2\}. Collision resistance means it is computationally hard to find two distinct messages m_1 \neq m_2 such that H(m_1) = H(m_2), preventing existential forgery attacks where an adversary could substitute messages without altering the hash value used in the signature. This hashing step condenses the message to fit within the exponent range of the group order p-1 while preserving security properties. Computations in the scheme require modular inverses, such as finding k^{-1} \mod (p-1) for a random integer k coprime to p-1, satisfying k \cdot k^{-1} \equiv 1 \mod (p-1). This inverse is efficiently computed using the extended Euclidean algorithm, which extends the standard Euclidean algorithm for greatest common divisors to express 1 as a linear combination of k and p-1, yielding the coefficients modulo p-1.^[8]

History

Invention

The ElGamal signature scheme was invented by Taher ElGamal in 1985, serving as an extension of his simultaneously developed public-key encryption scheme, with both relying on the hardness of the discrete logarithm problem over finite fields.^[1] This innovation addressed the growing need for efficient digital signatures in public-key cryptography, providing a scheme analogous to the Diffie-Hellman key exchange protocol while offering an alternative to earlier signature methods like those in RSA, which depend on the integer factorization problem and faced computational challenges for certain applications at the time.^[1]^[9] The scheme's development was motivated by the desire to create practical authentication mechanisms that leveraged the discrete logarithm assumption, building directly on foundational concepts from the Diffie-Hellman key exchange introduced in 1976, which had demonstrated the potential of discrete logarithms for secure key distribution without a trusted third party.^[1]^[9] ElGamal aimed to extend these ideas into a full signature system, emphasizing efficiency and security under the same computational assumptions, in contrast to knapsack-based approaches like the Merkle-Hellman scheme, by focusing squarely on discrete logarithms for broader applicability.^[1] The initial publication appeared in the paper titled "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms," first presented at the CRYPTO '84 conference in 1984 and formally published in 1985 in the IEEE Transactions on Information Theory.^[1]^[10] This work marked a pivotal step in discrete logarithm-based cryptography, establishing the ElGamal signature as a foundational primitive for subsequent developments in the field.^[1]

Influence and variants

The ElGamal signature scheme has profoundly influenced modern digital signature standards, serving as the foundational basis for the Digital Signature Algorithm (DSA) specified in the National Institute of Standards and Technology's (NIST) Digital Signature Standard (DSS), initially proposed in August 1991 and approved as Federal Information Processing Standard (FIPS) 186 in 1994.^[11] A key variant is the DSA, which adapts the ElGamal scheme for practical government and commercial use by incorporating hash functions such as SHA-1 (in early versions) and later SHA-2, along with fixed prime parameters to standardize implementation and enhance interoperability; notable differences include the use of a modular equation for the second signature component that integrates a hash of the message with the private key and a random value to bind the signature to the message content.^[12] Other variants include schemes with message recovery, such as the Nyberg-Rueppel construction, which modifies the ElGamal equations to embed part or all of the message within the signature itself, allowing the verifier to retrieve the message directly during validation without separate transmission. Probabilistic variants further evolve the original by emphasizing secure random selection of the ephemeral key k to mitigate forgery risks from predictable or reused values, ensuring each signature uses a unique, uniformly random k coprime to the order of the group. The scheme saw adoption in early cryptographic software like versions of Pretty Good Privacy (PGP) for experimental or alternative signing implementations, as well as in some blockchain protocols for transaction authentication, though its direct use has declined in favor of more efficient elliptic curve-based alternatives like ECDSA due to smaller key sizes and faster computations at equivalent security levels.^[13]^[14] Gaps in the original scheme, such as vulnerabilities from deterministic or poorly randomized k selection leading to private key recovery, are addressed in these variants through enforced randomization protocols.

Algorithm

Parameter and key generation

The ElGamal signature scheme begins with the selection of global parameters that are shared among users and form the basis for the cryptographic operations. A large prime number p, at least 2048 bits for 112-bit security or 3072 bits for 128-bit security to ensure computational security as recommended by NIST, is chosen such that p-1 has at least one large prime factor. This factorization property is crucial for resisting attacks on the underlying discrete logarithm problem. Additionally, a primitive element g (also denoted as \alpha in the original description) modulo p is selected, which serves as a generator of the multiplicative group \mathbb{Z}_p^*. The primitivity of g is verified by confirming that its order is exactly p-1, ensuring it generates the full group. These parameters p and g are publicly disclosed and fixed for the system.^[1]^[15] For each user, key generation proceeds as follows. The private key is a randomly selected integer x from the set \{1, 2, \dots, p-2\}, chosen uniformly to maintain secrecy and avoid boundary values that might simplify attacks. The corresponding public key is then computed as y = g^x \mod p. This public key y is derived directly from the private key and the system parameters, providing the necessary information for others to verify signatures without revealing x. The process relies on the hardness of the discrete logarithm problem, where computing x from y, g, and p is infeasible for large p.^[1] Security in parameter selection emphasizes the need for p-1 to include large prime factors, as subgroups of small order could otherwise allow efficient computation of discrete logarithms using algorithms like Pohlig-Hellman. The generator g must be tested to confirm its full order p-1, typically by checking that g^{(p-1)/q} \not\equiv 1 \mod p for each prime factor q of p-1. In practice, p is often chosen such that p-1 = 2q where q is another large prime, balancing security and efficiency. Once generated, the public parameters p and g, along with the user's public key y, are openly distributed via a public directory or certificate, while the private key x remains strictly confidential to the key owner.^[1]

Signature generation

To generate a signature on a message m, the signer uses the established system parameters p (a large prime number) and g (a generator of the multiplicative group \mathbb{Z}_p^*), along with their private key x.^[16] The message m is first processed through a secure cryptographic hash function H (such as SHA-256) to yield an integer h = H(m) \mod (p-1), ensuring the value fits within the range [0, p-2] for the subsequent computations.^[16] A random ephemeral integer k is then selected uniformly from the set \{1, 2, \dots, p-2\} such that \gcd(k, p-1) = 1, guaranteeing that k has a modular inverse modulo p-1.^[16] Next, compute r = g^k \mod p.^[16] Compute the modular inverse k^{-1} \mod (p-1). Then, derive s = k^{-1} (h - x r) \mod (p-1). If s = 0, select a new k and repeat the process from the computation of r.^[16] The resulting signature is the ordered pair (r, s). This process must be performed anew for each message, with a fresh random k chosen independently; failure to ensure uniqueness of k across signatures can enable recovery of the private key x from two signatures sharing the same k.^[16]

Signature verification

To verify a signature on a message m in the ElGamal signature scheme, the verifier uses the signer's public key (p, g, y), where p is a large prime, g is a generator of the multiplicative group modulo p, and y = g^x \mod p for the signer's private key x. The inputs are the message m, the signature pair (r, s), and a cryptographic hash function H (such as SHA-256).^[17] The verification process begins with a bounds check to ensure the signature components are valid: confirm that $1 \leq r \leq p-1 and $0 < s < p-1. If either condition fails, the signature is rejected immediately. This step prevents trivial forgeries and ensures the values are within the appropriate range for modular computations.^[17] Next, compute the hash value h = H(m) \mod (p-1). The verifier then calculates the left-hand side of the verification equation as g^h \mod p. Simultaneously, compute the right-hand side as y^r \cdot r^s \mod p. The signature is accepted if and only if these two values are equal:

g^{H(m)} \equiv y^r \cdot r^s \pmod{p}

Otherwise, it is rejected. This equation confirms that the signature was generated using the corresponding private key without revealing any secret information.^[17]^[1] The verification is efficient, relying solely on public information and requiring three modular exponentiations (one for y^r, one for r^s, and one for g^{H(m)}), each computable in O(\log p) time using fast exponentiation algorithms like binary exponentiation. No private key is needed, making it suitable for third-party verification, though optimizations such as simultaneous exponentiation can reduce the computational cost by approximately 40% in practice.^[17]

Correctness

Proof of correctness

To prove the correctness of the ElGamal signature scheme, consider a valid signature (r, s) generated for a message m with hash value h = H(m), where the scheme operates in the multiplicative group \mathbb{Z}_p^* with prime modulus p and generator g of order p-1. The private key is x, the public key is y = g^x \mod p, a random ephemeral key k is chosen such that \gcd(k, p-1) = 1, r = g^k \mod p, and s = k^{-1} (h - x r) \mod (p-1).^[1] The verification equation checks whether g^h \equiv y^r \cdot r^s \pmod{p}. Substituting the public key gives the right-hand side as y^r = (g^x)^r = g^{x r} \mod p. Similarly, r^s = (g^k)^s = g^{k s} \mod p. Thus, y^r \cdot r^s = g^{x r + k s} \mod p.^[1] From the signing equation, multiply both sides by k: k s \equiv h - x r \pmod{p-1}, so x r + k s \equiv x r + (h - x r) = h \pmod{p-1}. Since the order of g is p-1, it follows that g^{x r + k s} = g^h \mod p, confirming the left-hand side equals the right-hand side.^[1] This derivation relies on the properties of modular exponentiation in \mathbb{Z}_p^*, including the existence of the modular inverse k^{-1} \mod (p-1) due to \gcd(k, p-1) = 1, and the fact that exponents can be reduced modulo p-1 without altering the result for powers of g. Edge cases, such as when h - x r \equiv 0 \pmod{p-1}, are handled naturally by the arithmetic, yielding s = 0 (which is invalid and requires re-selection of k) or valid s values that still satisfy the equation.^[1]

Security analysis

Security foundations

The security of the ElGamal signature scheme rests primarily on the computational hardness of the discrete logarithm problem (DLP) in the multiplicative group \mathbb{Z}_p^*, where p is a large prime modulus. The scheme is designed such that breaking it—specifically, forging a valid signature—would enable an efficient solution to the DLP, extracting the signer's private key from the public key. This foundational assumption underpins the scheme's resistance to key recovery attacks in the classical setting. Formal security reductions for the hashed ElGamal variant, which is the commonly deployed form, establish that an existential forger under chosen-message attacks (EUF-CMA) can be transformed into an algorithm solving the DLP. By querying the forger for signatures on crafted messages, one obtains pairs (r, s) that yield linear equations modulo the group order; solving these for the private exponent x (e.g., via multiple signatures sharing ephemeral values) directly computes the discrete logarithm \log_g y = x. These reductions hold under the standard DLP assumption in \mathbb{Z}_p^*. The hash function H integrated into the scheme is essential for EUF-CMA security, requiring it to be collision-resistant to prevent adversaries from exploiting collisions to forge signatures on unrelated messages. Without this property, preimage attacks on H could allow construction of valid (r, s) pairs satisfying the verification equation without knowledge of x. Security proofs typically analyze the scheme in the random oracle model (ROM), treating H as an ideal, randomly chosen function that resists all but negligible-probability queries. Parameter selection is critical to realizing these security guarantees against known classical attacks. As of 2025, the prime p must be at least 3000 bits to achieve a security level exceeding 120 bits, providing a buffer against advances in factoring and discrete log algorithms; smaller moduli, such as 2048 bits, offer only marginal protection and are deprecated for new systems. The base g should generate a subgroup of high prime order q (at least 250 bits), typically a divisor of p-1, to avoid small subgroup attacks where an adversary confines computations to low-order elements, or Pohlig-Hellman reductions that decompose the DLP across smooth order factors.^[18] On quantum computers, the ElGamal signature scheme lacks post-quantum security, as Shor's algorithm solves the DLP in polynomial time by efficiently computing quantum Fourier transforms over the group order, allowing full key recovery from the public parameters. Consequently, it is unsuitable for long-term use in quantum-threatened environments; lattice-based digital signature schemes, such as those standardized in NIST's post-quantum cryptography suite, are advised as replacements.

Known vulnerabilities

The original unhashed ElGamal signature scheme is susceptible to existential forgery attacks, where an adversary can produce a valid signature for some message without knowledge of the private key. In the two-parameter attack, the adversary selects integers u and v with $1 < u, v < p-1 and \gcd(v, p-1) = 1, computes r = g^u y^v \mod p and s = -r v^{-1} \mod (p-1), and sets m = s u \mod (p-1). The pair (r, s) is then a valid signature for m.^[17] A critical vulnerability arises from nonce reuse, where the same ephemeral key k is used for signing two different messages m_1 and m_2. In this case, the adversary can recover the private key x using the relation x = \frac{h(m_1) s_2 - h(m_2) s_1}{r (s_2 - s_1)} \mod (p-1), derived from the signature equations s_1 k \equiv h(m_1) + x r \mod (p-1) and s_2 k \equiv h(m_2) + x r \mod (p-1).^[17] If the nonce k has low entropy—such as when only a few most or least significant bits are unknown—lattice-based attacks exploiting the Hidden Number Problem can recover the private key from sufficiently many signatures. These attacks model the partial nonce knowledge as a lattice problem, solving for x using techniques like the Coppersmith method or LLL reduction, and have been demonstrated effective even with 3-5 known bits per nonce in discrete logarithm-based schemes like ElGamal.^[19]^[20] Side-channel attacks pose implementation risks, particularly through timing or power analysis during the modular exponentiations for computing r = g^k \mod p and the modular inverse in signature generation. For instance, variations in exponentiation timing can leak information about k, enabling partial nonce recovery and subsequent key extraction via lattice methods.^[21] The original ElGamal scheme's deterministic variants (without hashing) are insecure against existential forgery, and even hashed versions become vulnerable if weak hash functions like MD5 are used, as collisions allow message manipulation. Modern implementations must employ fresh, high-entropy randomness for each k and cryptographically secure hashes to mitigate these issues.^[17] To address these vulnerabilities, variants like the Digital Signature Algorithm (DSA)—which modifies ElGamal with structured hashing and stricter parameter choices—incorporate per-signature randomness to prevent reuse and low-entropy attacks. Additionally, the scheme's reliance on the discrete logarithm problem renders it insecure against quantum adversaries using Shor's algorithm, necessitating migration to post-quantum alternatives.^[17]