TY - JOUR

T1 - Trading decryption for speeding encryption in Rebalanced-RSA

AU - Sun, Hung Min

AU - Wu, Mu En

AU - Jason Hinek, M.

AU - Yang, Cheng Ta

AU - Tseng, S.

PY - 2009/9/1

Y1 - 2009/9/1

N2 - 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.

AB - 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.

KW - CRT

KW - Cryptanalysis

KW - Digital signatures

KW - Encryption

KW - Lattice basis reduction

KW - RSA

UR - http://www.scopus.com/inward/record.url?scp=68949111772&partnerID=8YFLogxK

U2 - 10.1016/j.jss.2009.04.001

DO - 10.1016/j.jss.2009.04.001

M3 - Article

AN - SCOPUS:68949111772

VL - 82

SP - 1503

EP - 1512

JO - Journal of Systems and Software

JF - Journal of Systems and Software

SN - 0164-1212

IS - 9

ER -