Private key sieves for improved attacks on RSA
Abstract
The RSA cryptosystem has been studied extensively and its insecurity in specific scenarios is well known. For instance, a sufficiently small private key allows to factorize the modulus N and break the system. Attacks like this are often based on lattice reduction for finding small roots of polynomials, but high lattice dimensions can make it difficult to achieve the theoretically proved bounds in practice. In this paper, we adapt a sieve technique originally developed for deterministic integer factorization and apply it to RSA parameters. The sieve allows for an asymptotically significant reduction of the private key search space, and can be used to decrease the bounds for the polynomial roots. We also provide a square-root speed-up of the best currently known runtime bound for factoring semiprime N=pq with small prime difference q−p.
Related
- Horizontal moments of Kloosterman sums and a density version of sieves
- Grothendieck Topologies Are Extensional Presentations of the Form of Sieves
- Multi-target hyperbolic sieves and elliptic trace obstructions
- WAMS Operations in modern power systems: A median expectation-based state estimation approach for grid resilience towards cyber attacks
- A Simple Presentation of Robust Membership Inference Attacks
BibTeX
@misc{hittmeir2026private,
title = {{Private key sieves for improved attacks on RSA}},
author = {Markus Hittmeir},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.06427},
eprint = {2611.06427},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.06427},
}
RIS
TY - UNPB
TI - Private key sieves for improved attacks on RSA
AU - Markus Hittmeir
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.06427
UR - https://arxiv.org/abs/2611.06427
AB - The RSA cryptosystem has been studied extensively and its insecurity in specific scenarios is well known. For instance, a sufficiently small private key allows to factorize the modulus N and break the system. Attacks like this are often based on lattice reduction for finding small roots of polynomials, but high lattice dimensions can make it difficult to achieve the theoretically proved bounds in practice. In this paper, we adapt a sieve technique originally developed for deterministic integer factorization and apply it to RSA parameters. The sieve allows for an asymptotically significant reduction of the private key search space, and can be used to decrease the bounds for the polynomial roots. We also provide a square-root speed-up of the best currently known runtime bound for factoring semiprime N=pq with small prime difference q−p.
ER -