多变量公钥密码体制秩攻击的实现与分析

发布时间：2021-12-30 05:04

　　多变量公钥密码体制在近30年得到了快速地发展,由于其安全性基础——求解非线性多变量多项式方程组的困难问题在量子计算机模型下没有多项式时间可解算法,被认为是传统公钥密码体制的一种替代方案。目前,多数针对多变量公钥密码体制的安全性分析主要适用于二次多项式情况,不能确保在三次多项式情况同样适用。最小秩攻击是分析二次多变量公钥密码体制的常用工具,本文通过研究,成功地将最小秩攻击应用于三次多变量公钥密码体制的安全性分析。主要工作安排如下:1.本文针对三次MI密码体制进行了安全性分析,相较于MI体制,它的中心映射次数由qθ+1增加到qθ+3,所对应的公钥多项式的次数也由二次增加到了三次。新的中心映射可以避免线性化方程,但经过深入分析,可发现改进后的中心映射满足二次化方程。在找到所有满足条件的二次化方程后,结合Grobner基方法,可以快速地恢复合法密文对应的明文。同时,还发现该方案实例抵抗最小秩攻击的时间复杂度并没有达到作者所声称的O（2222）,而仅仅只有O（2132）。2.本文针对立方密码体制进行了安全性分析,这种体制是经典的多变量公钥密码体制Square的改进方案。通过增加中心映射次数,将公... 

【文章来源】：电子科技大学四川省 211工程院校 985工程院校 教育部直属院校

【文章页数】：89 页

【学位级别】：硕士

【部分图文】：

MI加密解密过程

MFE加密解密过程

第二章预备知识13其中为油变量，为醋变量。从上式可以看出，油醋多项式中，只有醋变量的二次项，没有油变量的二次项。确定醋变量的值，变为油变量的线性方程组，通过求解这个方程组，即可得到油变量的值，这个过程就是的求逆过程。油醋体制属于小域类方案，不需要同构变换来完成小域-扩域转换。给定仿射变换，复合得到公钥函数。对合法消息进行签名只需要依次计算，收到文档和签名后，通过比较来决定是否接受文档。油醋体制的签名验证的工作过程如图2-3所示：图2-3油醋体制签名验证过程油醋签名体制分为两类，一种是平衡油醋体制（），另一种是非平衡油醋体制（）。Kipnis等人[42]在1998年使用共轭矩阵方法破解了平衡油醋体制，非平衡油醋体制为了抵抗这种攻击，一般采用参数。另外，丁津泰等人基于油醋体制思想提出了的Rainbow签名体制，可看作是多层油醋体制。2.4主要攻击方法2.4.1直接攻击直接攻击是MPKC方案安全性分析最常使用的一种方法，直接攻击的实质是将密文变量带入公钥函数，得到关于明文变量的方程组如公式（2-17）所示：（2-17）然后直接使用解方程组的方法对方程组（2-17）求解。关于解方程组的方法，主要有Grobner基方法中的F4算法、F5算法[30]XL算法[29]。Grobner基方法是由Buchberger提出的一种高效的求解方程组的算法，F4算法和F5算法可以看作是Grobner基算法进一步的改进。本文主要介绍Grobner基算法：定义2.1（理想）如果集合是环的子集，集合对于环的加法运算，构成的加法群的子群，且任意，，有，则是的理想。

【参考文献】：
期刊论文
[1]投影对C*-体制对称性的破坏[J]. 袁峰,胡予濮,欧海文,赵东.  华南理工大学学报(自然科学版). 2010(05)

博士论文
[1]多变量公钥密码体制的设计与安全性分析研究[D]. 鲁刚.电子科技大学 2017



本文编号：3557531