Hardening the ElGamal Cryptosystem in the Setting of the Second Group of Units

Ramzi Haraty, AbdulNasser ElKassar, and Suzan Fanous

Department of Computer Science and Mathematics, Lebanese American University, Lebanon

Abstract: The Elgamal encryption scheme is best described in the setting of any finite cyclic group. Its classic case is typically presented in the multiplicative group of the ring of integers modulo a prime p and the multiplicative groups of finite fields of characteristic two. The Elgamal cryptosystem was modified to deal with Gaussian integers, and extended to work with group of units of Z_p[x]/<x²>. In this paper, we consider yet another extension to the Elgamal cryptosystem employing the second group of units of Z_n and the second group of units of Z₂[x]/<h(x)>, where h(x) is an irreducible polynomial. We describe the arithmetic needed in the new setting, and present examples, proofs and algorithms to illustrate the applicability of the proposed scheme. We implement our algorithms and conduct testing to evaluate the accuracy, efficiency and security of the modified cryptographic scheme.       

Keywords: Second group of units of z_nand z_n[x]/<h(x)>, elgamal cryptosystem, and baby step giant step attack algorithm.