| In recent years, algebraic attack is one of important techniques of cryptanalysis, mainly takes use of both algebraic properties of cryptography and existing methods of solving algebraic systems to attack cryptosystem. It can be used to attack blockciphers, streamciphers, multivariate public key cryptosystems and so on. There are two kinds of methods of algebraic attack:Grobner bases method and XL method.This paper improves and implementes a algorithm for Grobner bases of ideals of F[x,y] over a field F and MGB algorithm.The main results of this thesis are as follows:(1) Prove that when monomial order is lexicographical and after that polynomials set G is reduced and ordered, if the remainder on division of the S-polynomials of all neighbor pairs of G by G is zero, then G is a Grobner basis for ideal <G>. And a Grobner basis of an ideal with respect to the graded reverse lexicographical order is usually the easiest to compute. The improved algorithm synthesizes advantages of these two monomial orders and changes monomial orders in the computation so that it can reduce dramatically the number of the computation of S-Polynomials, finally properly and effectively gets Grobner basis. At last present experimental results comparing the behavior of our new algorithm to F4on random generated instances. The improved algorithm is faster than Magma’s implementation of F4, even ten times, and it can solve the case that Chen Yindong’s algorithm cannot.(2) Discover two cases that MGB algorithm cannot normally terminate and is unable to correctly calculate Grobner bases, analyse the reasons, and overcome these two defects by continuing to extend full partitions and a more careful partial enlargement. MGB algorithm ignores mutants that are generated in the last round and not selected in the Enlarge function. Our improved MGB algorithm finds these mutants good for speeding up the computation. Finally, improve MGB algorithm using elimination by substitution. In the computation of MGB algorithm, some polynomials of the degree one may appear, our improved algorithm eliminates some variables of equations P by these polynomials. Without increasing the degree of polynomials, it can reduce the number of variables and polynomials so that it can reduce the complexity of algorithm. This algorithm is also implemented, and finally present experimental results comparing the behavior of our new algorithm to MGB on HFE cryptosystem. The results of attacks show that the improved algorithm has less complexity than MGB’s. |
