Paper 2026/1478 Original: eprint.iacr.org/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.
- History
- 2026-09-22: last updated
- 2026-07-20: published
- Short URL
- https://ia.cr/2026/1478
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}