HKKS密钥交换协议分析
|
摘要
量子计算技术的发展对基于大整数因子分解、离散对数等问题具有交换代数结构的密码体制(如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 cryptosystems 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 apublic 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 theHKKS key agreement protocol over the platform——an extension of a semigroup of matrices over 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(n2ω)that recovers the secret shared key from the public key,where His a n×n matrix over a Galois field andω≈2.3755.(2)Due to HalmitonCaylay theorem,private key matrices H-a,Hacan be represented as a linear combination of the set{I,H,H2,…,Hn-1}and Gacan be represented as a linear combination of the set{I,G,G2,…,Gn-1},where G=HM.Two pairs of equivalent private key matrices(Ha,(HM)a)and(H-a,(HM)a)can be obtained by solving linear equations and XL Algorithm.Then we present two attack algorithms and they are both only require polynomial time complexity,that is to say,O(nω+1)for the linearization equations attack and O(n2ω)for the overdefined systems of multivariate polynomial equations attack,to achieve the shared secret key.(3)When the characteristic polynomial of the matrix H(or the matrix HM)is reducible,then the P-HKKS problem can be further reduced to a small set of discrete logarithm problems in an extension of the base field by using companion matrices of primitive polynomials.The private key a(or b)of HKKS key agreement protocol can be computed by an discrete logarithm attack method with the computational complexity of O(n4).At the same time,we also present that the HKKS protocol over matrix group rings is vulnerable to a structural attack,a linearization equations attack and an over defined systems of multivariate polynomial equations attack and that,they also only require polynomial time complexity respectively.Compared with a linear algebra attack proposed at ACNS 2014,the structural attack has the same computational complexity while the structural attack gives a polynomial time deterministic algorithm and computational complexity of the linearization equations attack is the smallest.In addition,we provide some improved suggestions on the HKKS protocol.
Advances in quantum computing technology threaten to break public key cryptosystems 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 apublic 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 theHKKS key agreement protocol over the platform——an extension of a semigroup of matrices over 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(n2ω)that recovers the secret shared key from the public key,where His a n×n matrix over a Galois field andω≈2.3755.(2)Due to HalmitonCaylay theorem,private key matrices H-a,Hacan be represented as a linear combination of the set{I,H,H2,…,Hn-1}and Gacan be represented as a linear combination of the set{I,G,G2,…,Gn-1},where G=HM.Two pairs of equivalent private key matrices(Ha,(HM)a)and(H-a,(HM)a)can be obtained by solving linear equations and XL Algorithm.Then we present two attack algorithms and they are both only require polynomial time complexity,that is to say,O(nω+1)for the linearization equations attack and O(n2ω)for the overdefined systems of multivariate polynomial equations attack,to achieve the shared secret key.(3)When the characteristic polynomial of the matrix H(or the matrix HM)is reducible,then the P-HKKS problem can be further reduced to a small set of discrete logarithm problems in an extension of the base field by using companion matrices of primitive polynomials.The private key a(or b)of HKKS key agreement protocol can be computed by an discrete logarithm attack method with the computational complexity of O(n4).At the same time,we also present that the HKKS protocol over matrix group rings is vulnerable to a structural attack,a linearization equations attack and an over defined systems of multivariate polynomial equations attack and that,they also only require polynomial time complexity respectively.Compared with a linear algebra attack proposed at ACNS 2014,the structural attack has the same computational complexity while the structural attack gives a polynomial time deterministic algorithm and computational complexity of the linearization equations attack is the smallest.In addition,we provide some improved suggestions on the HKKS protocol.
引文
[1]Li Hui-Xian,Chen Xu-Bao,Pang Liao-Jun,Wang Yu-Min.Certificateless multi-receiver signcryption scheme based on multivariate public key cryptography.Chinese Journal of Computers,2012,35(9):1881-1889(in Chinese)(李慧贤,陈绪宝,庞辽军,王育民.基于多变量公钥密码体制的无证书多接收者签密体制.计算机学报,2012,35(9):1881-1889)
[2]Wang H Z,Zhang H G,Wang Z Y,Tang M.Extended multivariate public key cryptosystems with secure encryption function.Science China Information Sciences,2011,54(6):1161-1171
[3]Mosca M.Post-Quantum Cryptography.Switzerland:Springer International Publishing,2014
[4]Gaborit P.Post-Quantum Cryptography.Berlin Heidelberg:Springer,2013
[5]Wang S B,Zhu Y,Ma D,et al.Lattice-based key exchange on small integer solution problem.Science China Information Sciences,2014,57(11):1-12
[6]Jarvis K,Nevins M.ETRU:NTRU over the Eisenstein integers.Designs,Codes and Cryptography,2015,74(1):1-12
[7]Cao Z.New Directions of Modern Cryptography.Boca Raton:CRC Press,2012
[8]Tsaban B.Polynomial-time solutions of computational problems in noncommutative algebraic cryptography.Journal of Cryptology,2015,28(3):601-622
[9]Armknecht F,Gagliardoni T,Katzenbeisser S,Peter A.General impossibility of group homomorphic encryption in the quantum world//Proceedings of the Public-Key Cryptography—PKC 2014.Buenos Aires,Argentina,2014:556-573
[10]Mao S W,Zhang H G,Wu W Q,et al.A resistant quantum key exchange protocol and its corresponding encryption scheme.China Communications,2014,11(9):131-141
[11]Zhang Huan-Guo,Liu Jin-Hui,Jia Jian-Wei,et al.A survey on applications of matrix decomposition in cryptography.Journal of Cryptologic Research,2014,1(4):341-357(in Chinese)(张焕国,刘金会,贾建卫等.矩阵分解在密码中应用研究.密码学报,2014,1(4):341-357)
[12]Kahrobaei D,Ha T Lam,Shpilrain V.Public key exchange using extensions by endomorphisms and matrices over a Galois field//Proceedings of the DIMACS Workshop on Multicore and Cryptography.Hoboken NJ,USA,2014:1-9
[13]Habeeb M,Kahrobaei D,Koupparis C,Shpilrain V.Public key exchange using semidirect product of(semi)groups//Proceedings of the Applied Cryptography and Network Security.Banff,Canada,2013:475-486
[14]Kreuzer M,Myasnikov A D,Ushakov A.A linear algebra attack to group-ring-based key exchange protocols//Proceedings of the Applied Cryptography and Network Security.Lausanne,Switzerland,2014:37-43
[15]Gashkov S B,Sergeev I S.Complexity of computation in finite fields.Journal of Mathematical Sciences,2013,191(5):661-685
[16]Fu Xiang-Qun,Bao Wan-Su,Wang Shuai.Quantum algorithm for discrete logarithm over ZN.Chinese Journal of Computers,2014,37(5):1058-1062(in Chinese)(付向群,鲍皖苏,王帅.ZN上离散对数量子计算算法.计算机学报,2014,37(5):1058-1062)
[17]Myasnikov A D,Ushakov A.Quantum algorithm for discrete logarithm problem for matrices over finite group rings.Groups Complexity Cryptology,2014,6(1):31-36
[18]Courtois N,Klimov A,Patarin J,Shamir A.Efficient algorithms for solving overdefined systems of multivariate polynomial equations//Proceedings of the EUROCRYPT2000.Bruges,Belgium,2000:392-407
[19]Liu Niu,Tan Shaohua,Li Xiaoyu,Xu Lingling.Cryptanalysis of a key agreement protocol over the ring of multivariate polynomials.Journal of Computational Information Systems,2014,10(13):5431-5436
[20]Menezes A J,Wu Y.The discrete logarithm problem in GL(n,p).Ars Combinatoria,1998,47:23-32
[21]Fortuna E,Gianni P.Square-free decomposition in finite characteristic:An application to Jordon Form computation.ACM SIGSAM Bulletin,1999,33(4):14-32
[22]Ke Shan-Xue,Zeng Ben-Sheng,Han Wen-Bao,Zhu WeiHua.Fast algorithm for factoring polynomials over finite fields.Journal of Information Engineering University,2004,4(4):8-14(in Chinese)(柯善学,曾本胜,韩文报,祝卫华.有限域上多项式分解的一种快速算法.信息工程大学学报,2004,4(4):8-14)
[23]Schneier B.Applied Cryptography:Protocols,Algorithms,and Source Code in C.2nd Edition.Hoboken:Wiley,2007
[2]Wang H Z,Zhang H G,Wang Z Y,Tang M.Extended multivariate public key cryptosystems with secure encryption function.Science China Information Sciences,2011,54(6):1161-1171
[3]Mosca M.Post-Quantum Cryptography.Switzerland:Springer International Publishing,2014
[4]Gaborit P.Post-Quantum Cryptography.Berlin Heidelberg:Springer,2013
[5]Wang S B,Zhu Y,Ma D,et al.Lattice-based key exchange on small integer solution problem.Science China Information Sciences,2014,57(11):1-12
[6]Jarvis K,Nevins M.ETRU:NTRU over the Eisenstein integers.Designs,Codes and Cryptography,2015,74(1):1-12
[7]Cao Z.New Directions of Modern Cryptography.Boca Raton:CRC Press,2012
[8]Tsaban B.Polynomial-time solutions of computational problems in noncommutative algebraic cryptography.Journal of Cryptology,2015,28(3):601-622
[9]Armknecht F,Gagliardoni T,Katzenbeisser S,Peter A.General impossibility of group homomorphic encryption in the quantum world//Proceedings of the Public-Key Cryptography—PKC 2014.Buenos Aires,Argentina,2014:556-573
[10]Mao S W,Zhang H G,Wu W Q,et al.A resistant quantum key exchange protocol and its corresponding encryption scheme.China Communications,2014,11(9):131-141
[11]Zhang Huan-Guo,Liu Jin-Hui,Jia Jian-Wei,et al.A survey on applications of matrix decomposition in cryptography.Journal of Cryptologic Research,2014,1(4):341-357(in Chinese)(张焕国,刘金会,贾建卫等.矩阵分解在密码中应用研究.密码学报,2014,1(4):341-357)
[12]Kahrobaei D,Ha T Lam,Shpilrain V.Public key exchange using extensions by endomorphisms and matrices over a Galois field//Proceedings of the DIMACS Workshop on Multicore and Cryptography.Hoboken NJ,USA,2014:1-9
[13]Habeeb M,Kahrobaei D,Koupparis C,Shpilrain V.Public key exchange using semidirect product of(semi)groups//Proceedings of the Applied Cryptography and Network Security.Banff,Canada,2013:475-486
[14]Kreuzer M,Myasnikov A D,Ushakov A.A linear algebra attack to group-ring-based key exchange protocols//Proceedings of the Applied Cryptography and Network Security.Lausanne,Switzerland,2014:37-43
[15]Gashkov S B,Sergeev I S.Complexity of computation in finite fields.Journal of Mathematical Sciences,2013,191(5):661-685
[16]Fu Xiang-Qun,Bao Wan-Su,Wang Shuai.Quantum algorithm for discrete logarithm over ZN.Chinese Journal of Computers,2014,37(5):1058-1062(in Chinese)(付向群,鲍皖苏,王帅.ZN上离散对数量子计算算法.计算机学报,2014,37(5):1058-1062)
[17]Myasnikov A D,Ushakov A.Quantum algorithm for discrete logarithm problem for matrices over finite group rings.Groups Complexity Cryptology,2014,6(1):31-36
[18]Courtois N,Klimov A,Patarin J,Shamir A.Efficient algorithms for solving overdefined systems of multivariate polynomial equations//Proceedings of the EUROCRYPT2000.Bruges,Belgium,2000:392-407
[19]Liu Niu,Tan Shaohua,Li Xiaoyu,Xu Lingling.Cryptanalysis of a key agreement protocol over the ring of multivariate polynomials.Journal of Computational Information Systems,2014,10(13):5431-5436
[20]Menezes A J,Wu Y.The discrete logarithm problem in GL(n,p).Ars Combinatoria,1998,47:23-32
[21]Fortuna E,Gianni P.Square-free decomposition in finite characteristic:An application to Jordon Form computation.ACM SIGSAM Bulletin,1999,33(4):14-32
[22]Ke Shan-Xue,Zeng Ben-Sheng,Han Wen-Bao,Zhu WeiHua.Fast algorithm for factoring polynomials over finite fields.Journal of Information Engineering University,2004,4(4):8-14(in Chinese)(柯善学,曾本胜,韩文报,祝卫华.有限域上多项式分解的一种快速算法.信息工程大学学报,2004,4(4):8-14)
[23]Schneier B.Applied Cryptography:Protocols,Algorithms,and Source Code in C.2nd Edition.Hoboken:Wiley,2007