Cryptanalysis of Cryptosystems Based on General Linear Group  

作　　者：Jianwei Jia Jinhui Liu Huanguo Zhang 

机构地区：[1]Computer School of Wuhan University,Wuhan,Hubei 430072,China [2]Key Laboratory of Aerospace Information security and trusted computing Ministry of Education,Wuhan University,Wuhan 430072,HubeiProvince,China

出　　处：《China Communications》2016年第6期217-224,共8页中国通信（英文版）

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

摘　　要：Advances in quantum computers threaten to break public key cryptosystems 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. In this background, Majid Khan et al.proposed two novel public-key encryption schemes based on large abelian subgroup of general linear group over a residue ring. In this paper we show that the two schemes are not secure. We present that they are vulnerable to a structural attack and that, it only requires polynomial time complexity to retrieve the message from associated public keys respectively. Then we conduct a detailed analysis on attack methods and show corresponding algorithmic description and efficiency analysis respectively. After that, we propose an improvement assisted to enhance Majid Khan's scheme. In addition, we discuss possible lines of future work.Advances in quantum computers threaten to break public key cryptosystems 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. In this background, Majid Khan et al.proposed two novel public-key encryption schemes based on large abelian subgroup of general linear group over a residue ring. In this paper we show that the two schemes are not secure. We present that they are vulnerable to a structural attack and that, it only requires polynomial time complexity to retrieve the message from associated public keys respectively. Then we conduct a detailed analysis on attack methods and show corresponding algorithmic description and efficiency analysis respectively. After that, we propose an improvement assisted to enhance Majid Khan＇s scheme. In addition, we discuss possible lines of future work.

关 键 词：CRYPTOGRAPHY post quantum computational cryptography CRYPTANALYSIS non-abelian algebraic structures linear equations 

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