Key Exchange Based On Matrices Over Finite Field

Security is one of the most important problems in the communication and information system, while the cryptography is the basis for the security. The principal of public-key cryptography is exchanging information between parties without requiring a secure channel. Public-key systems are used for key exchange or distribution in symmetric cryptosystems. Except for the key exchange, other applications of public-key cryptography are digital signature and data authentication schemes. The security of cryptosystems widely used at the moment is based on the difficulty of solving three kinds of problems: the RSA scheme relis on the difficulty of factoring large integers, the EIGamal scheme is based on the discrete logarithms problem, while the hardness of solving elliptic curve discrete logarithms provide the basis for the Elliptic Curves scheme. However, the potential weaknesses of existing public key schemes are emerging. In particular techniques for factorization and solving discrete logarithm improve continually. For example, polynomial time quantum algorithms can be used to solve all above problems. So, research on new schemes based on other classes of problems is necessary. Beginning with the ergodic matrices, we have studied the property of ergodic matrices and its applications in public key cryptography. The main contents and conclusions in this dissertation can be summarized as follows:Ⅰ.The scheme of Key-exchange based on ergodic matricesThe ergodic matrices has a maximal generating set, and the result of multiplying a nonzero column vector on the left or multiplying a nonzero row vector on the right by the ergodic matrix is thoroughly divergent. Let Fm1 , m2∈Mn×n be ergodic matrices, for A∈Mn×n, m1 A does corresponding m1 transformatin to every column of A, while Am2 does corresponding m2 transformatin to every row of A。So, m1 Am2 may"disarrange"every element of A;This process can be repeated many times, i.e. m1 a Am2b(1≤a,b≤qn?1), to get a complex transformation of A. Meanwhile,As a typical 1-ring, ( M nF×qn,+,×), its multiplication of matrices is noncommutative, but its multiplication of elements in Fq is commutative. So, the property of commutative and noncommutative both exist in it. All these property of ergodic matrices can be used to construct the difficult problems, which is the core-structure of public cryptography such as key-exchange.Ⅱ. The difficult problem based on the ergodic matricesThe construction of difficult problems is very impotant, and directly related to the security of the public-key cryptosystem. In this paper, first, we proved that the bisectional multivariate quadratic equations problem on finite fields is NP-Complete; then a new diffuicult problem named two-side ergodic matrices exponentiation (TEME) is proposed, which is proved at least NP-Complete. Through analyzing we found, the difficulty of TEME is related to the choice of the middle matrix, when the middle matrix is a strong matrix, the TEME problem is difficult. In addition, based on the TEME problem, we proposed two one-way functions that can be used to construct public-key cryptosystem.Ⅲ. The applications of ergodic matrices in public-key cryptosystemPublic key encryption scheme is very important in public-key cryptosystem. Public key encryption schemes normally give two algorithms, one for encrypting which involves the user's public key, and one for decrypting which involves the user's secret or private key. The security of the public key encryption scheme can be divided into three kinds according to the target: one-way, indistinguishability and non-malleability. In this paper, we present some new public key scheme based on ergodic matrices.Ⅳ. Using the ergodic matrices to implement Shamir three pass protocolBy the difficulty of our hard problems, the new scheme of Shamir 3-pass protocol has been proposed.V. Implement and validate of the exchange solution of the key Using the actual code and the result to validate the correctness of the theory...