Public key cryptography using discrete logarithms.
Part 3: ElGamal Encryption
ElGamal encryption is a method to encrypt a message $m$ based on the Diffie-Hellman Key Exchange method.
| << previous: MQV Key Agreement | next: Digital Signature Algorithm (DSA) >> |
ElGamal Encryption
ElGamal encryption [ELG85] is based on the Diffie-Hellman Key Exchange method. It uses the same domain parameters $(p,q,g)$ and private/public key pair $(b,B=g^b\bmod p)$ for a recipient B. The plaintext message to be encrypted needs to be encoded as an integer $m$ in the range $[1,p-2]$.
Algorithm: ElGamal Encryption
INPUT: Domain parameters $(p,q,g)$; recipient's public key $B$; encoded message $m$ in range $0\lt m\lt p-1$.
OUTPUT: Ciphertext $(c_1,c_2)$.
- Choose a random $k$ in the range $1\lt k\lt p-1$.
- Compute $c_1 = g^k\bmod p$
- Compute $c_2 = mB^k\bmod p$
- Return ciphertext $(c_1,c_2)$.
The ciphertext is the pair $(c_1, c_2)$, which are both about $p$ bits long. Neal Koblitz [KOB94] describes $c_2$ as the message $m$ "wearing a mask" and $c_1$ as a "clue" which can be used to remove the mask, but only by someone who knows the secret key $b$.
Algorithm: ElGamal Decryption
INPUT: Domain parameters $(p,q,g)$; recipient's private key $b$; ciphertext $(c_1,c_2)$.
OUTPUT: Message representative, $m$.
- Compute $m=c_1^{p-b-1}c_2\bmod p$
- Return $m$.
Note that $c_1^{p-b-1} = (c_1^b)^{-1}$, since, for any $c\in \mathbb{Z}_p^*$, $c^{p-b-1} = c^{-b}\cdot c^{p-1} = \left(c^b\right)^{-1}\cdot 1$, as $c^{p-1}=1$ by FLT.
▷ Why does this work?
Working modulo $p$ (i.e. append (mod $p$) to the end of every equation below), we have
$c_1 = g^k$, and
$c_2 = mB^k$
$\quad\; = m\left(g^b\right)^k$.
To decrypt, we compute
$c_1^{p-b-1}c_2 = \left(g^k\right)^{p-b-1}\cdot m\left(g^b\right)^k$, which can be rearranged
$\qquad\qquad = m\cdot\left[\left(g^{p-1}\right)^k \left(g^k\right)^{-b}\right]\cdot\left(g^k\right)^b$
$\qquad\qquad = m\cdot 1^k \cdot\left(g^k\right)^{-b}\left(g^k\right)^{b},\quad$ since $g^{p-1} = 1$ by Fermat's Little Theorem,
$\qquad\qquad = m\cdot 1,\quad$ since $\left(g^k\right)^{-b}\left(g^k\right)^{b} = 1$
$\qquad\qquad = m$.
Example of ElGamal encryption by Alice (or anyone) to Bob
- INPUT: Domain parameters $(p=283, q=47, g=60)$
- INPUT: Bob's public key, $B=216$;
- INPUT: encoded message, $m=101$, such that $0\lt m\lt p-1$.
- 1. Alice chooses a random $k=36$ in the range $[2,q-2]$
- 2. Alice computes $c_1 = g^k \bmod p = 60^{36}\bmod p = 78$.
- 3. Alice computes $c_2 = m B^k \bmod p = 101\cdot 216^{36}\bmod p = 218$.
- 4. Alice sends ciphertext $(c_1,c_2)=(78,218)$ to Bob
Example of ElGamal decryption by Bob
- INPUT: Domain parameters $(p=283, q=47, g=60)$
- INPUT: Bob's private key, $b=7$;
- INPUT: ciphertext $(c_1,c_2)=(78,218)$.
- 1. Bob computes $m = c_1^{p-b-1}c_2\bmod p$
$= 78^{283-7-1}\cdot c_2 = 116 \cdot 218 \bmod p$
$=101$
References
- [ELG85] Taher ElGamal (1985). A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, IEEE Transactions on Information Theory 31 (4): 469-472. <pdf-link>
- [KOB94] Koblitz, Neal (1994). A Course in Number Theory and Cryptography, 2nd ed., Springer, Graduate texts in mathematics; 114.
| << previous: MQV Key Agreement | next: Digital Signature Algorithm (DSA) >> |
Contact us
To comment on this page or to contact us, please send us a message.
This page first published 25 August 2013. Last updated 9 September 2025.
