ElGamal Public Key Cryptosystem

1. Alice and Bob agree on a large prime number $p$ and on an element $g$ of $\mathbb{F}^*_p$ with a large prime order.

2. Alice chooses a private key $a$, with $1 \lt a \lt p-1$, and publishes $A = g^a mod p$.

3. Bob chooses a random ephemeral key $k$.

4. He uses Alice's public key $A$ to compute $c_1 = g ^k modp$ and $c_2 = mA^kmodp$, where $m$ is the plaintext.

5. He then send $(c_1,c_2)$ to Alice.

6. To recover the plaintext $m$, Alice computes $m = (c^a_1)^{-1}c_2modp$. This works because $(c^a_1)^{-1}c_2 = g ^{-ak}mg^{ak} = m mod p$.

7. An eavesdropper has to find $k$ from $c_1$ (discrete logarithm problem).

8. A middle-man can easily manipulte $c_2$; for example, to replace $m$ by $2m$ all that is necessary is to replace $c_2$ by $2c_2 mod p$.

9. This public key cryptosystem, implemented exactly as above, has some security problems.