DI Management Home > Cryptography > Public key cryptography using discrete logarithms > Part 3: ElGamal Encryption

# 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\mod 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)$.
1. Choose a random $k$ in the range $1\lt k\lt p-1$.
2. Compute $c_1 = g^k\mod p$
3. Compute $c_2 = mB^k\mod p$
4. 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$.
1. Compute $m=c_1^{p-b-1}c_2\mod p$
2. Return $m$.

Note that $c_1^{p-b-1} = (c_1^b)^{-1}$.

### ▷ 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 \mod p = 60^{36}\mod p = 78$.
• 3. Alice computes $c_2 = m B^k \mod p = 101\cdot 216^{36}\mod 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\mod p$
$= 78^{283-7-1}\cdot c_2 = 116 \cdot 218 \mod 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.