一种基于热带半环的密钥建立协议的安全性分析

计算机科学 ›› 2022, Vol. 49 ›› Issue (6A): 571-574.doi: 10.11896/jsjkx.210700046

一种基于热带半环的密钥建立协议的安全性分析

黄华伟¹, 李春华²

1 贵州师范大学数学科学学院贵阳 550001
2 华东交通大学理学院南昌 330013

出版日期:2022-06-10 发布日期:2022-06-08
通讯作者: 黄华伟(hwhuang7809@163.com)
基金资助:
国家自然科学基金(61462016,61962011);贵州省科学技术基金资助项目(黔科合基础:ZK[2021]一般313号,[2019]1221号)

Security Analysis of A Key Exchange Protocol Based on Tropical Semi-ring

HUANG Hua-wei¹, LI Chun-hua²

1 School of Mathematical Sciences,Guizhou Normal University,Guiyang 550001,China
2 School of Science,East China Jiaotong University,Nanchang 330013,China

Online:2022-06-10 Published:2022-06-08
About author:HUANG Hua-wei,born in 1978,asso-ciate professor.His main researchin-terests include algebra and cryptography.
LI Chun-hua,born in 1973,professor.His main research interests include algebra and cryptography.
Supported by:
National Natural Science Foundation of China(61462016,61962011) and Science and Technology Foundation of Guizhou Province(QIANKEHEJICHU-ZK[2021]313,[2019]1221).

摘要/Abstract

摘要： 分析了Grigoriev等提出的基于热带半环的密钥建立协议的安全性,提出了一种代数密码分析方法。从协议的公开信息构造热带矩阵方程,通过解热带半环上的线性方程组试图获得双方的共享密钥。为防止这种代数密码分析,应适当增大协议的参数。

关键词: 计算复杂度, 密钥建立协议, 热带半环, 热带矩阵

Abstract: This paper analyses the security of a key exchange protocol based on tropical semi-ring proposed by Grigoriev et al,and provides a method of algebraic cryptanalysis.Some tropical matrix equations are constructed according to the public information of the protocol.And the shared key of the protocol is obtained by solving the linear system of equations over tropical semi-ring.The parameters of the protocol should be increased appropriately for resisting the algebraic cryptanalysis.

Key words: Computational complexity, Key exchange protocol, Tropical matrix, Tropical semi-ring

中图分类号:

TN918

黄华伟, 李春华. 一种基于热带半环的密钥建立协议的安全性分析[J]. 计算机科学, 2022, 49(6A): 571-574. https://doi.org/10.11896/jsjkx.210700046

HUANG Hua-wei, LI Chun-hua. Security Analysis of A Key Exchange Protocol Based on Tropical Semi-ring[J]. Computer Science, 2022, 49(6A): 571-574. https://doi.org/10.11896/jsjkx.210700046

参考文献

[1] MAZE G,MONICO C,ROSENTHAL J.Public key cryptography based on semigroup actions[J].Advances of Mathematics of Communications,2007,1(4):489-507.
[2] HUANG H,XIAO G.A Key Establishment Protocol Based on Conjugacy Search Problem in Clifford Semigroups[J].Computer Science,2007,34(2):76-78.
[3] HUANG H,ZHANG J,WEN Y,et al.Public key encryption scheme based on a class of matrix semigroup action[J].Journal on Communications,2007,28(8A):5-12.
[4] BAUMSLAG G,FAZIO N,NICOLOSI A R,et al.Generalized learning problems and applications to non-commutative cryptography[C]//Provable Security 2011.2011:324-339.
[5] BAGHERI K,SADEGHI M R,PANARIO D.A non-commutative cryptosystem based on quaternion algebras[J].Designs,Codes and Cryptography,2018,86:2345-2377.
[6] CLIMENT J J,NAVARRO P R,TORTOSA L.An extension of the noncommutative Bergman's ring with a large number of noninvertible elements[J].Applicable Algebra in Engineering,Communication and Computing,2014,25(5):347-361.
[7] ZHANG Y.Cryptanalysis of a key exchange protocol based on the ring Ep(m)[J].Applicable Algebra in Engineering,Communication and Computing,2018,29:103-112.
[8] GRIGORIEV D.Complexity of solving Tropical linear systems[J].Computational Complexity,2013,22:71-88.
[9] GRIGORIEV D,SHPILRAIN V.Tropical cryptography[J].Com-munications in Algebra,2014,42(6):2624-2632.
[10] KOTOV M,USHAKOV A.Analysis of a key exchange protocol based on tropical matrix algebra[J].Journal of Mathematical Cryptology,2018,12(3):137-141.
[11] GRIGORIEV D,SHPILRAIN V.Tropical cryptography II:Extensions by homomorphisms[J].Communications in Algebra,2019,47(10):4224-4229.

