Hardening the ElGamal cryptosystem in the setting of the second group of units

Abstract EN

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 group F2m* of finite fields of characteristic two.

The El Gamal cryptosystem was modified to deal with Gaussian integers, and extended to work with group of units of Z p [X] / < X2>.

In this paper, we consider yet another extension to the El Gamal 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.