Cryptanalysis of a Key Exchange Protocol Based on Commuting Matrices

JIA Jianwei; LIU Jinhui; ZHANG Huanguo

doi:10.1049/cje.2017.08.013

Volume 26 Issue 5

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2017 > 26(5): 947-951

JIA Jianwei, LIU Jinhui, ZHANG Huanguo, “Cryptanalysis of a Key Exchange Protocol Based on Commuting Matrices,” Chinese Journal of Electronics, vol. 26, no. 5, pp. 947-951, 2017, doi: 10.1049/cje.2017.08.013

Citation:

JIA Jianwei, LIU Jinhui, ZHANG Huanguo, “Cryptanalysis of a Key Exchange Protocol Based on Commuting Matrices,” Chinese Journal of Electronics, vol. 26, no. 5, pp. 947-951, 2017, doi: 10.1049/cje.2017.08.013

Citation:

PDF( 141 KB)

Cryptanalysis of a Key Exchange Protocol Based on Commuting Matrices

doi: 10.1049/cje.2017.08.013

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

Funds: This work is 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), and the Hubei Natural Science Foundation of China (No.2011CDB453, No.2014CFB440).

More Information

Corresponding author: ZHANG Huanguo (corresponding author) was born in 1945. He is now a professor of the School of Computer, Wuhan University. His main research interests include cryptography, theory and technology of network and information security. (Email:liss@whu.edu.cn)
Received Date: 2015-10-26
Rev Recd Date: 2016-06-01
Publish Date: 2017-09-10

Abstract

Abstract

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

FullText(HTML)

References(21)

References

Diffie Whitfield and Martin Hellman, "New Directions in Cryptography", IEEE Transactions on Information Theory, Vol.22, No.6, pp.644-654, 1976.

R.W. Odoni, et al., "Public key distribution in matrix rings", Electronics Letters, Vol.20, No.9, pp.386-387, 1984.

H.G. Zhang, et al., "Survey on cyberspace security", Science China Information Sciences, Vol.58, No.11, pp.1-43, 2015.

Gu L, Wang L, Ota K, et al., "New public key cryptosystems based on non-Abelian factorization problems", Security and Communication Networks, Vol.6, No.7, pp.912-922, 2013.

S.W. Mao, H.G. Zhang, et al., "A resistant quantum key exchange protocol and its corresponding encryption scheme", China Communications, Vol.11, No.9, pp.124-134, 2014.

Habutsu T, Nishio Y, Sasase I, et al., "A secret key cryptosystem by iterating a chaotic map", Proc. of Workshop on the Theory and Application of of Cryptographic Techniques, Berlin, Germany, pp.127-140, 1991.

T. Stojanovski and L. Kocarev, "Chaos-based random number generators-part I:Analysis[cryptography]", IEEE Transactions on Circuits Systems I Fundamental Theory Applications, Vol.48, No.3, pp.281-288, 2001.

A. Klimov, A. Mityagin and A. Shamir, "Analysis of Neural Cryptography", Proc. of Lecture Notes in Computer Science, Berlin, Germany, pp.288-298, 2002.

Kocarev Ljupco and Zarko Tasev, "Public-key encryption based on Chebyshev maps", Proceedings of the 2003 International Symposium on. Circuits and Systems IEEE, Khon Kaen, Thailand, pp.497-517, 2003.

R. Tenny, L.S. Tsimring, L. Larson, et al., "Using distributed nonlinear dynamics for public key encryption", Physical review letters, Vol.90, No.4, pp.047903:1-047903:4, 2003.

H.F. Chen, H.b. Sun, Y. Pan et al., "Characteristics of parameterized chaotic map on security and implementation", Chinese Journal of Electronics, Vol.16, No.4, pp.627-630, 2007.

X.Y. Wang and J. Zhao, "An improved key agreement protocol based on chaos", Communications in Nonlinear Science Numerical Simulation, Vol.15, No.12, pp.4052-4057, 2010.

C.C. Lee, C.L. Chen and S.Y. Huang, "An extended chaotic maps-based key agreement protocol with user anonymity", Nonlinear Dynamics, Vol.69, No.1-2, pp.79-8, 2012.

M.S. Farash and M.A. Attari, "An efficient and provably secure three-party password-based authenticated key exchange protocol based on Chebyshev chaotic maps", Nonlinear Dynamics, Vol.77, No.1-2, pp.399-411, 2014.

H.F. Zhu and X. Hao, "A provable authenticated key agreement protocol with privacy protection using smart card based on chaotic maps", Nonlinear Dynamics, Vol.81, No.1-2, pp.311-321, 2015.

R. Bose, "Novel public key encryption technique based on multiple chaotic systems", Physical Review Letters, Vol.95, No.9, pp.098702:1-098702:4, 2005.

K. Wang, W. Pei, L. Zou, et al., "Security of public key encryption technique based on multiple chaotic systems", Physics Letters A, Vol.360, No.2, pp.259-262, 2006.

M. Almulla, et al., "A concurrent key exchange protocol based on commuting matrices", Concurrency and Computation:Practice and Experience, Vol.25, No.5, pp.743-751, 2013.

S.B. Gashkov and I.S. Sergeev, "Complexity of computation in finite fields", Journal of Mathematical Sciences, Vol.191, No.5, pp.661-685, 2013.

J.H. Liu, H.G. Zhang, J.W. Jia, et al., "Cryptoanalysis of HKKS key exchange protocols", Chinese Journal of Computers, Vol.39, No.3, pp.516-528, 2016.

J.H. Liu, H.G. Zhang, J.W. Jia, et al., "Cryptanalysis of an asymmetric cipher protocol using a matrix decomposition problem", Science China Information Sciencs, Vol.59, No.3, pp.052109:1-052109:9, 2016.

Relative Articles

Supplements(0)

Cited By

Proportional views