Small solutions to polynomial equations, and low exponent RSA vulnerabilities (Q1382143)

The problem of computing integer roots of a polynomial nicely illustrates how a seemingly small change in the problem definition may affect complexity of computing its solution. While computing integer roots of a polynomial in a single variable over the integers is easy, in the case of a modular polynomial or polynomial in several variables, finding integer roots seems to be hard. However, by imposing additional restrictions, one can specify subclasses of instances that can be efficiently solved. The paper is about solving special cases of these problems, namely those that are restricted to the case where there exists a solution small enough. The technique used here is based on using coefficients of the polynomial to build a matrix whose rows give the basis of an integer lattice. Then lattice basis reduction techniques are used to find a hyperplane containing all the short lattice elements; its equation translates into equations that can be solved to obtain a solution of the original polynomial. These results have interesting applications in cryptanalysis of RSA encryption with small exponent or factoring an integer, in both cases given some partial information on the result. As lattice basis reduction plays a central role in the approach to solving such restricted instances, after the introduction the article begins with recalling the necessary facts about lattice basis reduction. Then, a heuristic approach to solving a modular polynomial equation by lattice basis reduction techniques is given to introduce some ideas used later on. The next three sections refine the approach and show how to make the heuristic approach work. It is proved that given a polynomial of degree \(\delta\) in one variable modulo an integer \(N\) of unknown factorization, if the desired solution is bounded above by \(\frac{1}{2} N^{1/{\delta} - \epsilon}\) then the approach described allows one to find in polynomial time all integer solutions that are less then a given upper bound. In the next two sections of the paper, applications of the result are given. Namely, it is shown that RSA encryption with small exponent when most of the message is fixed can be broken if the fixed part of the message is known and the length of the unknown part of the message is less than one-third of the length of \(N\). Also it is shown that if the message is subjected to random padding before being RSA-encrypted with an exponent of 3, then multiple encryptions of the same message (but with a different random pad) will reveal the message. The key assumption here is that the length of the random padding is less than one-ninth of the length of \(N\). In the rest of the paper, the case of a single polynomial in two variables over the integers is studied. Again, by using lattice basis reduction it is shown that if the desired solutions are suitably bounded then the problem is solvable in polynomial time. The result is then applied to the problem of factoring an integer when high-order bits of one of the factors are known. Particularly, it is shown that knowledge of the high-order \((\frac{1}{4} \log_2 N)\) bits of \(P\) is enough to find the factorization of \(N = PQ\). The same holds if low-order bits of \(P\) are known instead of high-order ones. Finally, an extension to more variables is discussed and an approach which works often but not always is outlined. The paper ends with two appendices covering some more technical aspects of material in previous sections.