Trading decryption for speeding encryption in Rebalanced-RSA

Hung Min Sun*, Mu En Wu, M. Jason Hinek, Cheng Ta Yang, S. Tseng

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


In 1982, Quisquater and Couvreur proposed an RSA variant, called RSA-CRT, based on the Chinese Remainder Theorem to speed up RSA decryption. In 1990, Wiener suggested another RSA variant, called Rebalanced-RSA, which further speeds up RSA decryption by shifting decryption costs to encryption costs. However, this approach essentially maximizes the encryption time since the public exponent e is generally about the same order of magnitude as the RSA modulus. In this paper, we introduce two variants of Rebalanced-RSA in which the public exponent e is much smaller than the modulus, thus reducing the encryption costs, while still maintaining low decryption costs. For a 1024-bit RSA modulus, our first variant (Scheme A) offers encryption times that are at least 2.6 times faster than that in the original Rebalanced-RSA, while the second variant (Scheme B) offers encryption times at least 3 times faster. In both variants, the decrease in encryption costs is obtained at the expense of slightly increased decryption costs and increased key generation costs. Thus, the variants proposed here are best suited for applications which require low costs in encryption and decryption.

Original languageEnglish
Pages (from-to)1503-1512
Number of pages10
JournalJournal of Systems and Software
Issue number9
StatePublished - 1 Sep 2009


  • CRT
  • Cryptanalysis
  • Digital signatures
  • Encryption
  • Lattice basis reduction
  • RSA

Fingerprint Dive into the research topics of 'Trading decryption for speeding encryption in Rebalanced-RSA'. Together they form a unique fingerprint.

Cite this