Paper 2009/323
Factoring Unbalanced Moduli with Known Bits
Eric Brier, David Naccache, and Mehdi Tibouchi
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
- Published elsewhere. Unknown where it was published
- Keywords
- factoringLLL
- Contact author(s)
- david naccache @ ens fr
- History
- 2009-07-01: received
- Short URL
- https://ia.cr/2009/323
- License
-
CC BY
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},
note = {\url{https://eprint.iacr.org/2009/323}},
url = {https://eprint.iacr.org/2009/323}
}
