On the Improvement of the BDF Attack on LSBS-RSA

An

$\left( \alpha ,\beta ,\gamma \right) $

-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:

$ed=k\cdot \varphi \left( N\right) +1$

. 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

$\gamma \leq \min \left\{ \beta ,2\alpha \right\} -\sigma $

, 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

$\gamma >\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

$\max \left\{ 2\alpha ,\beta \right\} $

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.