基于热带矩阵密钥交换协议的密码分析

来源：计算机技术与发展杂志2023年第03期北京时间：

作者：黄华伟*;李春华

单位：1. 贵州师范大学 数学科学学院,贵州 贵阳 550001;2. 华东交通大学 理学院,江西 南昌 330013

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

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