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\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)$.
  1. Choose a random $k$ in the range $1\lt k\lt p-1$.
  2. Compute $c_1 = g^k\bmod p$
  3. Compute $c_2 = mB^k\bmod 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\bmod p$
  2. 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

Example of ElGamal decryption by Bob

References

<< 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 22 November 2019.