Elgamal

The Elgamal cryptosystem is a public key encryption scheme based on the difficulty of the discrete logarithm problem.

Setup

Choose a prime $p$ and a primitive root $g$ modulo $p$.

Bob chooses a secret key $a$ and publishes

$$A\equiv g^a(\mathrm{mod}p)$$

So the public key is $(p,g,A)$ and the private key is $a$.

Encryption

To send a message $m$ modulo $p$, Alice chooses a random integer $k$ and computes

$$\begin{array}{rl}{c}_1& \equiv g^k(\mathrm{mod}p)\\ c_2& \equiv m{A}^k(\mathrm{mod}p)\end{array}$$

These powers modulo $p$ are computed efficiently using Binary Exponentiation.

The ciphertext is the pair $(c_1,c_2)$.

Decryption

Bob computes

$$c_1^a\equiv (g^k{)}^a=g^{ka}\equiv A^k(\mathrm{mod}p)$$

and then recovers the plaintext by

$$m\equiv c_2(c_1^a{)}^{-1}(\mathrm{mod}p)$$

Security Idea

An attacker sees $g^a$ and $g^k$, but recovering $a$ or $k$ from those values requires solving a discrete logarithm problem.