【摘要】：量子計算技術(shù)的發(fā)展對基于大整數(shù)因子分解、離散對數(shù)等問題具有交換代數(shù)結(jié)構(gòu)的密碼體制(如RSA、ECC和EIGamal密碼)構(gòu)成威脅,因此研究具有非交換代數(shù)結(jié)構(gòu)的密碼體制是一項富有挑戰(zhàn)性的課題.針對該課題,Kahrobaei等人于2013年將一般矩陣群環(huán)作為平臺提出了HKKS密鑰交換協(xié)議并且于2014年將有限域上的矩陣群作為平臺介紹該HKKS密鑰交換協(xié)議.該文針對基于有限域上矩陣群的HKKS密鑰交換協(xié)議,提出了4種攻擊方法:結(jié)構(gòu)攻擊、線性化方程組攻擊、超定多變量方程組攻擊和離散對數(shù)方法攻擊,并且分別給出了對應的算法描述和有效性分析.通過分析可知:(1)結(jié)構(gòu)攻擊算法是確定性算法,能夠在O(n2ω)計算復雜度內(nèi)獲得共享密鑰,其中n是矩陣H的階數(shù),ω≈2.3755;(2)線性化方程組攻擊和超定多變量方程組攻擊都利用Halmiton-Caylay定理將HKKS協(xié)議中私鑰矩陣對(Ha,(HM)a)和(H-a,(HM)a)進行線性表示,采用線性方程組求解和XL算法求出一個相應的等價私鑰矩陣進而計算共享密鑰,這兩種攻擊方法的計算復雜度分別是O(nω+1)和O(n2ω);(3)當矩陣H(或者是矩陣HM)的特征多項式可約時,離散對數(shù)方法利用伴侶矩陣的性質(zhì)分析P-HKKS問題進而求出該協(xié)議的私鑰a(或者b),分析該方法的計算復雜度是O(n4).與此同時,該文分別將結(jié)構(gòu)攻擊、線性化方程組攻擊、超定多變量方程組攻擊應用到一般矩陣群環(huán)上的HKKS協(xié)議,這3種攻擊方法也分別能夠在多項式計算復雜度內(nèi)得到共享密鑰.與ACNS 2014會議上提出的線性代數(shù)攻擊方法相比,結(jié)構(gòu)攻擊方法是確定性算法并且線性化方程組攻擊的計算復雜度最低.最后,該文在給出攻擊算法的基礎(chǔ)上對HKKS協(xié)議給出了一些修正建議.
[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