  The difficulty of factoring large integers into primes is the basis for
cryptosystems such as RSA. Due to the widespread popularity of RSA, there have
been many proposed attacks on the factorization problem such as side-channel
attacks where some bits of the prime factors are available. When enough bits of
the prime factors are known, two methods that are effective at solving the
factorization problem are satisfiability (SAT) solvers and Coppersmith's
method. The SAT approach reduces the factorization problem to a Boolean
satisfiability problem, while Coppersmith's approach uses lattice basis
reduction. Both methods have their advantages, but they also have their
limitations: Coppersmith's method does not apply when the known bit positions
are randomized, while SAT-based methods can take advantage of known bits in
arbitrary locations, but have no knowledge of the algebraic structure exploited
by Coppersmith's method. In this paper we describe a new hybrid SAT and
computer algebra approach to efficiently solve random leaked-bit factorization
problems. Specifically, Coppersmith's method is invoked by a SAT solver to
determine whether a partial bit assignment can be extended to a complete
assignment. Our hybrid implementation solves random leaked-bit factorization
problems significantly faster than either a pure SAT or pure computer algebra
approach.
