Paper 2026/1478
Provable Recovery of RSA Private Exponents below \(N^{11/42-\varepsilon}\)
Abstract
Wiener's continued-fraction attack gives the classical provable bound \(d<N^{1/4}\) for balanced RSA. Boneh and Durfee reached the exponent \(1-\sqrt{2}/2\approx0.2929\), but their argument relies on a heuristic independence assumption. We prove the first fully provable improvement beyond Wiener's \(1/4\) exponent: for every fixed \(\varepsilon>0\), balanced RSA with \(e=\Theta(N)\) can be factored deterministically in polynomial time whenever \(d\leq N^{11/42-\varepsilon}\).
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Contact author(s)
-
qw1234567 @ mail ustc edu cn
hghu2005 @ ustc edu cn - History
- 2026-07-23: approved
- 2026-07-20: received
- See all versions
- Short URL
- https://ia.cr/2026/1478
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/1478,
author = {Yiming Gao and Honggang Hu},
title = {Provable Recovery of {RSA} Private Exponents below \(N^{11/42-\varepsilon}\)},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/1478},
year = {2026},
url = {https://eprint.iacr.org/2026/1478}
}
