Steklov Institute St. Petersburg
Technische Universität München
State University St. Petersburg
Joint Advanced Student School (JASS)
Course 1: Algorithms in IT Security
St. Petersburg - Wednesday, March 30 through Saturday, April 9, 2005
The ElGamal Cryptosystem
Taher Elgamal rst described the ElGamal Cryptosystem  in an article
published in the proceedings of the CRYPTO '84, a conference on the advances
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  discovered in late
2003 we will show the importance of correct implementation of cryptographic
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.