几种多变量公钥密码体制的破解

摘要

多变量公钥密码在近些年得到了快速地发展，由于可以抵抗量子攻击，其被认为是传统公钥密码体制的一种替代方案。目前已经设计出多种多变量公钥密码体制，例如MI加密体制，油醋签名体制，MFE加密体制，EMC体制等。MFE加密体制已经被破解，但是目前存在多种MFE体制的改进体制，设计者声称它们可以抵抗现有的所有针对多变量密码的攻击方法。EMC体制作为一种增强体制，其设计者声称EMC体制可以很大程度上增强现存多变量密码体制的安全性。
　　本文的主要工作是详细地分析上面提到的MFE体制的两种改进体制和基于EMC体制构造出来的HTTP加密体制以及HTTM签名体制的安全性，并利用相应的攻击方法对它们进行安全性分析。
　　MFE加密体制的中心映射满足二阶线性化方程，因此不能抵抗高阶线性化方程的攻击。MFE加密体制的两种改进体制试图通过修改MFE体制的中心映射来使MFE体制可以抵抗二阶线性化方程的攻击。经过详细地分析发现，这两种改进体制不但不能抵抗二阶线性化方程的攻击，甚至不能抵抗一阶线性化方程的攻击。文中分别用一阶线性化方程和二阶线性化方程的攻击方法对这两种改进体制进行了攻击，对这两种MFE改进体制攻击的复杂度分别为235个域216?运算和252个域216?运算。
　　EMC体制属于多变量公钥密码的增强体制，它可以应用到所有现存的多变量公钥密码体制中，目的是增强已存多变量体制的安全性。EMC体制的核心是在加密变换中增加一个基于哈希函数的非线性变换-HT变换。经过详细地分析，文中找到一种方法，可以将EMC体制褪化为原始的多变量公钥密码体制，并利用对原始多变量公钥密码体制的攻击方法对EMC体制进行攻击。利用这种攻击方法，文中成功地破解了基于EMC体制的HTTP加密体制和HTTM签名体制，对HTTP加密体制的攻击复杂度为228个域28?运算，对HTTM签名体制的攻击复杂度为241个域28?运算。
　　本文应用工具软件Magma实现了上述所有攻击，验证了本文的理论分析结果，并在本文中介绍了攻击过程实现的关键算法。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 研究背景和意义

1.2 国内外研究现状

1.3 论文的主要工作

1.4 论文的内容安排

第二章 多变量公钥密码体制

2.1 基本概念

2.2 多变量公钥密码的一般形式

2.3 多变量公钥密码的基本构造

2.4 多变量公钥密码的攻击方法

2.5 MPKC增强方法

2.6 本章小结

第三章 MFE改进体制的安全性分析

3.1 MFE加密体制

3.2 MFE的改进体制

3.3 二阶矩阵构造分析

3.4 本章小结

第四章 多变量扩展体制的安全性分析

4.1 多变量公钥密码的扩展体制

4.2 对EMC体制的安全性分析

4.3 HTTP加密体制

4.4 HTTM签名体制

4.5 本章小结

第五章 攻击算法实现的关键技术

5.1 多变量公钥密码算法的实现

5.2 线性化方程算法实现

5.3 解方程算法实现

5.4 本章小结

第六章 总结和展望

6.1 本文总结

6.2 未来工作展望

致谢

参考文献

攻读硕士期间取得的学术成果