利用有限域上的遍历矩阵构造单向函数

摘要：

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

关键词： 遍历矩阵 强壮矩阵 有限域 单向函数 函数构造

作者: 赵永哲 姜占华 黄声烈 裴士辉

作者单位: 吉林大学计算机科学与技术学院，长春130012

会议类型: 国内会议

会议名称: 2005中国计算机大会

会议地点: 武汉

会议语种:中文

在线出版日期: 2005-10-13（万方平台首次上网日期，不代表论文的发表时间）