RSA及其变体算法的格分析

摘要

RSA算法是一个广泛应用的公钥密码体制，在公钥密码学领域有着深远影响。随着格理论的发展与LLL算法的提出，基于格基约化技巧的密码分析技术逐渐成为研究公钥密码算法安全性的重要数学工具。针对RSA算法的格分析技术通过提炼密钥信息含有的代数关系，将安全性分析转化为在多项式时间内求解模方程或整方程的小根。 在本文中，利用格分析技术和以其为基础的格优化分析技巧，重点关注RSA及其变体算法的安全性分析，拓展、改进并优化了前人的分析结果，同时提出新的问题并给出研究结果。 本文的主要成果与创新点如下: 1.针对小加密指数的标准RSA算法，应用线性化技巧求解三变量模方程得到了小指数攻击的新拓展分析结果。我们的方法克服了已有工作中小加密指数受限的不足之处，使得小解密指数攻击可适用于任意小加密指数情形。 2.针对使用多对加解密指数对的PP-RSA变体算法，通过联立求解特定模方程组，应用指数优化技巧得到了小指数攻击的新拓展分析结果。我们的方法考虑了更多的加解密指数对，从而改进了之前的攻击结果。 3.针对使用改性欧拉函数的MEQ-RSA变体算法，给出了小指数攻击的精确适用范围。分析了使用多对加解密指数对的情形，应用Minkowski和技巧求解模方程组，得到了小指数攻击的新拓展分析结果。 4.针对存在素数差的MP-RSA变体算法，指出当素因子个数增多时模数分解攻击比小解密指数攻击更为有效。随后通过整方程方法与线性化技巧得到了优化分析结果，提高了素数差的不安全界。 5.针对一般RSA模数的已知比特分解问题，通过求解特定形式的双变量整方程，给出了该问题的统一求解条件。该条件既可以覆盖之前所有已知结果，又能够进一步给出优化分析结果。 6.提出隐式相关私钥分解问题并对其进行研究。隐式相关私钥分解问题可以看作隐式分解问题与部分私钥泄露攻击的混合模型。通过应用分裂技巧与线性化技巧，将私钥转化为多个更小未知变量的线性组合，随后求解模方程得到隐式信息的不安全界。该分析结果可以给隐式相关私钥的使用提供理论上的安全性要求。

目录

声明

摘要

第1章绪论

1．1研究背景与意义

1．2 RSA算法安全性分析的研究现状

1．3研究内容与论文结构

第2章预备知识

2．1标准RSA算法

2．2 RSA变体算法

2．3格的基础知识

2．4格分析技术

2．5实验环境

2．6本章小结

第3章小指数攻击的拓展分析

3．1 标准RSA算法的小加密指数情形

3．1．1 引言

3．1．2拓展分析

3．1．3理论结果

3．2．2拓展分析

3．2．3理论与实验结果

3．3 MEQ-RSA算法的小解密指数情形

3．3．1 引言

3．3．2拓展分析

3．3．3实验结果

3．4本章小结

第4章模数分解攻击的优化分析

4．1．1 引言

4．1．2优化分析

4．1．3理论与实验结果

4．2一般RSA模数的已知比特情形

4．2．1 引言

4．2．2优化分析

4．2．3理论结果

4．3本章小结

第5章隐式相关私钥分解问题

5．1 引言

5．2两个实例情形

5．3多个实例情形

5．4理论与实验结果

5．5本章小结

第6章结论与展望

6．1 论文总结

6．2工作展望

参考文献

致谢

在读期间发表的学术论文与取得的研究成果