# 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.
