Andreas Meier

The ElGamal Cryptosystem

Abstract

Taher Elgamal rst described the ElGamal Cryptosystem [6] in an article published in the proceedings of the CRYPTO '84, a conference on the advances 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 logarithm 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. Today the ElGamal algorithm is used in many cryptographic products. The open-source software GnuPG uses ElGamal as standard for signatures. On behalf of this software and its problems with ElGamal [10] discovered in late 2003 we will show the importance of correct implementation of cryptographic algorithms. This paper will present the ElGamal Cryptosystem and will show how it is used for the encryption and decryption of secret messages as well as for signing messages in order to make them authentic. Variants of the algorithm will be shown that aim to make the algorithm more secure. Furthermore, issues in the design and implementations of the algorithm will be discussed.