Cryptology ePrint Archive: Report 2009/323

Factoring Unbalanced Moduli with Known Bits

Eric Brier and 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$.

Category / Keywords: foundations / factoring, LLL

Date: received 1 Jul 2009, last revised 1 Jul 2009

Contact author: david naccache at ens fr

Available format(s): PDF | BibTeX Citation

Version: 20090701:110016 (All versions of this report)

Short URL: ia.cr/2009/323

Discussion forum: Show discussion | Start new discussion