基于F_2上遍历矩阵的Shamir三次传递协议的实现

Implementation of Shamir's Three Pass Protocol Based on Ergodic Matrix over Finite Field

给出了Shamir三次传递协议的一种新的实现方案.与已有的基于离散对数问题的实现方案不同,它是基于在特定的非交换壹半群(m,·)中,由A和B=x·A·y求解x和y的难度;为此我们选取有限域F2上的n×n矩阵在F2矩阵乘法下所构成的非交换壹半群作为研究的对象,利用F2上“遍历矩阵”的密码学特性,提出了一个基于F2上遍历矩阵的Shamir三次传递协议的实现方案,并对可能的攻击手段进行了分析.为了增加通讯的安全性,提出了“强壮矩阵”的概念,并对于给定的两个遍历矩阵Q1和Q2,给出了关于Q1,Q2的强壮矩阵的判别标准和寻找算法;利用<Q1>,<Q2>以及关于Q1,Q2的强壮矩阵m,可以构造一个单向(陷门)函数,基于该单向函数,可具体实现Shamir三次传递协议、Diffie-Hellman密钥交换协议以及常规的公钥密码.

Presented a new implementation of the Shamir＇s three-pass protocol. Being different from the existing implementation based on the discrete logarithm problem, the new realization is based on the difficulty of deducing x and y from A and B· x·A·y in a specific monoid （m,·） which is noneommutative. So we focus on the certain monoid which is formed by all the n×n matrices over finite field F2 with respect to multiplication. By the cryptography characteristics of ＂ergodic matrix＂ over F2, we propose a realization of the Shamir＇ s three-pass protocol based on the ergodic matrix over F2 and then analyze the possibility of attack. In order to increase the security of the communication, we introduce the concept of ＂strong matrix＂ . We also provide a search algorithm for the strong matrix about two certain ergodic matrices Q1 and Q2. Using 〈Q1〉, 〈Q2〉 and a strong matrix m about Q1 and Q2, we can construct a one-way（trapdoor） function, by which we can implement Shamir＇s three-pass Protocol, Diffie-Hellman key-exchange protocol, and the conventional public-key cryptography.