The School of Computer Science is pleased to present...
A Hybrid SAT and Lattice Reduction Approach for Integer Factorization
MSc Thesis Defense by: Yameen Ajani
Date: Tuesday, 11 Jun 2024
Time: 1:00 PM
Location: Memorial Hall, Room 109
Abstract:
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 thesis 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 orders of magnitude faster than either a pure SAT or pure computer algebra approach.
Thesis Committee:
Internal Reader: Dr. Ahmad Biniaz
External Reader: Dr. Ilya Shapiro
Advisor: Dr. Curtis Bright
Chair: Dr. Jessica Chen
