ElGamal Encryption and Decryption Calculator
Choose a prime p, a generator g and a private key x to get the public key, then encrypt a message with a random number k or decrypt a ciphertext pair (c₁, c₂).
How ElGamal encryption works
ElGamal, published by Taher ElGamal in 1985, is a public-key cipher built on the discrete logarithm problem, the same hard problem behind Diffie–Hellman. In fact it can be seen as a Diffie–Hellman exchange in which one side's value is the long-term public key.
Key generation: choose a prime p, a generator g and a private key x with 1 ≤ x ≤ p − 2, and publish y = gx mod p. To encrypt a message m (an integer from 1 to p − 1), pick a fresh random k and send the pair c₁ = gk mod p and c₂ = m · yk mod p.
Decryption
The receiver computes s = c₁x mod p. Because c₁x = gkx = yk, this is exactly the mask that multiplied the message. Multiplying c₂ by the modular inverse of s recovers m. The calculator shows the extended Euclidean table used for the inverse and then checks that m · s ≡ c₂.
Worked example
With p = 23, g = 5 and x = 6 the public key is y = 56 mod 23 = 8. To encrypt m = 10 with k = 3: c₁ = 53 mod 23 = 10 and c₂ = 10 · 83 mod 23 = 14. The ciphertext is (10, 14). To decrypt, s = 106 mod 23 = 6, its inverse is 4, and 14 · 4 = 56 ≡ 10 (mod 23), which returns the original message.
Properties and cautions
ElGamal is probabilistic: encrypting the same message twice with different k gives different ciphertexts, which is a security advantage over textbook RSA. The cost is that the ciphertext is twice as long as the message. The number k must be random and never reused, because two ciphertexts made with the same k reveal the ratio of the two messages. As with every tool on this site, the small parameters used here are for learning only and offer no real security.
Worked examples
These examples are computed by the same engine as the calculator above, so you can compare each step with your own working.
Encrypt m=10, k=3
- Prime p:
23 - Generator g:
5 - Private key x:
6 - Operation:
Encrypt a message - Message m (encrypt):
10 - Random number k (encrypt):
3 - c₁ (decrypt):
10 - c₂ (decrypt):
14
Ciphertext (c₁, c₂)
(10, 14)
Public key y = g^x mod p
8
Encrypting the same message again with a different random k gives a different ciphertext. k must be fresh and secret each time.
Teaching demonstration only: small primes and no padding are insecure. Never use this tool to protect real data.
Step-by-step solution
Formula used
Keys: y = g^x mod p (public), x (private)
Encrypt: c₁ = g^k mod p, c₂ = m·y^k mod p
Decrypt: m = c₂ · (c₁^x)⁻¹ mod p
CalculateKey generation
public key y = g^x mod p
y = 5^6 mod 23 = 8
Public key (p, g, y) = (23, 5, 8); private key x = 6
CalculateFirst part of the ciphertext
c₁ = g^k mod p
c₁ = 5^3 mod 23 = 10
CalculateShared mask s
s = y^k mod p
s = 8^3 mod 23 = 6
CalculateSecond part of the ciphertext
c₂ = m · s mod p
c₂ = 10 × 6 mod 23 = 60 mod 23 = 14
ResultCiphertext
(c₁, c₂) = (10, 14)
CheckVerify by decrypting
c₁^x mod p = 6 (equals s ✓)
s⁻¹ mod p = 4
c₂ · s⁻¹ mod p = 10 = m ✓
Decrypt (10, 14)
- Prime p:
23 - Generator g:
5 - Private key x:
6 - Operation:
Decrypt (c₁, c₂) - Message m (encrypt):
10 - Random number k (encrypt):
3 - c₁ (decrypt):
10 - c₂ (decrypt):
14
Public key y = g^x mod p
8
Teaching demonstration only: small primes and no padding are insecure. Never use this tool to protect real data.
Step-by-step solution
Formula used
Keys: y = g^x mod p (public), x (private)
Encrypt: c₁ = g^k mod p, c₂ = m·y^k mod p
Decrypt: m = c₂ · (c₁^x)⁻¹ mod p
CalculateKey generation
public key y = g^x mod p
y = 5^6 mod 23 = 8
Public key (p, g, y) = (23, 5, 8); private key x = 6
CalculateRecover the shared mask
s = c₁^x mod p
s = 10^6 mod 23 = 6
CalculateInvert s modulo p
s⁻¹ ≡ 4 (mod 23)
| i | q | r | s | t |
|---|
| 0 | — | 6 | 1 | 0 |
| 1 | — | 23 | 0 | 1 |
| 2 | 0 | 6 | 1 | 0 |
| 3 | 3 | 5 | -3 | 1 |
| 4 | 1 | 1 | 4 | -1 |
| 5 | 5 | 0 | -23 | 6 |
CalculateRecover the message
m = c₂ · s⁻¹ mod p
m = 14 × 4 mod 23 = 10
ResultPlaintext
m = 10
CheckVerify
m · s mod p = 10 × 6 mod 23 = 14 = c₂ ✓
p=467, g=2, x=127
- Prime p:
467 - Generator g:
2 - Private key x:
127 - Operation:
Encrypt a message - Message m (encrypt):
100 - Random number k (encrypt):
213 - c₁ (decrypt):
1 - c₂ (decrypt):
1
Ciphertext (c₁, c₂)
(29, 375)
Public key y = g^x mod p
132
Encrypting the same message again with a different random k gives a different ciphertext. k must be fresh and secret each time.
Teaching demonstration only: small primes and no padding are insecure. Never use this tool to protect real data.
Step-by-step solution
Formula used
Keys: y = g^x mod p (public), x (private)
Encrypt: c₁ = g^k mod p, c₂ = m·y^k mod p
Decrypt: m = c₂ · (c₁^x)⁻¹ mod p
CalculateKey generation
public key y = g^x mod p
y = 2^127 mod 467 = 132
Public key (p, g, y) = (467, 2, 132); private key x = 127
CalculateFirst part of the ciphertext
c₁ = g^k mod p
c₁ = 2^213 mod 467 = 29
CalculateShared mask s
s = y^k mod p
s = 132^213 mod 467 = 354
CalculateSecond part of the ciphertext
c₂ = m · s mod p
c₂ = 100 × 354 mod 467 = 35400 mod 467 = 375
ResultCiphertext
(c₁, c₂) = (29, 375)
CheckVerify by decrypting
c₁^x mod p = 354 (equals s ✓)
s⁻¹ mod p = 405
c₂ · s⁻¹ mod p = 100 = m ✓
Frequently asked questions
Why is ElGamal ciphertext twice as long as the message?
Each message number m becomes a pair (c₁, c₂) of numbers modulo p, so the ciphertext has two values for every plaintext value.
What happens if the same k is reused?
If two messages are encrypted with the same k, then c₂ / c₂′ = m / m′, so knowing one message reveals the other. k must be fresh for every encryption.
How is ElGamal different from RSA?
RSA relies on the difficulty of factoring, ElGamal on the discrete logarithm problem. ElGamal is randomized and needs no φ(n), but its ciphertexts are twice as large.
Do I need a primitive root for g?
It is the usual textbook choice because it makes the group as large as possible. In practice an element of large prime order is also fine.