HKKS密钥交换协议分析

• 作者: 刘金会 吴万青 张焕国 毛少武 王后珍 贾建卫
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 密码学 抗量子计算密码 密钥交换协议 密码分析 矩阵分解
• 年，卷（期）: 2016,（3）
• 所属期刊栏目: 信息安全
• 页码范围: 516-528
• 页数: 13页
• 分类号: TP309
• 字数: 9961字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2016.00516

摘要

量子计算技术的发展对基于大整数因子分解、离散对数等问题具有交换代数结构的密码体制(如RSA、ECC和EIGamal密码)构成威胁,因此研究具有非交换代数结构的密码体制是一项富有挑战性的课题.针对该课题,Kahrobaei等人于2013年将一般矩阵群环作为平台提出了HKKS密钥交换协议并且于2014年将有限域上的矩阵群作为平台介绍该HKKS密钥交换协议.该文针对基于有限域上矩阵群的HKKS密钥交换协议,提出了4种攻击方法:结构攻击、线性化方程组攻击、超定多变量方程组攻击和离散对数方法攻击,并且分别给出了对应的算法描述和有效性分析.通过分析可知:(1)结构攻击算法是确定性算法,能够在O(n2w)计算复杂度内获得共享密钥,其中n是矩阵H的阶数,ω≈2.3755;(2)线性化方程组攻击和超定多变量方程组攻击都利用Halmiton-Caylay定理将HKKS协议中私钥矩阵对(Ha,(HM)a)和(H-a,(HM)a)进行线性表示,采用线性方程组求解和XL算法求出一个相应的等价私钥矩阵进而计算共享密钥,这两种攻击方法的计算复杂度分别是O(nω+1)和O(n2ω);(3)当矩阵H(或者是矩阵HM)的特征多项式可约时,离散对数方法利用伴侣矩阵的性质分析P-HKKS问题进而求出该协议的私钥a(或者6),分析该方法的计算复杂度是O(n4).与此同时,该文分别将结构攻击、线性化方程组攻击、超定多变量方程组攻击应用到一般矩阵群环上的HKKS协议,这3种攻击方法也分别能够在多项式计算复杂度内得到共享密钥.与ACNS 2014会议上提出的线性代数攻击方法相比,结构攻击方法是确定性算法并且线性化方程组攻击的计算复杂度最低.最后,该文在给出攻击算法的基础上对HKKS协议给出了一些修正建议.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张焕国		26	389	8.0	19.0
2	王后珍		5	35	4.0	5.0
3	刘金会	武汉大学计算机学院	5	34	3.0	5.0
4	贾建卫	武汉大学计算机学院	5	34	3.0	5.0
5	毛少武	武汉大学计算机学院	6	33	3.0	5.0
6	吴万青	武汉大学计算机学院	2	8	1.0	2.0