ElGamal Encryption
Algorithm
Setup
A keypair 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, p1\}$
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

$e = g^r \mod p$

$c = m\left(g^d\right)^r \mod p$
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^{p1d}$
which is equivalent and easy to calculate.
Back to Computer Security