Research On Parallelization Of Lattice Basis Reduction Algorithms And The Applications

Lattice basis reduction has a long history being studied as the important aspects of geometry of numbers. With the proposal of LLL algorithm, lattice basis reduction has been showing the tremendous power to cryptanalysis. Especially, it has been playing an important role in the cryptanalysis of RSA scheme and other public key cryptosystems.With the increase of dimension or the input data of a lattice, the time cost of lattice basis reduction algorithms will increase rapidly. Then, parallelization is an important way to improve the efficiency of the algorithms. When using the public key cryptosystems such as RSA, there are always some special cases such as the exposure of private key. Then the attacks on these schemes are usually equivalent to the problems of lattice basis reduction. Therefore, the research of lattice basis reduction algorithms and their applications on cryptanalysis has caught great attention of the cryptographic society. On the one hand, the implementation of lattice basis reduction algorithms pan improve their efficiency and be used to attack the cryptosystems effectively; On the other hand, the research of the applications on cryptanalysis can give us a better appreciation of the cryptosystems and indicate us to use them properly in the real environment.This thesis mainly focuses on several problems related to lattice basis reduction algorithms and their applications on public key cryptosystems, including the parallization of LLL and BKZ algorithms, the design and anslysis of lattice basis reduction algorithm based on genetic strategy, the lattice attacks on RSA given partial discrete bits of d, the lattice attacks on the cryptosystems base on discrete logarithm problem. The main results are as follows:1. A parallel scheme of LLL algorithm is given from the idea of block and is implemented on the Sunway cluster. The experimental results show that the efficiency is low because that the load of every computing unit is not balanced. BKZ algorithm is described from the view of parallelism and a parallel implementation scheme is given. Experiments also show that the speedup factor of BKZ algorithm in parallel is extremely low, and then a new parallel lattice reduction algorithm is proposed. The new algorithm can obtain a BKZ reduced basis and the parallel speedup is effective. With the practical results on Goldstein lattices and Ajtai lattices, it is shown that the new algorithm performs well for the high-dimensional lattices or large block size. The speedup factor can be40for the100-dimensional lattices. At the same time, the length of the shortest vector is smaller.2. The influence of basis order on LLL algorithm is discussed. If the suitable order is used, the cost of LLL algorithm can be decreased effectively. Based on the strategies of genetic algorithm, a new lattice basis reduction algorithm is proposed. Also, the initial population, fitness function, genetic operators and terminal condition are designed and analyzed in detail. By the new algorithm, some lattice bases of the SVP challenge are experienced and the outputs of the new algorithm can always reach or break the records on the internet which illustrates that the new algorithm behaves well.3. The constructing methods of Coppersmith are analyzed systemically and the strategies of solving modular equations are discussed. With different methods for the lattice construction, two lattice attack algorithms on RSA given partial discrete private key bits of d are obtained. If the public parameter satisfies e=Nβ and the length of unknown part of d is (1/2-β)m, the private key d can be recovered where m is the length of module number N. Also, the two algorithms are compared and analyzed. The lattices constructed by Algorithm1should be with a low density, but the dimensions are lower. Algorithm2overcomes the limit of density, but the dimensions should be much higher.4. The lattice attack on integer factorization problem is discussed. Then the dimensions of lattices for integers with different size are given and the complexity is analyzed. Based on the lattice attack on integer factorization problem, the implementation scheme for discrete logarithm problem on Zp*is proposed. Also, the lattice attack on ElGamal scheme is analyzed and an unsafe case is given with the solution to the hidden number problem. If the user choose the same random number and some bits of plaintext are exposed, the attackers can recover the complete plaintext with the solution to the hidden number problem.