«上一篇/Previous Article|本期目录/Table of Contents|下一篇/Next Article»

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:

33

期数:

2023年03期

页码:

93-97

栏目:

网络空间安全

出版日期:

2023-03-10

文章信息/Info

Title:

Cryptanalysis of a Key Exchange Protocol Based on Tropical Matrices

文章编号:

1673-629X(2023)03-0093-05

作者:

黄华伟^1* ; 李春华²

1. 贵州师范大学 数学科学学院,贵州 贵阳 550001;

2. 华东交通大学 理学院,江西 南昌 330013

Author(s):

HUANG Hua-wei1 * ; LI Chun-hua2

1. School of Mathematical Sciences,Guizhou Normal University,Guiyang 550001,China;

2. School of Science,East China Jiaotong University,Nanchang 330013,China

关键词:

公钥密码; 密钥交换协议; 密码分析; 热带半环; 热带矩阵

Keywords:

public-key cryptography; key exchange protocol; cryptanalysis; tropical semi-ring; tropical matrix

分类号:

TP309. 2;TN918. 1

DOI:

10. 3969 / j. issn. 1673-629X. 2023. 03. 014

摘要:

量子计算机的发展对目前广泛使用的公钥密码体制构成了潜在的威胁,具有抗量子分析性质的密码体制受到了广泛关注。 由于热带半环中的乘法实际上是普通加法,具有运算效率高的优势,且求解多变量热带非线性多项式方程组是 NP 问题,近年来一些基于热带半环的公钥密码被提出。 该文分析了 Grigoriev 和 Shpilrain 基于热带矩阵半环半直积的密钥交换协议安全性。 定义了一种矩阵的比较大小关系,并证明了半直积运算具有部分的保序性,元素的乘法幂关于第一个分量矩阵构成了单调递减序列。 据此,针对该协议,提出了一种简单的二分查找攻击算法。 该算法通过公开信息可以求用户私钥,从而破解了该协议。 该攻击算法的比特位运算的计算复杂度为 O (2log2r (2k3 +5k2 ) ) ,其中 r 为指数上界,k 为矩阵的阶。 实验结果表明,如果协议参数选取自 Grigoriev 和 Shpilrain 建议的范围,攻击算法在一分钟内就能求出私钥。 而且即使增大协议的参数,该攻击仍然有效。

Abstract:

With the development of quantum computer,the classical public key cryptosystems widely used will encounter potential threat.So it is currently a research focus of cryptography to explore the cryptosystems which can resist quantum attack. Because themultiplication in tropical semiring is actually the ordinary addition,it has the advantage of high operation efficiency. And the problem ofsolving multivariable tropical nonlinear polynomial equations is NP hard. In recent years,some public key cryptography based on tropicalsemiring have been proposed. We analyze the security of a key exchange protocol based on the semidirect product of tropical matrix　semiring. A matrix size comparison is defined,and it is proved that the semidirect product operation has partial order preservation,and themultiplicative power of the element constitutes a monotonically decreasing sequence with respect to the first component matrix.Therefore,a simple binary search attack algorithm is proposed for the protocol. The algorithm can find the user’s private key throughpublic information,so as to crack the protocol. The computational complexity of the bit operation of the attack algorithm is O (2log2r(2k3 +5k2 ) ) ,where r is the upper bound of the index and k is the order of the matrix. The experimental results show that if the protocol　parameters are selected in the range suggested by Grigoriev and Shpilrain,the attack algorithm can find the private key in one minute.Moreover,even if the parameters of the protocol are increased,the attack is still effective.

常用功能

更新日期/Last Update: 2023-03-10