Paper 2009/323 Original: eprint.iacr.org/2009/323 ↗
Factoring Unbalanced Moduli with Known Bits
Abstract
Let $n = pq > q^3$ be an RSA modulus. This note describes a LLL-based method allowing to factor $n$ given $2log_2q$ contiguous bits of $p$, irrespective to their position. A second method is presented, which needs fewer bits but whose length depends on the position of the known bit pattern. Finally, we introduce a somewhat surprising ad hoc method where two different known bit chunks, totalling $\frac32 log_2 q$ bits suffice to factor $n$.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2009-07-01: last updated
- 2009-07-01: published
- Short URL
- https://ia.cr/2009/323
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2009/323,
author = {Eric Brier and David Naccache and Mehdi Tibouchi},
title = {Factoring Unbalanced Moduli with Known Bits},
howpublished = {Cryptology {ePrint} Archive, Paper 2009/323},
year = {2009},
url = {https://eprint.iacr.org/2009/323}
}