The ElGamal algorithm

This algorithm is an asymmetric version of the D-H algorithm. ElGamal aims to overcome the problems of MitM and the impossibility of the signatures for key ownership in D-H. Moreover, ElGamal (just like RSA) is an authentic asymmetric algorithm because it encrypts the message without previously exchanging the key.

The difficulty here is commonly related to solving the discrete logarithm. As we will see later, there is also a problem related to factorization.

ElGamal is the first algorithm we’ll explore that presents a new element: an integer random number, [k], that’s chosen by the sender and kept secret. It’s an important innovative element because it makes its encryption “ephemeral,” in the sense that [k] makes the encryption function unpredictable. Moreover, we will frequently see this new element related to the zero-knowledge protocol in Chapter 5, Zero-Knowledge Protocols.

Let’s look at the implementation...