El Gamal is a variant of Diffie-Hellman Key Exchange# based on the difficulty of Discrete Logarithms (DLOG)# problem invented by El Gamal in 1985 1 . It consists of three components: key generation, encryption, and decryption.
Key generation is done first by selecting a random large prime number \(p\) so that calculating DLOG for it will be hard. Compute a generator \(g\) from \(Z_p^*\), then pick a random number \(x\), which would be the private key, from \(Z_{p-1}\). Compute \(y = g^x \mod p\). The public key will be \((p, g, y)\).
To encrypt the message \(M\) into ciphertext \(C\), first select a random number \(k\) from \(Z_{p-1}\), then compute the ciphertext \(C = (c_1, c_2)\) where \(c_1 = g^k \mod p\) and \(c_2 = My^k \mod p\).
To decrypt, apply the formula \(M = c_2/c_1^x \mod p = c_2 (c_1^x)^{-1} \mod p\) or \(M = c_2 c_1^{p-1-x} \mod p\) to avoid the calculation of multiplicative inverse#.
However, the above algorithm is not safe from CCA#.