公钥密码分析中的格方法与代数攻击

Public key cryptography is an important technology for ensuring the security of modern information systems. The starting point of the present proposal is to study methods which combine linear identical relations and high order identical relations derived from cryptographic systems to attack public key cryptographic systems, and to obtain cryptographic analysis methods with low complexity by applying lattice basis reduction algorithms to solve linear identical relations and algebraic equation solving algorithms to high order identical relations. The project will mainly study how to combine lattice basis reduction and algebraic equation solving algorithms to analyze and break public key cryptographic systems based on error coding, lattices, or multivariate polynomials; research how to launch broadcast, multiple transmission or fault injection attacks on such cryptographic systems; study how to apply combined lattice basis reduction and algebraic equation solving methods to analyze public key cryptographic variant schemes based on discrete logarithm, integer factorization, or vector knapsack problems; and present new combined broadcast-type attacks on conventional ECC, RSA and SM2 cryptosystems. The project will focus on the analysis of post quantum public key cryptography which is regarded to resist against quantum computer attacks and achieve obvious effect on understanding and designing secure public key cryptography.

公钥密码是现代信息系统安全性的重要保障。本项目的出发点是研究公钥密码系统两种恒等关系--线性恒等关系和高阶恒等关系相结合的攻击方法，即公钥密码的基于格基归约求解和代数方程求解相结合的分析方法，旨在得到低复杂度的代数密码分析新方法。主要研究破解纠错码、格和多变量多项式公钥密码中的格基归约求解--代数方程求解的分析方法，研究纠错码、格和多变量公钥密码中的广播攻击、重放攻击、差错攻击分析方法，研究以离散对数、因子分解、向量背包等困难假设为基础设计的公钥密码变型的格基归约求解--代数方程求解的分析方法，以及研究ECC、RSA、SM2等常规公钥密码的基于格和代数攻击的广播模式下的新攻击方法。本项目的研究以后量子公钥密码的分析为主要载体，对于我们理解和设计安全的可抵御量子计算机攻击的公钥密码具有重要意义。

公钥密码是现代信息系统安全性的重要保障，利用格基约化来求解多项式方程的小根、进而恢复相应秘密信息的格方法是公钥密码分析和基础问题计算难度评估的重要工具，起着举足轻重的作用。. 本项目研究格基归约求解的分析方法和基于格的公钥密码分析技术，项目研究按计划执行，进展顺利，完成了预定的研究任务。. 项目主要研究结果如下：（1）分析了Dual RSA方案的安全性，利用二次格基约化技术提出的小解密指数攻击首次改进了Dual RSA方案的安全性分析结果。（2）给出了RSA及其Takagi变型方案的部分比特泄露攻击；给出CRT-RSA方案和Prime Power RSA的多组加解密指数的安全性分析，得到目前最优的私钥恢复分析结果。（3）利用二次格分析方法分析隐式线索下的大数分解问题，提高了以前大量的的分析结果。（4）结合Coppersmith方法与Herrmann-May线性化方法，分析了RSA算法在新的私钥泄露模型下的安全性，攻击成功的条件优于已有的Nitaj-Douh结果，且实际攻击的效率更高。扩展此方法到分析具有更多未知比特块的私钥和多组加解密指数对问题和隐式分解问题的问题，得到相关改进分析结果。（5）将模逆隐藏数问题中的和求逆同余生成器中秘密信息的恢复转换成二次多变量模方程的求解，提出了的基于格的求解优化方法显著减少了所需要的样本数量和样本比特信息位数。（6）利用格基约化算法评估多素数phi隐藏假设的安全性，给出未知小根的上界为N^{O(m-1)}的两个结果。（7）利用线性化技术给出了一个NTRU密码方案的不安全性分析和反制方案。（8）给出了一种确定性的计算小区间因子的算法，复杂度与以前的概率性算法相同，而且不需要因子是素数的假设。（9）给出简洁的格方法分析近似公因子问题，方法优于知名的正交格攻击技术，显示了2015年欧密会上全同态加密需要更大的参数。（10）改进了Mersenne数低汉明重量比搜索问题的中间相遇攻击的复杂度，基于此设计了一个密钥量有改进的基于梅森素数困难问题的公钥密码体制。. 项目在权威刊物《Designs，Codes and Cryptography》和主流密码学专业学术会议上发表论文21篇，全程参与课题研究的三名博士生毕业获得博士学位。项目研究对于我们理解和设计安全的公钥密码具有重要意义。