ElGamal Public-Key cryptosystem in multiplicative groups of quotient rings of polynomials over finite fields

Abstract

The ElGamal encryption scheme is described in the setting of any finite cyclic group G. Among the groups of most interest in cryptography are the multiplicative group Zp of the ring of integers modulo a prime p, and the multiplicative groups F2m of finite fields of characteristic two. The later requires finding irreducible polynomials H(x) and constructing the quotient ring Z2[x]/ < h(x)>. El-Kassar et al. modified the ElGamal scheme to the domain of Gaussian integers. El-Kassar and Haraty gave an extension in the multiplicative group of Zp[x]/ < x2 >. Their major finding is that the quotient ring need not be a field. In this paper, we consider another extension employing the group of units of Z2[x]/ < h(x) >, where H(x) = h1(x)h2(x)..Hr(x)is a product of irreducible polynomials whose degrees are pairwise relatively prime. The arithmetic needed in this new setting is described. Examples, algorithms and proofs are given. Advantages of the new method are pointed out and comparisons with the classical case of F2m are made.