基于格的RSA密码分析

发布时间：2018-09-18 16:34

【摘要】：格在公钥密码分析领域中有着十分重要的地位.1996年,Coppersmith以多项式方程求小值解的问题为桥梁,把攻击RSA密码体制的问题转换为求格中短向量的问题,开辟了基于格的RSA密码分析的研究,他的工作也在后人的简化完善下逐渐形成了Coppersmith方法.一方面,关于基于格的Coppersmith方法,依次介绍了模多项式方程求小值解的方法、整系数多项式方程求小值解的方法、求解近似公共因子问题的方法,还简单描述了除Coppersmith方法外的一种在低维格中寻找最短非零向量的格方法.另一方面,关于RSA密码分析,回顾了小加密指数攻击、小解密指数攻击、部分私钥泄露攻击、求解私钥d与分解模数N的等价性证明、隐式分解问题的分析、素因子部分比特泄露攻击、共模攻击等,并且以Prime Power RSA,Takagi's RSA,CRT-RSA,Common Prime RSA为例,介绍了格方法在RSA密码变体分析中的应用.
[Abstract]:In 1996, Coppersheimer used the problem of solving the small value solution of polynomial equation as a bridge, and transformed the problem of attacking RSA cryptosystem into the problem of finding the short vector in the lattice, which is very important in the field of public key cryptosystem analysis. The research of RSA cryptanalysis based on lattice has been opened up, and his work has gradually formed the Coppersmith method under the simplification and perfection of later generations. On the one hand, with regard to the lattice-based Coppersmith method, the methods of finding small value solutions for modular polynomial equations, integer coefficient polynomial equations and approximate common factor problems are introduced in turn. In addition to the Coppersmith method, a lattice method for finding the shortest nonzero vector in a low dimensional lattice is also briefly described. On the other hand, with regard to RSA cryptographic analysis, we review the small encryption exponent attack, the small decryption exponent attack, the partial private key leak attack, the proof of equivalence between solving the private key d and the decomposition modulus N, and the analysis of the implicit decomposition problem. Prime factor partial bit leak attack, common-mode attack and so on. Taking Prime Power RSA,Takagi's RSA,CRT-RSA,Common Prime RSA as an example, this paper introduces the application of lattice method in RSA cryptographic variant analysis.
【作者单位】：国防科学技术大学计算机学院;国防科学技术大学理学院;
【基金】：国家自然科学基金(11531002;61572026) 国防科技大学科研计划项目(CJ13-02-01) 教育部新世纪人才项目(NCET)
【分类号】：TN918

【相似文献】