7.5 The ElGamal encryption scheme

Without a doubt, you will have noticed that the Diffie-Hellman key exchange protocol is not yet a fully blown public-key scheme. While it accomplishes the task of sharing a secret over an insecure channel, which was the main motivation in thinking about public-key cryptosystems, it would still be nice to have actual encryption and decryption operations based on the discrete logarithm problem in the sense of Section 7.1.

Here, the ElGamal cryptosystem comes into play as an extension of the Diffie-Hellman key exchange protocol. The basic idea is very simple. Remember that in Diffie-Hellman key exchange, the triple PK_Alice = (g,𝔾,A) can be seen as Alice’s public key. Assume Alice has published it on her web server. Bob wants to send Alice a message, so he retrieves (g,𝔾,A). The key observation is now that as soon as Bob chooses a private key SK_Bob = β, he already knows the shared secret K_AB from the key exchange, so he might...