【摘要】 针对基于特定非交换壹半群(m,.)中的困难问题,给出了单向(陷门)函数的一种新的构造方案,即已知A和B=xAy,而求x和y的难度;选取有限域Fq上的n×n矩阵,在Fq矩阵乘法下,以所构成的非交换壹半群作为研究对象,利用Fq上“遍历矩阵”的密码学特性,提出了基于Fq上遍历矩阵的实现方案,并对可能的攻击手段进行了分析。提出了“强壮矩阵”的概念,并对给定的两个遍历矩阵Q1和Q2,给出了关于Q1,Q2的强壮矩阵的判别标准和寻找算法;由〈Q1〉,〈Q2〉以及关于Q1,Q2的强壮矩阵,可以构造相应的单向(陷门)函数。更多还原

【Abstract】 We present a new implementation of the one-way（trapdoor） functions.It is based on the difficult problem in a specific monoid（m,·） which is noncommutativ e,namely the difficulty to deduce x and y by knowing A and B=xAy.So we focus on certain monoid which is formed by all the n×n matrices over finite field F_q under multiplication.By the cryptography characteristics of "erg odic matrix" over F_q,we scheme out a method based on the ergodic matrices over F_q and then analyze the pos sible attacks.Then we introduce the concept of "strong matrix" and provide di stinguishing criterion and search algorithm of the strong matrix about two certa in ergodic matrices Q₁ and Q₂.Using 〈 Q₁〉,〈Q₂〉 and a strong matrix m about Q₁ and Q₂,we can construct a one-way（trapdoor） fun ction.更多还原