ElGamal Public-Key Cryptosystem in Multiplicative Groups of Quotient Rings of Polynomials over Finite Fields

A. N. El-Kassar, Ramzi A. Haraty

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 $Z_p^*$ of the ring of integers modulo a prime p, and the multiplicative groups $F_{2^m}^*$ of finite fields of characteristic two. The later requires finding irreducible polynomials $h(x)$ and constructing the quotient ring $Z_2{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 $Z_2{x}/$. 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 $Z_2{x}/$, where $h(x)=h_1(x)h_2(x)...h_r(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 $F_{2^m}^*$ are made.