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.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- RSAFactorizationCoppersmith's methodPartial key attack
- Contact author(s)
-
fengyansong @ amss ac cn
abderrahmane nitaj @ unicaen fr
panyanbin @ amss ac cn - History
- 2024-08-26: approved
- 2024-08-25: received
- See all versions
- Short URL
- https://ia.cr/2024/1329
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1329, author = {Yansong Feng and Abderrahmane Nitaj and Yanbin Pan}, title = {Small Public Exponent Brings More: Improved Partial Key Exposure Attacks against {RSA}}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1329}, year = {2024}, url = {https://eprint.iacr.org/2024/1329} }