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

References

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.