Paper 2018/930

A study on the fast ElGamal encryption

Kim Gyu-Chol and Li Su-Chol


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.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
RSAElGamalpublic keyRebalanced RSACRT
Contact author(s)
kgc841110 @ star-co net kp
2018-10-02: received
Short URL
Creative Commons Attribution


      author = {Kim Gyu-Chol and Li Su-Chol},
      title = {A study on the fast ElGamal encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2018/930},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.