Paper 2024/1331 Original: eprint.iacr.org/2024/1331 ↗

Practical Small Private Exponent Attacks against RSA

Abstract

It is well known that the best small private exponent attack against RSA is that when the private exponent $d < N^{0.292}$, one can factor the RSA modulus $N = pq$. However, the bound $N^{0.292}$ is very difficult to achieve directly since we need to deal with some lattice with very high dimension, which seems infeasible by now. Recently, Li et al. proposed a practical attack that can solve cases when $d$ approaches $N^{0.292}$ within a month for $1024$ bit $N$. In this paper, we propose an improved practical small private exponent attack by enumerating the most significant bits of $p + q$. Together with some skills in implementations, we can also achieve the bound $N^{0.292}$, but with significantly less time compared to previous work.