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

论文摘要

96欧密会上，Coppersmith[11]提出了用求解最短格的LLL算法，来求解模多项式，并把这种方法用在求解RSA明文中的低比特部分；（M+M0）e=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≤O(N0.25)时是可以恢复私钥的．Boneh等人的格约化的LLL算法把RSA密码体制的私钥攻击范围提高到d<N0.292，证明了LLL分析RSA密码体制有很好的效果和扩展前景．在Coppersmith和Boneh等人的开创性工作后，又有好多人对这种LLL算法攻击RSA密码体制的方法进行扩展．如：May，Bl（o|¨）mer[3]和Hinek[16]等人对这种LLL算法的RSA攻击进行了扩展，使得知道私钥d的高位和地位比特时，仍可以用格约化的LLL算法来求解那些未知部分比特．Hinek,Teske[16]等人分析n是多个平衡素数因子乘积的情况等．在07年中国密码会上，孔凡玉[31]等人认为环上的圆锥曲线上RSA密码体制也可以用格约化的LLL方法进行求解．并给出了p+1和q+1最大公约数等于2的情况下，环上的圆锥曲线RSA密码体制的格约化攻击方法．本文对的环上的圆锥曲线和椭圆曲线上的RSA公钥密码体制用格约化的LLL算法进行分析，并对p+1和q+1最大公因数大于2情况下对更多未知数模上多项式方程进行求解．得出当小比特私钥d≤O(N1/4-3/2γ)时，可以用LLL算法求解模上多项式方程的方法恢复小私钥，其中公因子（?）1=O（Nγ）．这种情况其实是Boneh等人所求解的模上多项式方程的一个更为普遍地情况．本文还继续分析了即使密钥较大的情况下，暴露部分比特时，仍可以用格约化的LLL算法进行有效分析．这种分析其实是对Bl（o|¨）mer和May等人用LLL算法对RSA分析在椭圆曲线和圆锥曲线上密码体制的扩展，即如果暴露了一定量的高位比特密钥时，是能够恢复椭圆曲线和圆锥曲线上密码体制的私钥的未知低比特部分：当已知私钥的（?） = O（Nβ）高位比特时，如果β≤1/2，而未知的低位部分O(N4γ+3/4-β-δ)≤d0≤O(N5/4+β-4γ-δ)时，我们是可以恢复私钥的；当已知私钥的（?） = O（Nβ）高位比特时，如果β≥1/2，而如果未知的低位部分O(N4γ+3/4-δ-β≤d0≤O(N9/4-β-4γ-δ时，我们是可以恢复私钥的；同理，如果暴露了一定量的低位比特密钥，密钥未知高比特部分也是能够恢复的：已知私钥的（?）=O（Nβ）低比特时，如果未知的高位部分d0≤O(N5/4-2γ-1/4（?）)，是可以恢复私钥的．本文还把Hinek,Teske等人分析n是平衡素数乘积的方法扩展到椭圆曲线和圆锥曲线的RSA密码体制中．当n有r个平衡因子的情况下，短私钥d≤（?）时是可以恢复私钥的．如果私钥比较大，但是已知其高位或低位的部分比特，如果满足一定条件，也可以恢复那部分未知比特的：当已知私钥的（?） = O（Nβ）高位比特时，其中β≤1/r，如果未知的低位部分O(N4γ+3/2-3/2r+β-δ)≤d0≤O(N1/2+3/2r+β-4γ-δ)，我们是可以恢复私钥的未知比特的；当已知私钥的（?）=O（Nβ）高位比特时，其中β≥1/r，如果未知的低位部分O(N4γ+3/2-3/2r-β-δ≤d0≤O(N3/2+3/2r-β-4γ-a)，我们是可以恢复私钥的未知比特的；当已知私钥的（?）=O（Nβ）低位比特时，如果未知的高位部分d0≤（?），我们是可以恢复私钥的未知比特的．

论文目录

• 中文摘要
• 英文摘要
• 第一章 引言
• 第二章 背景知识
• n上的椭圆曲线的RSA密码体制'>§2.1 环Z_n上的椭圆曲线的RSA密码体制
• n上的圆锥曲线的RSA密码体制'>§2.2 环Z_n上的圆锥曲线的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低比特的情况
• 1…p_r的椭圆曲线和圆锥曲线的RSA型密码体制'>第五章 用LLL算法分析多因子N=p₁…p_r的椭圆曲线和圆锥曲线的RSA型密码体制
• §5.1 私钥d是小私钥的时候
• §5.2 已知私钥d的高比特的情况
• §5.3已知私钥d的低比特的情况
• 第六章 对模上多项式方程解RSA问题的展望
• 参考文献
• 致谢
• 学位论文评阅及答辩情况表