F5 Algorithm Attacking BMQ System Analysis And Research

Current algebra calculation of the theoretical and applications, Grobner basis has become an indispensable tool. F[X] is the domain of multi-variable polynomial F on the ring, Grobner basis is the polynomial ring on the non-zero ideal of a special base. Buchberger in his thesis has proposed such an algorithm: Given a polynomial sequence F?F[X], compute a Grobner base G?F[X] makes the F and G generate the same ideal I. If found a G, I, just a number given on the F domain of the difficult problems becomes much easier, so Grobner basis is a good tool. May be the most basic problem is that the ideal problem: for any given a polynomial f∈F[X], determine whether f∈I set up. Of course, Grobenr base is one of the most useful application of multi-variable polynomial equation solving system, which is most interested in cryptography a problem. In fact, in such a way to solve such a system is usually the most difficult task is to find a Grobner basis.Grobner basis is useful but it is very difficult to calculate: Practice has proved that in the worst case, the calculation of the workload as the input Grobner basis polynomial increase exponentially. The good news is that in many cases make use of Grobner basis to solve problems faster, and desktop computers of all major computer algebra systems contain a similar GrobnerBasis button.Grobner basis of calculation, the basic Buchberger algorithm efficiency is not high, so many researchers working to improve the Buchberger algorithm and have found several new algorithms. According to Lazard's thinking, Jean-Charles Faugere F4 proposed algorithm to search for Grobner bases polynomial coefficient domain transformed into a linear algebra problem. This idea makes the calculation of Grobner bases much faster and achieved a lot in the application of the results. F4 implementation of several open so you can get, and this algorithm has been in the computer algebra systems have been implemented.F4 was raised, Faugere then according to Moller, Mora, and Traverso thesis put forward the idea F5 algorithm to further avoid the process of computing Grobner base excess calculations. Despite the growing literature F4, F5, but research is not published in the paper a lot. In addition Faugere papers, works only Bardet brief introduction to F5 algorithm, although this method has been published in 2002. In addition to the algorithm that, Bardet discussed the use of algebraic geometry F5 algorithm complexity theory.In this paper, we try to solve the inefficiency terms. Brief Grobner basis based upon the theory and then explore the F5 algorithm. We discuss and prove the main theoretical F5, and under certain assumptions prove correctness of the algorithm. All of these arguments are probably in the original paper presentation.Modern cryptography in a variety of rapid development of science and technology has also gained rapid development, It is in this case the contents of the thesis seems essential. Development of computer technology makes the encryption algorithm is more complex and more difficult to crack, but on the other side, computer technology, rapid development, especially of quantum computers appears likely to seriously threaten the currently password system security, there is an urgent The need to find a new password system instead of the password system has been less secure. The MQ system, the most likely attack against quantum cryptography replacement for the original, BMQ system is a special case of MQ. Grobner base is solving BMQ solving the most important part, as long as the Grobner base solved the problem, then the system is also to be cracked.MQ system is the so-called multivariate public key cryptography, the password system is based on solving multivariate polynomial group of high difficulty of the above, the BMQ system is a special case of MQ systems. BMQ system has two sets of variables, which is defined as concrete is this:Equations on a total of 2n variables E and m equations, where each equation in the form below: Seek solutions of E( x₁ ,..., x_n ),( y₁ ,..., y_n)∈F_qⁿ.We in this paper the system through the F5 algorithm attack BMQ BMQ generated data to determine the system's security. Now, I simply thought about this side of a specific description so that we more scientific analysis:In the first chapter in a brief introduction and development of cryptography, the meaning of the contents of this paper, thus introducing the F5 algorithm and BMQ system concept and gives this area of research and organizational structure. Prior knowledge in the second chapter, first introduced the paper used in the algebraic system, and then introduces the concept and use of items ordered. Introduced after the entry sequence leads us the concept of Grobner bases, and then introduces the theory of Grobner basis and the Buchberger algorithm for solving the Grobner basis. Finally, the practical application of the Grobner basis. In the third chapter F5 algorithm and implementation, this chapter first introduces the theoretical basis for F5 algorithm then gives the pseudo code implementation F5. F5 algorithm in the fourth chapter of attacks on BMQ systems analysis study, the beginning of this chapter describes BMQ system, and then attack through the F5 algorithm in the system to produce the data analysis system of safety and merits of F5 algorithm. In the fifth chapter summary and outlook in the thesis stage of the experiment, and identify future research directions.