基于半环的密钥交换协议的分析与设计.pdf
目录
摘要III
ABSTRACTIV
1绪论1
1.1传统公钥密码的量子威胁1
1.2基于群和环的密码方案的研究现状1
1.3基于半环的密码方案的研究现状2
1.4本文研究内容及结构安排4
2预备知识6
2.1半环的基本概念6
2.2半环的矩阵代数8
3一类热带半环密码的密码分析10
3.1DURCHEVA热带加密方案10
3.2DURCHEVA热带加密方案的密码分析11
4新的半环结构设计17
4.1数位半环的定义17
4.2数位半环的性质23
4.3数位半环多项式方程组求解24
4.4数位半环矩阵的交换性34
5基于数位半环的密钥交换协议38
I
5.1基于数位半环循环矩阵的密钥交换协议38
5.2参数选取40
5.3安全性分析42
5.3.1数位循环矩阵双边作用问题42
5.3.2共享密钥矩阵的特点44
3.3.4KU攻击分析48
6总结与展望49
6.1总结49
6.2展望50
参考文献51
致谢54
攻读硕士学位期间主要研究成果55
贵州师范大学学位论文使用授权书56
II
摘要
摘要
半环在组合数学、函数分析、拓扑、自动机、计算机理论科学、都有其广泛
的应用。由于许多半环的计算效率较高，且半环上的矩阵分解问题、多项式分解
问题、多项式方程组求解问题等被证明是NP困难的，故近年来许多学者提出了
基于半环的密码方案，然而很多半环密码方案存在安全缺陷。
本文首先对一个热带半环上的双密钥密码方案进行了密码分析，研究结果表
明，在极短时间内可以通过求解热带半环上的多项式方程组获得第一阶段的共享
密钥。第二阶段的共享密钥可以通过KU攻击获得，故该密码方案是不安全的。
其次，提出了自然数集上一类新的半环结构，即数位半环，该半环的加法和
乘法由数的数位和的大小来定义。在验证了自然数关于新的加法和乘法构成半环
之后，分析了两个子环同构的条件和子集是子半环的条件，并讨论了该半环上的
多项式方程的求解问题、矩阵交换性，然后证明了该半环上的多元二次多项式方
程组求解问题是NP困难的，并给出了在一般情形下求解多项式方程的计算复杂
度。
最后，提出了基于数位半环的密钥交换协议。在密钥交换协议中，由于数位
半环定义的特殊性，该协议能够抵抗KU攻击。从公钥矩阵和公开参数求私钥矩
阵的已知方法是求解新半环上的多项式方程组，从公共参数、公钥矩阵求解共享
矩阵的已知方法是枚举法。实验结果表明，随机选择私钥矩阵可以使公钥矩阵和
共享密钥矩阵都呈现良好的随机性。
关键词：半环；密码分析；热带矩阵的交换性；密钥交换协议；半环
方程求解
III
贵州师范大学硕士学位论文
ABSTRACT
Semiringshaveextensiveapplicationsincombinatorialmathematics,functional
analysis,topology,automatatheory,andcomputerscience.Duetotheirhigh
computationalefficiency,manysemiringsposeNP-hardproblemssuchasmatrix
decomposition,polynomialfactorization,