Paper 2024/1329

Small Public Exponent Brings More: Improved Partial Key Exposure Attacks against RSA

Abstract

Let $(N,e)$ be a public key of the RSA cryptosystem, and $d$ be the corresponding private key. In practice, we usually choose a small $e$ for quick encryption. In this paper, we improve partial private key exposure attacks against RSA with MSBs of $d$ and small $e$. The key idea is that under such a setting we can usually obtain more information about the prime factors of $N$ and then, by solving a univariate modular polynomial equation using Coppersmith's method, $N$ can be factored in polynomial time. Compared to previous results, we reduce the number of the leaked bits in $d$ that are needed to mount the attack by $\log_2 (e)$ bits. For $e=65537$, previous work required an additional enumeration of 17 bits to achieve our new bound, resulting in a $2^{10}$ (or 1,024x) increase in time consumption. Furthermore, our experiments show that for a $1024$-bit modulus $N$, our attack can achieve the theoretical bound on a simple personal computer, which verifies the new method.