Research On Difficult Problems In Cryptology Base On The Ergodic Matrix

The implementation of PKI that based on mathematical can be dividedinto three general, first, on the basis of specific trapdoor one-way function,and the second is based on the Diffie-Hellman key agreement protocol, andthe third is based on Shamir three-pass protocol. These three methods arebased on the certain hard problems by which to construct the requiredone-way (trapdoor) function. But the current popular methods have beenproventobeofpolynomial timeifquantum computers practical.Soit is verynecessary and urgent to look for other alternatives. In this paper, we finishedtwo tasks based on the basic theory of ergodic matrices over the finite field,one is improving the nature of primitive polynomial, and the other isconstructing some hard problems from a new perspective, and the difficultyoftheproblemswereanalyzedandproven,theapplicationwasgivenatlast.The period of the Linear feedback shift register ( LFSR_c) is onlyconfirmed by its characteristic polynomial (or friends matrix). For eachc= ( c₁ ,…,c_n )∈F_qⁿ, the necessary condition that LFSR_c's sequence has thelargest period=qn-1 is its characteristic polynomial pc(x)is irreducible inthe F_q [x]. irreducible polynomials p (x)∈F_q[x]called primitive polynomialif the period of the p(x)is qn-1. From above , we can see that the relationshipofprimitivepolynomialand LFSR careclose.The number of n×n ergodic matrix over Fq often more than thenumber of the primitive polynomial in F_q [x]. that means more Ergodicmatrices corresponding to the same primitive polynomial, but primitivepolynomial ( Friends Matrix) that not the same must corresponding to thedifferent ergodic matrices. We can get ergodic matrix immediately by theprimitive polynomial, and even more for their basic properties. If P_m (x)isthe characteristics polynomial of the Ergodic matrix -it is primitivepolynomialin F_q[x].Fromabove,wecangetthattheergodicmatrixoverfinitefieldsandtheprimitive polynomial have very close connections, and can be derived each other.Bythebasicrelationshipofprimitivepolynomialandergodicmatrix,wegive two algorithms for searching the N-degree primitive polynomials. Wefurther determine the number of different N-degree primitive polynomial isφ( q n- 1)/n by exhaustiving friends matrices. About the characteristicpolynomial method, we have three reasonable speculate on equivalentergodicmatrixandN-thprimitivepolynomial,asfollowed:Speculate 1. Not all of the equivalent ergodic matrix corresponds tothesameprimitivepolynomial.Speculate 2. The n×n equivalent ergodic matrix of F_q can bedivided intoφ(qⁿ-1)/n groups, each with n elements and correspondstosameN-degreeprimitivepolynomial.Speculate 3. With the increase of q and n , the ergodic matrixbecome more and to find initial ergodic matrix more easily. We can findall the N-degree primitive polynomialv directly through the equivalentergodicmatrix.Exploring the nature of N-degree primitive polynomial is one key pointof this paper, and the other is the analysis and demonstration of thedifficultiesofthehardproblems.According to the nature of ergodic matrix, 5 difficult problems has beenraised,asfollowed: x∈?{1 ,2,…, qⁿ-1},byknown (Q , M,Q^xMQ^y),togetintegersxandy.Problem 1 is the discrete logarithm problem of matrix multiplication(semi-) group over Fq. As the matrix ring constructed by the n×n matrixbased over the ring (R,+,*)is (?), if the discrete logarithm problem on(?)is solvable, the discrete logarithm problem on (?)must besovabletoo,while,fortheergodicmatrix F thediscretelogarithmproblem on Fq *solvable not derived the discrete logarithm problem on( m ,?)solvable. So the difficulty of problem 1 maystronger than problemsRSA andElGmal, it also means that we can construct a cryptosystem basedonproblem1whosestrengthhigherthan RSA and ElGmal.In order to analyse the difficulty of solving problems 2 and 3, theBMQ-problem overfinitefieldshouldbeintroduced.AndBMQ-problem hasalreadybeen proved is NP-complete byus through the NP-complete problem"3-Coloring",andproblem2and3isequivalenttotheBMQ-problem,so wecan say problems 2 and 3 is NP-complete. As problems 4 and 5 is closelyrelated to problem 1+2 and 1+3 , the difficulty of the five problems areguaranteed.Although we has proved that BMQ-problem over finite field isNP-complete in theory, but this does not mean that work at anycase, and thedifficulty of solving it is lie on the choices of the finite field, and equations ,andthenumberofvariablesinequation.If the BMQ-equations E that over finite field involving a total of 2nvariablesandmequations,andeachequationhasthefollowingform:for a solution ( x₁ ,…, x_n ,y₁,…,y_n)∈F_q²ⁿ of the equations, each quadratic(x_iy_j)can be represented with a new variable z_ijthat can have n 2newvariablesandaequationswithmequations. If m? n2,allofthe z ijcanbefound first, and then we can get the solution ( x₁ ,…, x_n ,y₁,…,y_n)∈F_q²ⁿ ofthe equations E. But the vast majority of the z ijare parasitic solution , we can not get the correct solution from the vast ij z s by brute force.By the current MQ-problem solving technological, the most effectiveway is the method of relinearization by Kipnis and Shamir. Through theanalysis of this method, we can see that for the BMQ-problem, the size of qmainly impact of parameters'storage and expression, but not impact thedifficulty of solving the equations, while n and m does. Therefore, in order toenable the BMQ-problem has the expectant difficulties, we should choosesmaller q and larger n and relatively small m.The relationship between prombles 2,3,4,5 and Q_x ¹MQ₂^y is close. Ifqmq N be set to the number of matrix could be , it has only two values, oneqmq N ? q ? at the time of Rank ( Q M Q ) ? n 1 2 , the number ofwhich small N always be n(qn ?1) , and the other is ( n 1)2 /( 1)qmq N ? q ? q ? atthe time of others, which,s number big N always be 2 qn ? n(qn ?1) ?1 . Withthe increase of q and n , / big small N N increase rapidly, if we attempt to usebrute force exhaustive approach is not feasible when ( n 1)2 /( 1)qmq N ? q ? q ? .Analyzing the difficulty from each point of view, we can see theimportance of matrix M, for ergodic matrix Fqand the solving of BMQ-problem with 2n variables and m equations isdifficult, that called M strong on ((Q₁,Q₂) , written to M_s()(Q₁,Q₂)={[A|∈M^FA(Q₁,Q₂)) { | 1 2 strong on (Q₁,Q₂)} , and called it the set of strong matrix of ((Q₁,Q₂)).Wecan see that the difficulty of problem 2 is lie on the choice of M. Problems 2and 3 is difficult when M is strong. So the key of difficulty is find the strongmatrix M. The difficulty of problems 4 and 5 will be guaranteed if we can dothat.Finally, several schemas based on these difficult problems are metioned,they are for key exchange, for Shamir three transmission protocols, and forpublic key cryptography .