椭圆曲线和圆锥曲线的RSA密码体制的攻击

摘要

96欧密会上，Coppersmith[11]提出了用求解最短格的LLL算法，来求解模多项式，并把这种方法用在求解RSA明文中的低比特部分：(M+Mo)c：C mod N中的低比特部分M0.这是第一种对RSA密码体制的LLL算法的攻击方法，开创了用求最短格的方法分析RSA密码体制的先例. 由于Coppersmith的开创性地工作，以及对RSA较好的分析效果，很多学者开始对他的方法进行了深入研究，并对他的方法进行了各种改进。98年，Howgrave-Graham[20]给出了一种更容易实现和高效的算法，并证明了他的方法和Coppersmith的方法等价.但是由于他的方法只是对Coppersmith求解模上的一元多项式方程进行了改进，所以他的方法也只是局限于和Coppersmith方法一样求解明文的低比特的情况。 在99年美密会上，Boneh[5]等人把Howgrave-Graham的方法扩展到解两个未知数的模方程上。从而能够把这种方法应用到私钥和公钥的模多项式方程中，开创了用LLL算法分析RSA私钥的方法。在此之前，wiener[38]曾用连分数的方法分析RSA密码体制的私钥，并得出当小私钥d≤ο(N0.25)时是可以恢复私钥的。Boneh等人的格约化的LLL算法把RSA密码体制的私钥攻击范围提高到d

目录

文摘

英文文摘

声明

第一章引言

第二章背景知识

§2.1环Zn上的椭圆曲线的RSA密码体制

§2.2环Zn上的圆锥曲线的RSA密码体制

§2.3 LLL算法在解多未知数模上多项式方程的应用

第三章椭圆曲线和圆锥曲线的RSA型密码体制的短私钥攻击

§3.1求解椭圆曲线和圆锥曲线密码体制的小私钥攻击

§3.2通过添加效率项提高小私钥的求解范围

第四章部分密钥比特泄露攻击

§4.1当公钥e接近于N的时候

§4.1.1已知私钥d的高位比特的情况

§4.1.2已知私钥d的低比特部分的情况

§4.2当公钥e为任意大小的时候

§4.2.1已知私钥d的高位比特的情况

§4.2.2求解已知私钥d低比特的情况

第五章用3L算法分析多因子N=p1…pr的椭圆曲线和圆锥曲线的RSA型密码体制

§5.1私钥d是小私钥的时候

§5.2已知私钥d的高比特的情况

§5.3已知私钥d的低比特的情况

第六章对模上多项式方程解RSA问题的展望

参考文献

致谢