The Construct Of One-way Function Based On The Ergodic Matrix Over The Finite Field

The cryptographical theory and technology mainly include two parts: the cryptography based on mathematics(including public key cryptosystem,stream cipher, block cipher,digital signature,authentication code,Hash function,identity certification,key management,public key infrastructure etc.) and that based on non-mathematics(including information hiding,quantum cipher,identification technology based on biologic characteristics).We pay much attention to the cryptographical theory and technology based on mathematics in this article.At the present,there are two kinds of theretical foundations of the cryptographical system that is used widely:One is based on discrete logarithm problem,the other is based on polynomial factorization.The two problems are both NP problem. We make research on NP complete problem in this article. Concretely,in the given non-commutative semigroup with 1 A and B=xAy are known quantums but working out x and y is difficult . It is based on the multivariate quadratic problem over the finite field. The problem has been proved to be NP complete problem. The theory about group, ring and field is the foundation of cryptography. If n is a prime or a big prime power, we can use it construct a finite field. We call it p not n. This type of finite field is Galosi field, denoted as GF(p).(Evariste Galois was a French mathematician in the early nineteenth century. He did a lot of work in mathematics.).The rank of the finite field is always prime or integral power of prime.For interal power of every prime,there just exists a finite field GF ( pn),denoted as F pn nowadays. GF(p) represents a prime field whose rank is p,denoting 0,1,…,p-1. a=b in the prime field GF (p) means a ≡b(mod p)。Let n and (2n-1) be mutual prime,for any g=(gn …g2 g1)∈(F2)n∧(gn≠0),let g(x)=gnxn+gn-1xn-1+ …g1x+1,then Qg is an ergodic matrix if and only if g(x)|Φ2n-1(x)。Therefore the number of g∈(F2)n such that Qg is an ergodic matrix is just ?(2n-1)/n.(Φ(x) is cyclotomic polynomial,?(x) is Euler function)。Let n and (2n-1) be mutual prime,then for any g=(gn …g2 g1)∈(F2)n∧(gn≠0),Qg is an ergodic matrix if and only if Qg's period is (2n-1) under matrix multiplication over F2. For n-dimensional vector g=(gn …g2 g1)∈(F2)n,define Qg∈MnF2 as follows: 0 1 0 0 0 …0 0 0 0 1 0 0 …0 0 Qg = 0 0 0 1 0 …0 0 ┇0 0 0 0 0 …0 1 gn gn-1 …g2 g1 We get the algorithm of looking for the ergodic matrices according to the above theorem and definition: i) Choose ( gn L g2 g1) and there is even 1 in g1 , g2,L,gn and gn≠0 ii) Construct Qg according to the above definitioniii) Compute A = Qg2n iv) Judge A = Qg ∧A' speriod=2n?1 is right or not ,if it is right Qg is an ergodic matrix,or goto the step 1,continuing looking for the ergodic matrix。1. Ergodic Matrix and its Construction Let MnF2 be a set which is composed of all n*n non-singular matrices over F2 ,then MnF2 constructs a group under matrix multiplication over F2 。Suppose B n is a set which is composed of all ( 2 n ?1) non-zero n bit binary number,and for ?Q ?M n ,define a mapping f Q: B n→B n ,for ?x ∈Bn ,such that fQ ( x)=Qx.Here we regard x as a n ×1 matrix over F2 。It is easy to prove that f Qis bijective,i.e. f Qis a permutation of B n.So f Qis denoted as the following multiplication of non-iteractive alternative(including the alternative whose length is 1): f Q=(a1 1 a12L a1n1)(a 21 a22L a2n2) …(a k 1 ak2Laknk) (Ⅰ) Let Q's period be d in the group MnF2 , then (Q) ={Q ,Q2 ,L Qd ?1,Qd=E}forms the subgroup of MnF2。When f Q only has a alternative whose length is ( 2 n ?1),Q's period is ( 2 n ?1) in MnF2。And for ?x ∈Bn , the equation is always right (Q)x = B n, i.e. QxQxQxQxxnn, 2 ,L 2? 2,2?1= just exhausts B n 。It is known that Q exhaustsevery non-zero n bit binary number,and call n*n non-singular matrix Q like that in MnF2 n*n ergodic matrix over prime field F2 ,simply ergodic matrix。For the matrix over Fq,if for any non-zero column vector v∈Fqn\{0} over Fq;Qv,Q2v, …,Qqn-1v just exhausts Fqn\{0},then Q is an ergodic matrix over Fq.(Here 0=[0 0 …0]T) 2. The Advancing of Strong Matrix For the attacks to the one-way function B=Q1xAQ2y have brute force attack , given attack,and simultaneous equations attack。The simultaneous equations attack is fatal of all attacks。The attacker elaborately chooses a1, a2, …,am∈?Q1? and b1,b2, …,bm∈?Q2?,forming the following equations: B1=Q1xA1Q2y B2=Q1xA2Q2y (Here both Ak=akAbk and Bk=akBbk are known quantities) : Bm=Q1xAmQ2y In this way the attacker is likely to deduce Q1x 和Q2y from the above equations.The reason why attacker can work out Q1x and Q2y is that if the coefficient matrix T of the equations is non-singular, i.e. Rank(?Q1?A?Q2?)=n2,then we can work out Q1x and Q2y。So computing the above equations has something to do with the choice of A 。If Rank(?Q1?A?Q2?)2,the solution is not unique。So Relinearization is not a effective way. For the given ergodic matrix Q1,Q2∈FqM n×n,to make B=XAY difficult ,the matrix A should satisfy Rank(C(Q1s)AC(Q2t))