摘要
量子计算技术的发展对基于大整数因子分解、离散对数等问题具有交换代数结构的密码体制(如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协议给出了一些修正建议.
Advances in quantum computing technology threaten to break public key cryptosys- terns based oncommutative algebraic structures such as RSA, ECC, and EIGamal on the hardness of factoring or taking a discrete logarithm, while no quantum algorithms are found to solve certain mathematical problems on non-commutative algebraic structures until now. How to study a public key cryptosystem based on non-commutative algebraic structures is one of the most challenging issues. Kahrobaei et al. put forward a novel Habeeb-Kahrobaei-Koupparis-Shpilrain （HKKS） key exchange protocol based on an extension of a semigroup by automorphisms （more generally endomorphisms）. They proposed a non-commutative semigroup of matrices over a Galois field as platform and matrices over group rings as platform respectively. Aiming at the HKKS key agreement protocol over the platiorm--an extension of a Galois field, we show that the particular instance of the protocol suggested in their paper can be broken via four different attack methods such as a structural attack, a linearization equations attack, an overdefined systems of multivariate polynomial equations attack and a discrete logarithm method attack and that, they require polynomial time complexity to achieve the shared secret key from associated public-key respectively. In this paper, we conduct a detailed analysis on the attack methods and showed corresponding algorithmic description and efficiency analysis. Theoretic analysis shows the following conclusions： （1） the structural attack gives a polynomial time deterministic algorithm with complexity of O（n^2ω） that recovers the secret shared key from the public key, where H is a n×n matrix over a Galois field and ω≈2. 3755. （2） Due to Halmiton- Caylay theorem private key matrices H^-a ,H^a can be represented as a linear combination of the set （ I,H,H^2,…,H^n-1} and G^a can be represented as a linear combination of the set { I,G,G ^2,…, G^n-1 }, where G=HM. Two pairs of equivalent private key matrices （H
出处
《计算机学报》
EI
CSCD
北大核心
2016年第3期516-528,共13页
Chinese Journal of Computers
基金
国家自然科学基金(61303212
61170080
61202386
61332019U1135004
91018008)
国家"九七三"重点基础研究发展规划项目基金(2014CB340600)
湖北省自然科学基金(2011CDB453
2014CFB440)资助~~
关键词
密码学
抗量子计算密码
密钥交换协议
密码分析
矩阵分解
cryptography
post-quantum computational cryptography
key exchange protocol
cryptanalysis
matrix decomposition
