TY - GEN

T1 - On the improvement of the BDF attack on LSBS-RSA

AU - Sun, Hung Min

AU - Wu, Mu En

AU - Wang, Huaxiong

AU - Guo, Jian

PY - 2008

Y1 - 2008

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

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

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

U2 - 10.1007/978-3-540-70500-0-7

DO - 10.1007/978-3-540-70500-0-7

M3 - Conference proceeding contribution

AN - SCOPUS:70349850769

SN - 3540699716

SN - 9783540699712

VL - 5107 LNCS

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

SP - 84

EP - 97

BT - Information Security and Privacy - 13th Australasian Conference, ACISP 2008, Proceedings

A2 - Mu, Yi

A2 - Susilo, Willy

A2 - Seberry, Jennifer

PB - Springer, Springer Nature

CY - Berlin; New York

T2 - 13th Australasian Conference on Information Security and Privacy, ACISP 2008

Y2 - 7 July 2008 through 9 July 2008

ER -