Cryptanalysis of a Key Exchange Protocol Based on Commuting Matrices  

作　　者：JIA Jianwei LIU Jinhui ZHANG Huanguo 

机构地区：[1]Computer School of Wuhan University,Wuhan 430072,China [2]Key Laboratory of Aerospace Information Security and Trusted Computing Ministry of Education,Wuhan 430072,China

出　　处：《Chinese Journal of Electronics》2017年第5期947-951,共5页电子学报（英文版）

基　　金：supported by the National Natural Science Foundation of China(No.61303212,No.61170080,No.61202386);the State Key Program of National Natural Science of China(No.61332019,No.U1135004);the Major Research Plan of the National Natural Science Foundation of China(No.91018008);Major State Basic Research Development Program of China(973 Program)(No.2014CB340600);the Hubei Natural Science Foundation of China(No.2011CDB453,No.2014CFB440)

摘　　要：A key exchange protocol is considered unsafe.The scheme is based on a set of m commuting square singular matrices of dimension n×n over a finite field,and its security is claimed to rely on the hardness of the matrix version discrete logarithm problem.However,the proposal's design allows for a clean attack strategy.We show that the key exchange protocol is vulnerable to a linear algebra attack which only requires polynomial time to obtain the equivalent keys for all given public keys.We conduct a detailed analysis on the attack method and provide some improved suggestions on the key exchange protocol based on commuting matrices.A key exchange protocol is considered unsafe.The scheme is based on a set of m commuting square singular matrices of dimension n×n over a finite field,and its security is claimed to rely on the hardness of the matrix version discrete logarithm problem.However,the proposal＇s design allows for a clean attack strategy.We show that the key exchange protocol is vulnerable to a linear algebra attack which only requires polynomial time to obtain the equivalent keys for all given public keys.We conduct a detailed analysis on the attack method and provide some improved suggestions on the key exchange protocol based on commuting matrices.

关 键 词：CRYPTOGRAPHY Key exchange protocol CRYPTANALYSIS Discrete logarithm problem Linear equations 

分 类 号：TN918.4[电子电信—通信与信息系统]