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

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 *Z p of the ring of integers modulo a prime p and the multiplicative groups * 2 F m 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 Zp[x]/<x2>. In this paper, we consider yet another extension to the Elgamal cryptosystem employing the second group of units of Zn and the second group of units of Z2[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.