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

Example of ElGamal decryption by Bob


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 1 October 2016.