公钥密码的格分析优化方法研究

Since the LLL lattice basis reduction algorithm has been proposed, the application of lattices in the public-key cryptanalysis has attracted lots of attentions. Based on the algebraic relation between the public and private keys of RSA scheme, the lattice-based Coppersmith's method which can solve small roots of equations in polynomial time has become an important tool in the analysis of the RSA scheme. Moreover, the lattice-based methods can also be applied to analyze some other problems such as subset sum problem, simultaneous Diophantine equations and approximate common divisor problem. In this project we will mainly study the following problems: (1) The research in the small private exponent attacks on RSA and CRT-RSA is of great theoretical value in the designs of public-key schemes and selection of parameters, we will propose novel lattice constructions to improve the existing results; (2) Study the effects on the security of RSA scheme and DSA algorithm with implicit hint, and the results can be applied to detect if there are any insecure pseudo-random numbers in the private keys; (3) In studying the selections of polynomials in the Coppersmith's method, we fully capture the algebraic structure of the original polynomials and unknown variables, which results in better lattice constructions. These studies are of great help in improving the existing results and promoting the applications and developments on lattice-based methods.

随着LLL格基约化算法的提出，格在公钥密码分析学中的应用引起了大量关注。基于LLL算法实现的Coppersmith方法可以在多项式时间内求解方程的小根，结合RSA方案私钥的代数关系，该方法成为了分析RSA方案的重要技术。同时，格分析方法在求解子集和、同步丢番图方程以及近似公因子等问题中也有重要应用。本项目的主要研究内容包括：一、RSA以及CRT-RSA方案的小解密指数攻击结果对公钥方案的设计以及参数的选取有重要的理论研究意义，我们将提出新的格优化技巧以提高现有分析结果；二、研究隐式线索问题对RSA方案和DSA数字签名算法的安全性影响，该研究结果可以检测私钥中是否存在不安全的伪随机数；三、研究Coppersmith方法中多项式选取的优化方法，使得在多项式选取中可以充分挖掘方程中未知变量的代数关系以优化格的构造。这些研究有助于提高现有的分析结果，利于格方法的应用及发展。

随着LLL格基约化算法的提出，格在公钥密码分析学中的应用引起了大量关注。基于LLL算法实现的Coppersmith方法可以在多项式时间内求解方程的小根，结合RSA方案私钥的代数关系，该方法成为了分析RSA方案的重要技术。本项目的主要研究内容包括：一、RSA以及CRT-RSA方案的小解密指数安全性分析；二、研究隐式线索问题对RSA方案和DSA数字签名算法的安全性影响；三、研究Coppersmith方法中多项式选取的优化方法。. 我们对CRT-RSA方案的安全性分析取得了重要研究进展，我们的结果大幅度改进了2007年美密会中所发表的分析结果。尽管关于该问题的研究已经有近三十年的历史，但是不安全的解密指数范围对方案设技术参数的选取有着重要理论意义和应用价值。我们的研究成果发表在了密码学最顶级的期刊Journal of Cryptology（CCF-A）。我们还在DCC（CCF-B）、TCS（CCF-B）等国际会议和期刊上发表了多篇论文。