The ElGamal Cryptosystem

Taher Elgamal rst described the ElGamal Cryptosystem [6] in an article published in the proceedings of the CRYPTO '84, a conference on the ad-vances of cryptology. The proposed algorithm belongs to the family of public key cryptographic algorithms. Therefore it makes use of a key separated into a public and a private part. A fundamental aspect of this system is, that the knowledge of the private part makes the decryption easy. If the private key is unknown, it is virtually impossible to decrypt the message in acceptable time. The security of ElGamal is based on the discrete logarithm problem. To encrypt and respectively decrypt a message, a discrete power is executed. This operation is ecient to compute. An attacker that seeks to decrypt an intercepted message may try to recover the private key. To this end a loga-rithm needs to be computed. No actual method exists for this, given certain requirements on the initial group are met. Under these circumstances, the encryption is secure