Ergodic Matrices And Their Applications In Cryptography

With the development of Internet and e-commerce, information securitytechnology has become more and more important. Encipher is the vital methodwhich is widely used in Internet and e-commerce. In security service, we canguarantee the safety of network information communication through proper enciphertechnology and management.At present, the most practical encipher technology paid close attention to atpresent is PKI technology. In foreign countries PKI has started to be applied in manyareas, there are many manufacturers that develop PKI. A lot of producers, forinstance Baltimore, Entrust, etc. have put out the PKI products, some companiessuch as VerySign have already begun to offer PKI service. A lot of networks areusing PKI technology to guarantee authentication, undeniable, decipher, encipherand key management.The implementation scheme of PKI based on mathematics can be divided intothree kinds on the whole: First, on the basis of specific one-way trapdoor function;Second, on the basis of Diffie-Hellman protocol; Third, on the basis of Shamir'sthree-pass protocol. Realizing these three kinds of schemes needs a specific hardquestion to construct the one-way (trapdoor) function. Two kinds of public keysystems popular at present such as RSA and ECC have been proved to be solvable inpolynomial time, so if quantum computer is pratical and feasible, these kinds ofcryptosystem must be insecure. Therefore, looking for other schemes to substitutethe present ones has become extraordinarily necessary and urgent.At present, a substitutable scheme is based on multivariate quadratic polynomialquestion over finite fields. This question has already been proved to be anNP-complete problem. But different hard problems correspond to different cryptotechnology. So the key of creating different crypto technological lies in how to selecta specific hard problem. For this reason, this thesis provides a new way to construct ahard problem. The basic thought is as follows:Suppose there is a non-empty set M, KL, KR, where KL?M, KR?M, if there is abinary operation ? to make that: (4) (M,?) is a monoid, its identity unit is e (5) (KL,?) and (KR,?) are Abelian groups, their identity units are also e (6) for a,b∈M, we usually have: (a?b)≠(b?a), i.e. operation ? has no commutative law in M then we can construct a function f: KL×M×KR→M (f(a,x,b)=a?x?b), then wehave: (5) known that x∈M,a∈KL,b∈KR; it's easy to compute y=f(a,x,b) (6) if |KL| and |KR| are relatively big, known that x,y∈M, it's probably hard to find a∈KL,b∈KR and make y=f(a,x,b) (7) for any x∈M, a1,a2∈KL, b1,b2∈KR; we always have: f(a2, f(a1,x,b1),b2)= f(a1, f(a2,x,b2), b1) (8) known that a∈KL and b∈KR, it's easy to deduce a-1∈KL and b-1∈KR, and for any x∈M, we always have: f(a-1, f(a,x,b),b-1)=x If property (2) is true, then by (1) and (2) we know that the function f hasone-way property. (2) and (3) indicate that f can implement techniques likeDiffie-Hellman key exchange. (2), (3) and (4) indicate that f can implement Shamir'sthree-pass protocol. Moreover, by (3) and (4), we can use (a,b) as a "trapdoor"of theone-way function f, thereby we can implement normal public-key cryptography.Obvious that if we can construct a hard problem satisfies conditions above, then wecan get the corresponding one-way function and thus the cryptography techniquesbased on that can be developed. Therefor, let Mn Fq ×n be a set of n×n matrix over finite field Fq, then (Mn Fq ×n ,+,×)is a 1-ring, here + and ×are addition and multiplication over Fq, respectively. Wearbitrarily select two nonsingular matrices Q1 and Q2(here Q1, Q2∈Mn Fq ×n ) and let thegeneration sets, which are generated under the multiplication of Q1 and Q2 over Fq,be ?Q1? and ?Q2?, then we have: (1) (Mn Fq ×n ,×) is a monoid, its identity unit is In ×n (2) (?Q1?,×) and (?Q2?,×) are Abelian group, their identity units are also In ×n (3) for Q1 and Q2(here Q1, Q2∈Mn Fq ×n ), generally we have: Q1×Q2≠Q2×Q1. i.e.