A new attack to RSA with small private exponent and partial information

Abstract

We give a new algorithm to attack RSA with small private exponent, when some partial information of $p+q$ is given.The algorithm is a very simple modification of original Wiener's attack with continued fractions, and allows to factor $n$ whenever $d<n^{(1+\hat{I}´)/4}$ if we know a $\hat{I}´$-fraction of the most significant bits of $p+q$. The algorithm is unconditional, which is not the case in previous improvements that use Coppersmith method. As an example, ouir algorithm can be applied to break any criptosystem with modulus of $512$ bits and $d<n^{0.3}$, giving an improvement in the original attack of Wiener.

14 pages