相关文章 15

[1]	韩洁, 陈俊芬, 李艳, 湛泽聪. 基于自注意力的自监督深度聚类算法 Self-supervised Deep Clustering Algorithm Based on Self-attention 计算机科学, 2022, 49(3): 134-143. https://doi.org/10.11896/jsjkx.210100001
[2]	尤凌, 管张均. 一种低复杂度的水声OFDM通信系统子载波分配算法 Low-complexity Subcarrier Allocation Algorithm for Underwater OFDM Acoustic CommunicationSystems 计算机科学, 2021, 48(6A): 387-391. https://doi.org/10.11896/jsjkx.201100064
[3]	陆钊,朱晓姝. 基于压缩感知的图像处理算法研究 Research on Image Processing Algorithm Based on Compressed Sensing 计算机科学, 2017, 44(6): 312-316. https://doi.org/10.11896/j.issn.1002-137X.2017.06.055
[4]	岑跃峰,王万良,姚信威,王超超,潘铁强. 基于决策树的HEVC编码单元划分算法 Decision Tree Based Coding Unit Splitting Algorithm for HEVC 计算机科学, 2016, 43(4): 308-312. https://doi.org/10.11896/j.issn.1002-137X.2016.04.063
[5]	何琨,姚鹏程,李立文. 求解二维矩形Packing问题的完备算法 Complete Algorithm for 2D Rectangular Packing Problem 计算机科学, 2014, 41(8): 55-59. https://doi.org/10.11896/j.issn.1002-137X.2014.08.011
[6]	刘嘉，祁奇，陈振宇，惠成峰. ESSK:一种计算点击流相似度的新方法 ESSK; A New Approach to Compute Clickstream Similarity 计算机科学, 2012, 39(6): 147-150.
[7]	柳毅,郝彦军,庞辽军. 一个新的基于Merkle树的移动代理路由解决方案 New Mobile Agents Secure Itinerary Protection Based on Merkle Trees 计算机科学, 2011, 38(5): 28-30.
[8]	柳毅,丁勇,庞辽军. 一种新的移动代理路由解决方案 Secure Itinerary Protection Based on Mobile Agents 计算机科学, 2009, 36(11): 113-115.
[9]	黄华伟肖国镇. 基于Clifford半群上共轭搜索问题的密钥建立协议计算机科学, 2007, 34(2): 76-78.
[10]	. 基于移动代理的安全集式路由协议计算机科学, 2007, 34(1): 112-114.
[11]	庞辽军王育民. 一个安全高效的门限多重秘密共享方案计算机科学, 2006, 33(1): 66-68.
[12]	左志宏舒敏周明天. 计算机病毒的计算复杂度问题计算机科学, 2005, 32(7): 102-104.
[13]	柳毅姜正涛王育民. 基于Merkle树的安全移动代理路由协议计算机科学, 2005, 32(7): 85-86.
[14]	陈铿韩伯棠. 有限长度信号正交小波变换的若干问题的探讨计算机科学, 2005, 32(1): 212-213.
[15]	张峰秦志光刘锦德. 网络安全中协同攻击的威胁评估方法计算机科学, 2004, 31(12): 55-57.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed