On the improvement of the BDF attack on LSBS-RSA

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

*Corresponding author for this work

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

6 Citations (Scopus)

Abstract

An (α β, γ)-LSBS RSA denotes an RSA system with primes sharing α least significant bits, private exponent d with β least significant bits leaked, and public exponent e with bit-length γ. Steinfeld and Zheng showed that LSBS-RSA with small e is inherently resistant to the BDF attack, but LSBS-RSA with large e is more vulnerable than standard RSA. In this paper, we improve the BDF attack on LSBS-RSA by reducing the cost of exhaustive search for k, where k is the parameter in RSA equation: . Consequently, the complexity of the BDF attacks on LSBS-RSA can be further reduced. Denote σ as the multiplicity of 2 in k. Our method gives the improvements, which depend on the two cases: 1 In the case , the cost of exhaustive search for k in LSBS-RSA can be simplified to searching k in polynomial time. Thus, the complexity of the BDF attack is independent of γ, but it still increases as α increases. 1 In the case \min \left\{ \beta ,2\alpha \right\} -\sigma]] , the complexity of the BDF attack on LSBS-RSA can be further reduced with increasing α or β. More precisely, we show that an LSBS-RSA is more vulnerable under the BDF attack as increases proportionally with the size of N. In the last, we point out that although LSBS-RSA benefits the computational efficiency in some applications, one should be more careful in using LSBS-RSA.

Original languageEnglish
Title of host publicationInformation Security and Privacy - 13th Australasian Conference, ACISP 2008, Proceedings
EditorsYi Mu, Willy Susilo, Jennifer Seberry
Place of PublicationBerlin; New York
PublisherSpringer, Springer Nature
Pages84-97
Number of pages14
Volume5107 LNCS
ISBN (Print)3540699716, 9783540699712
DOIs
Publication statusPublished - 2008
Event13th Australasian Conference on Information Security and Privacy, ACISP 2008 - Wollongong, NSW, Australia
Duration: 7 Jul 20089 Jul 2008

Publication series

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

Other

Other13th Australasian Conference on Information Security and Privacy, ACISP 2008
CountryAustralia
CityWollongong, NSW
Period7/07/089/07/08

Fingerprint Dive into the research topics of 'On the improvement of the BDF attack on LSBS-RSA'. Together they form a unique fingerprint.

Cite this