TY - GEN

T1 - Cryptanalysis of short exponent RSA with primes sharing least significant bits

AU - Sun, Hung Min

AU - Wu, Mu En

AU - Steinfeld, Ron

AU - Guo, Jian

AU - Wang, Huaxiong

PY - 2008

Y1 - 2008

N2 - LSBS-RSA denotes an RSA system with modulus primes, p and q, sharing a large number of least significant bits. In ISC 2007, Zhao and Qi analyzed the security of short exponent LSBS-RSA. They claimed that short exponent LSBS-RSA is much more vulnerable to the lattice attack than the standard RSA. In this paper, we further raise the security boundary of the Zhao-Qi attack by considering another polynomial. Our improvemet supports the result of analogue Fermat factoring on LSBS-RSA, which claims that p and q cannot share more than least significant bits, where n is the bit-length of pq. In conclusion, it is a trade-off between the number of sharing bits and the security level in LSBS-RSA. One should be more careful when using LSBS-RSA with short exponents.

AB - LSBS-RSA denotes an RSA system with modulus primes, p and q, sharing a large number of least significant bits. In ISC 2007, Zhao and Qi analyzed the security of short exponent LSBS-RSA. They claimed that short exponent LSBS-RSA is much more vulnerable to the lattice attack than the standard RSA. In this paper, we further raise the security boundary of the Zhao-Qi attack by considering another polynomial. Our improvemet supports the result of analogue Fermat factoring on LSBS-RSA, which claims that p and q cannot share more than least significant bits, where n is the bit-length of pq. In conclusion, it is a trade-off between the number of sharing bits and the security level in LSBS-RSA. One should be more careful when using LSBS-RSA with short exponents.

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

U2 - 10.1007/978-3-540-89641-8_4

DO - 10.1007/978-3-540-89641-8_4

M3 - Conference proceeding contribution

SN - 3540896406

SN - 9783540896401

VL - 5339 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 49

EP - 63

BT - Cryptology and Network Security - 7th International Conference, CANS 2008, Proceedings

A2 - Franklin, Matthew K.

A2 - Hui, Lucas Chi Kwong

A2 - Wong, Duncan S.

PB - Springer, Springer Nature

CY - Berlin

ER -