Paper 2009/323

Factoring Unbalanced Moduli with Known Bits

Eric Brier, David Naccache, and Mehdi Tibouchi

Abstract

Let n=pq>q3 be an RSA modulus. This note describes a LLL-based method allowing to factor n given 2log2q 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 32log2q 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
Creative Commons Attribution
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},
      url = {https://eprint.iacr.org/2009/323}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.