ElGamal Encryption

Algorithm

Setup

A key-pair is based on a large, random, secure prime $p$ and a generator $g \in Z^*_p$. The public key is $(p, g, g^d \mod p)$ and the private key is $d$.

The message space $M = \{0,\dots, p-1\}$

Encryption

Encryption is performed by selecting a random integer $r$ and computing a pair: $$E_{\left(p, g, g^d\right)}\left(m\right) = (e, c)$$

where

Decryption

Given the message $(e, c)$ compute $e^{-d} = (g^r)^{-d} = g^{-dr}$, then compute $$e^{-d}\cdot c = (g^{-dr})(mg^{dr}) \equiv m \mod p$$

$e^{-d}$ is hard to compute directly, so we instead calculate $e^{p-1-d}$ which is equivalent and easy to calculate.

Back to Computer Security