**A study on the fast ElGamal encryption**

*Kim Gyu-Chol and Li Su-Chol*

**Abstract: **ElGamal cryptosystem is typically developed in the multiplicative group $\mathbb{Z}_p^*$ ($p$ is a prime number), but it can be applied to the other groups in which discrete logarithm problem should be computationally infeasible. Practically, instead of ElGamal in $\mathbb Z_p^*$, various variants such as ECElGamal (ElGamal in elliptic curve group), CRTElGamal (ElGamal in subgroup of $\mathbb Z_n^*$ where $n=pq$ and $p,q,(p-1)/2,(q-1)/2$ are primes) have already been used for the semantic security.
In this paper, for the fast decryption, we reduced the private CRT exponent $x_p$ ($= x mod (p - 1)$) and $x_q$ ($= x mod (q-1)$)maintaining full sized private exponent $x$ ($0<x<n$) in CRTElGamal as reducing $d_p$ ($= d mod (p - 1)$) and $d_q$ ($= d mod (q-1)$) in RSA for the fast decryption. (i.e. as in rebalanced RSA).
In this case, unlike rebalanced RSA, decryption of CRTElGamal can be done faster without losing of encryption speed. As a result, it is possible to propose the fast public key cryptosystem that has fast encryption and fast decryption.

**Category / Keywords: **public-key cryptography / RSA, ElGamal, public key, Rebalanced RSA, CRT

**Date: **received 28 Sep 2018

**Contact author: **kgc841110 at star-co net kp

**Available format(s): **PDF | BibTeX Citation

**Version: **20181002:041026 (All versions of this report)

**Short URL: **ia.cr/2018/930

[ Cryptology ePrint archive ]