Offensive Security Researcher & Quantum Cryptography Analyst

ElGamal Encryption Algorithm: Working, Explanation, and Public-Key Cryptography

Abdul Wahab Junaid
ElGamal encryption algorithm and working of this algorithm

ElGamal encryption algorithm and working of this algorithm

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:

How It Works

I break ElGamal into key generation, encryption, and decryption.

  1. 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$.
  2. 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)$.
  3. 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.

  1. I choose the prime $p = 23$ and generator $g = 5$.
  2. I choose my private key $x = 6$.
  3. I compute my public key $y = 5^6 \bmod 23 = 8$.
  4. My public key is $(23, 5, 8)$, and my private key is $6$.
  5. Suppose a sender wants to encrypt the message $M = 10$. They pick a random ephemeral key $k = 3$.
  6. They compute $C_1 = 5^3 \bmod 23 = 10$.
  7. They compute $s = y^k \bmod p = 8^3 \bmod 23 = 6$.
  8. They compute $C_2 = M \times s \bmod p = 10 \times 6 \bmod 23 = 14$.
  9. The ciphertext sent to me is $(C_1, C_2) = (10, 14)$.
  10. To decrypt, I compute $s = C_1^x \bmod p = 10^6 \bmod 23 = 6$.
  11. I compute the modular inverse of $6$ modulo $23$, which is $4$, since $6 \times 4 = 24 \equiv 1 \pmod{23}$.
  12. 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

Disadvantages

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:

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

Exit mobile version