基于格的RSA密码分析

摘要:

格在公钥密码分析领域中有着十分重要的地位.1996年,Coppersmith以多项式方程求小值解的问题为桥梁,把攻击RSA密码体制的问题转换为求格中短向量的问题,开辟了基于格的RSA密码分析的研究,他的工作也在后人的简化完善下逐渐形成了Coppersmith方法.一方面,关于基于格的Coppersmith方法,依次介绍了模多项式方程求小值解的方法、整系数多项式方程求小值解的方法、求解近似公共因子问题的方法,还简单描述了除Coppersmith方法外的一种在低维格中寻找最短非零向量的格方法.另一方面,关于RSA密码分析,回顾了小加密指数攻击、小解密指数攻击、部分私钥泄露攻击、求解私钥d与分解模数N的等价性证明、隐式分解问题的分析、素因子部分比特泄露攻击、共模攻击等,并且以Prime Power RSA,Takagi's RSA,CRT-RSA,Common Prime RSA为例,介绍了格方法在RSA密码变体分析中的应用.

Lattice plays an important role in the field of cryptanalysis of public key cryptosystem. In 1996, Coppersmith introduces new ways of finding small roots of polynomial equation. According to his work, from the problem of some attacks on RSA cryptosystem, one can derive the problem of finding short vectors in lattice. Lattice-based cryptanalysis of RSA crypto-system thus begins to attract attentions＇ and the method has been developed into ^Coppersmith^s method,r after some reformula-tions and extensions. On the one hand, about lattice-based Coppersmith^ method, this paper introduces the methods of finding small roots of modular polynomial equation and integer polynomial equation, and the method of solving approximate common di-visor problem. Besides, another lattice method which needs to find the shortest vector in a low-dimension lattice is also presen-ted. On the other hand, about the cryptanalysis of RSA cryptosystem, this paper summarizes small public exponent attack, small private exponent attack, partial key exposure attack, deterministic polynomial-time equivalence of computing the private key d and factoring the modulus N ＇ cryptanalysis of the implicit factorization problem, partial prime factor exposure attack, and cryptanalysis of RSA with multiple exponents and the same modulus. Moreover, we take Prime Power RSA, 丁akagi’ s RSA, CRT-RSA and Common Prime RSA for examples＇ and introduce cryptanalysis of RSA variants by means of lattice meth-ods.

作者:

李超 王世雄 屈龙江 付绍静

机构地区:

国防科学技术大学计算机学院 国防科学技术大学理学院

出处:

《betway官方app 学报：自然科学版》 CAS 北大核心 2017年第3期1-13,共13页

基金:

国家自然科学基金(11531002 61572026) 国防科技大学科研计划项目(CJ13-02-01) 教育部新世纪人才项目(NCET)

关键词:

格 RSA密码 Coppersmith方法 LLL算法

lattice RSA cryptosystem Coppersmith’s method LLL algorithm

分类号:

TN918 [电子电信—通信与信息系统]

基于格的RSA密码分析.pdf