HKKS密钥交换协议分析
发布时间：2018-10-13 16:24
【摘要】：量子计算技术的发展对基于大整数因子分解、离散对数等问题具有交换代数结构的密码体制(如RSA、ECC和EIGamal密码)构成威胁,因此研究具有非交换代数结构的密码体制是一项富有挑战性的课题.针对该课题,Kahrobaei等人于2013年将一般矩阵群环作为平台提出了HKKS密钥交换协议并且于2014年将有限域上的矩阵群作为平台介绍该HKKS密钥交换协议.该文针对基于有限域上矩阵群的HKKS密钥交换协议,提出了4种攻击方法:结构攻击、线性化方程组攻击、超定多变量方程组攻击和离散对数方法攻击,并且分别给出了对应的算法描述和有效性分析.通过分析可知:(1)结构攻击算法是确定性算法,能够在O(n2ω)计算复杂度内获得共享密钥,其中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(或者b),分析该方法的计算复杂度是O(n4).与此同时,该文分别将结构攻击、线性化方程组攻击、超定多变量方程组攻击应用到一般矩阵群环上的HKKS协议,这3种攻击方法也分别能够在多项式计算复杂度内得到共享密钥.与ACNS 2014会议上提出的线性代数攻击方法相比,结构攻击方法是确定性算法并且线性化方程组攻击的计算复杂度最低.最后,该文在给出攻击算法的基础上对HKKS协议给出了一些修正建议.
[Abstract]:The development of quantum computing technology poses a threat to cryptosystems with commutative algebraic structures (such as RSA,ECC and EIGamal ciphers) based on large integer factorization and discrete logarithm. Therefore, the study of cryptographic systems with noncommutative algebraic structures is a challenging subject. In order to solve this problem, Kahrobaei et al proposed the HKKS key exchange protocol based on the general matrix group ring in 2013 and introduced the HKKS key exchange protocol on the matrix group over finite fields in 2014. For the HKKS key exchange protocol based on matrix groups over finite fields, this paper proposes four attack methods: structural attack, linearized equations attack, overdetermined multivariable system attack and discrete logarithmic attack. The corresponding algorithm description and validity analysis are given respectively. The results show that: (1) the structure attack algorithm is a deterministic algorithm, which can obtain the shared key in O (N2 蠅) computational complexity. Where n is the order of matrix H, 蠅 鈮，
本文编号：2269238
[Abstract]:The development of quantum computing technology poses a threat to cryptosystems with commutative algebraic structures (such as RSA,ECC and EIGamal ciphers) based on large integer factorization and discrete logarithm. Therefore, the study of cryptographic systems with noncommutative algebraic structures is a challenging subject. In order to solve this problem, Kahrobaei et al proposed the HKKS key exchange protocol based on the general matrix group ring in 2013 and introduced the HKKS key exchange protocol on the matrix group over finite fields in 2014. For the HKKS key exchange protocol based on matrix groups over finite fields, this paper proposes four attack methods: structural attack, linearized equations attack, overdetermined multivariable system attack and discrete logarithmic attack. The corresponding algorithm description and validity analysis are given respectively. The results show that: (1) the structure attack algorithm is a deterministic algorithm, which can obtain the shared key in O (N2 蠅) computational complexity. Where n is the order of matrix H, 蠅 鈮，
本文编号：2269238
本文链接：https://www.wllwen.com/kejilunwen/xinxigongchenglunwen/2269238.html
