Research On The Application Of Lattice Theory & Lattice Basis Reduction Algorithm In Public-key Cryptanalysis

Lattice and lattice basis reduction theories & algorithms have been acting as efficient & versatile tools as well as playing a more and more important role in the field of cryptanalysis over the decades. Back in 1990, an attack using LLL reduction algorithm succeeded in breaking the knapsack-problem-based public-key cryptosystem in polynomial time, which is known as the first significantly successful application of the method. Since Don Coppersmith proposed his LLL algorithm-based methods which can be used for solving both univariate modular equations and bivariate equations with integer coefficients and small roots, various kinds of applications of his methods have raised to analyze the RSA cryptosystem and its variants in the past few years. For instance, the low-exponent attack on RSA proposed by Boneh & Durfee in the year 2000, the partial key exposure attacks on RSA proposed by Blomer, Ernest, the attacks on many sorts of RSA variants, etc.. Amongst these achievements, many results have been proposed most recently. All the results above lead to an undeniable fact that nowadays lattice-based methods are playing a more and more important & essential role in the field of public-key cryptanalysis(In fact, lattice-based attacks are known as one of the two most efficient in cryptanalysing RSA-based systems, the other one is the number field sieve(NFS)). Moreover, there are still incredibly many applications of the methods which are still unknown are yet to be discovered.The main achievement in this article is the improvement to the bound proposed by Coppersmith on the problem: factoring with high order bits known. According toCoppersmith, when knows [1/4log₂N] higher bits of p one can factor N withinpolynomial time. In this new approach, it was proved that when RSA private key d < 0.483, knowing a smaller fraction of p is sufficient in yielding the factorization of N in polynomial time. Despite the fact that the result is asymptotic & heuristic, it can output a valid result with an outstanding probability. Moreover, it is an efficient algorithm which can be completed in time polynomial. Besides, several new. understandings as well as some expansion to the original applications of Coppersmith's theorem, which mainly includes the analysis of more general cases, have also been proposed in the former chapter.