Decryption speed up of ElGamal with composite modulus.

Abstract

Public key cryptosystems such as RSA, rebalanced RSA and ElGamal have the disadvantage of serious asymmetry between encryption and decryption speed. We reduced the CRT (Chinese Remainder Theorem) exponents maintaining full sized private exponent in ElGamal with composite modulus (CRT-ElGamal) for the fast decryption as in rebalanced RSA. In this case, unlike rebalanced RSA, decryption speed up can be obtained without losing of the fast encryption speed which is comparable to RSA with small public exponent. As a result, it is possible to propose the fast public key cryptosystem in which both encryption and decryption are fast, by reducing the asymmetry (i.e., fast encryption/slow decryption) in CRT-ElGamal encryption.