Abstract: The ElGamal Cryptosystem is a public-key cryptosystem based on the discrete logarithm problem over multiplicative group modulo , , where is a prime. This cryptosytem have two keys, the public key and the private key. This key-pair have four-tuple , where is a prime, is a generator of , and . The public key is 3-tuple and used for encryption. The private key is , and used for decryption.
The security of this cryptosystem is equal to the difficulty of the assosiate discrete logarithm problem for the cryptosystem. If we take a bigger prime, then the difficulty of discrete logarithm problem may increase, so the cryptosystem is more secure. In this paper, we present several algorithms for generating the public key and the private key of ElGamal Cryptosystem. The first algorithm is used to find a big prime and the second algorithm is used to find a generator of . To find a big prime, we take a primality test for a choosen integer to know that integer is prime or composite. To find a generator of , we take a test for a choosen integer.
Keywords: ElGamal cryptosystem, key-generation algorithm, public-key
(Makalah ini telah dipresentasikan pada Seminar Nasional Matematika dan Pendidikan Matematika, yang diselenggarakan oleh Universitas Muhammadiyah Malang, 30 Januari 2010)
Follow me at Twitter @uhaisnaini