Research On Lattice Reduction Algorithm And Knapsack Public Key Cryptosystem

A basic research method in modern cryptography is applying the problem ofmathematics to cipher design and cryptanalysis. Lattice is a linear structure and themajority of computing in lattice are linear operation, so it has a faster processingspeed. Lattice reduction algorithm is an important part of the lattice theory, and it hasbeen widely used in the design and analysis areas of cryptography.Knapsack public key cryptosystem is a well-known public key system, and theresearch on knapsack problem also combines various fields, such as informationsecurity, mathematics,and biology, so it has very extensive research prospects. At thesame time, knapsack system has higher efficiency than that of the number theory typepublic systems like RSA, and the idea of MH public key cryptography first explainsthe nature of public key cryptography algorithm. Most of all, it is especially suitablefor cases where memory,running time, or other resources are constrained.This paper focuses on some problems such as the lattice, lattice reductionalgorithms and knapsack cryptosystems. The main research contents as follows:(1) Analyze the application status of using the lattice reduction algorithm inseveral public-key cryptosystems, and summarize the methods of using latticereduction attacks on public-key cryptosystem process: generally, real cryptographyscheme are abstracted into a mathematical model, and then use the lattice algorithm tosolve this math problem.(2) Meanwhile, for the new knapsack public-key algorithm which is based onlinear indeterminate equation in two variables, we will conduct a lattice attack. Andby comparing different data which are obtained by computational experiment, get thefour aspects to ensure the security of the knapsack algorithm. The four aspects are thelength of secret key, the influence of knapsack density, the selection of initialsequence and the processing of plaintext complexity.(3) Propose an improved knapsack algorithm. It will be improved in four aspectsmentioned above. At the same time, we will perform a security analysis to theimproved knapsack algorithm. Specify the knapsack algorithm resistance to severalcommon attacks, and prove the security of the improved knapsack algorithm.According to the research described above, the innovations of this thesis are: (1) Analyze a central issue of cryptography lattice reduction theory, and describeit from the perspectives of Cryptosystem and Cryptanalysis. Summarize and concludeof the research progress at home and abroad.(2) Make a comparison of several attack schemes based on lattice theory, andpropose a lattice instance to attack the new knapsack public-key algorithm based onlinear indeterminate equation in two variables. Through the calculation analysis ofexperimental data, see how important of the length of secret key’s influence, knapsackdensity, the choice of initial sequence and the complexity of plaintext are.(3) An improved algorithm is proposed for this knapsack system which is basedon linear indeterminate equation. And the new algorithm’s security will be proved indifferent aspects. The analysis of the algorithm in this paper not only has the theoryproof, but also a large number of experimental data, so as to achieve a combination oftheory and practice.