格理论及格基约减算法在公钥密码分析学中的应用研究

论文摘要

近年来，格理论及格基约减算法作为一个用来高效的分析、攻击公钥密码系统的工具，其角色正在变得越来越重要。格基约减算法在1990年对基于背包问题的密码系统的成功攻击，正式确立了其在密码分析学中的地位。而自从1996年Coppersmith提出用LLL算法对根较小的整系数单变量模等式及双变量等式的解法以来，对其方法的各种应用更是成了分析RSA系统及其变种的有力工具。迄今为止，各种分析方法及思路百花齐放、层出不穷，许多成果都是近几年提出的，比如Boneh和Durfee在2000年提出的对RSA的低指数攻击、Bl（o|¨）mer、Ernest等人提出的部分密钥泄漏攻击、May等人对RSA变种体制的攻击，等等。这些引人注目的成果表明，使用格基约减算法的攻击（没有误会的情况下后文简称“格攻击”）作为一种高效率的分析方法，在现代密码分析学中扮演着极其重要的地位（事实上，格攻击是与数域筛法并列的最有效的分解RSA模的分析工具）。不但如此，而且该方法的应用潜力巨大，有许多新的价值等待人们来挖掘。本论文的主要成果是：使用新的方法分析了在RSA体制中已知一部分p求N的分解的问题；此方法在实践中也可以作为一种对RSA公钥体制的部分泄漏攻击来使用。该问题的最好结果是Coppersmith在1996年提出的上界，即已知p的[1/4log2N]高位比特可以在多项式时间内分解N。本文在使用新的方法进行分析，证明了在公钥e≈1（这是RSA体制参数选择的通常情况）并且私钥d<0．483时用较少的p的高位比特就可以在多项式时间内分解N，得到了比Coppersmith原方法更优的结果。这个优化的结果进一步扩展了格攻击的应用价值。另外，本文第三章中对Coppersmith定理的最初应用也提出了一些自己的见解及扩展，提供了对更加一般的情况的分析。

论文目录

• 摘要
• ABSTRACT
• 符号说明
• 第一章 引言
• 第二章 格基础理论、格基约减算法及RSA公钥系统
• 2.1 格的定义及性质
• 2.2 格基约减算法
• 2.3 使用格进行密码分析的对象——RSA公钥系统
• 第三章 Coppersmith的方法
• 3.1 概要
• 3.2 当变量满足给定上界时求等式的解
• 3.2.1 分析单变量模等式——求解一元模方程
• 3.2.2 求解多变量模等式及二元方程
• 3.3 Coppersmith结论在密码分析学中的直接应用
• 3.4.1 当e很小并知道部分明文时进行的攻击
• 3.4.2 当知道p部分比特时的分解问题——Factoring with High Order Bits Known
• 3.4.3 已知d与分解N的多项式时间等价性
• 第四章 格攻击的各种高级应用
• 4.1 几种典型的现有应用
• 4.1.1 弱安全性的RSA私钥d
• 4.1.2 部分密钥泄漏攻击
• 4.1.3 对使用小的CRT指数的RSA变种的攻击
• 4.2 对已知高位p的分解问题的新分析
• 结束语及展望
• 参考文献
• 致谢
• 学位论文评阅及答辩情况表