Cryptanalysis of short exponent RSA with primes sharing least significant bits

Hung Min Sun*, Mu En Wu, Ron Steinfeld, Jian Guo, Huaxiong Wang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

10 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationCryptology and Network Security - 7th International Conference, CANS 2008, Proceedings
EditorsMatthew K. Franklin, Lucas Chi Kwong Hui, Duncan S. Wong
Place of PublicationBerlin
PublisherSpringer, Springer Nature
Pages49-63
Number of pages15
Volume5339 LNCS
ISBN (Print)3540896406, 9783540896401
DOIs
Publication statusPublished - 2008
Event7th International Conference on Cryptology and Network Security, CANS 2008 - Hong-Kong, China
Duration: 2 Dec 20084 Dec 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5339 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other7th International Conference on Cryptology and Network Security, CANS 2008
CountryChina
CityHong-Kong
Period2/12/084/12/08

Fingerprint Dive into the research topics of 'Cryptanalysis of short exponent RSA with primes sharing least significant bits'. Together they form a unique fingerprint.

Cite this