橢圓曲線和圓錐曲線的RSA密碼體制的攻擊.pdf

1、96歐密會上，Coppersmith[11]提出了用求解最短格的LLL算法，來求解模多項式，并把這種方法用在求解RSA明文中的低比特部分：(M+Mo)c：C mod N中的低比特部分M0.這是第一種對RSA密碼體制的LLL算法的攻擊方法，開創(chuàng)了用求最短格的方法分析RSA密碼體制的先例. 由于Coppersmith的開創(chuàng)性地工作，以及對RSA較好的分析效果，很多學者開始對他的方法進行了深入研究，并對他的方法進行了各種改進。98年，

2、Howgrave-Graham[20]給出了一種更容易實現(xiàn)和高效的算法，并證明了他的方法和Coppersmith的方法等價.但是由于他的方法只是對Coppersmith求解模上的一元多項式方程進行了改進，所以他的方法也只是局限于和Coppersmith方法一樣求解明文的低比特的情況。 在99年美密會上，Boneh[5]等人把Howgrave-Graham的方法擴展到解兩個未知數(shù)的模方程上。從而能夠把這種方法應用到私鑰和公鑰的模多

3、項式方程中，開創(chuàng)了用LLL算法分析RSA私鑰的方法。在此之前，wiener[38]曾用連分數(shù)的方法分析RSA密碼體制的私鑰，并得出當小私鑰d≤ο(N0.25)時是可以恢復私鑰的。Boneh等人的格約化的LLL算法把RSA密碼體制的私鑰攻擊范圍提高到d

4、擴展.如：May，Blomer[3]和Hinek[16]等人對這種LLL算法的RSA攻擊進行了擴展，使得知道私鑰d的高位和地位比特時，仍可以用格約化的LLL算法來求解那些未知部分比特。Hinek，Teskef[6]等人分析n是多個平衡素數(shù)因子乘積的情況等. 在07年中國密碼會上?？追灿馵31]等人認為環(huán)上的圓錐曲線上RSA密碼體制也可以用格約化的LLL方法進行求解.并給出了p+1和q+1最大公約數(shù)等于2的情況下，環(huán)上的圓錐曲線R

5、SA密碼體制的格約化攻擊方法. 本文對的環(huán)上的圓錐曲線和橢圓曲線上的RSA公鑰密碼體制用格約化的LLL算法進行分析，并對p+1和q+1最大公因數(shù)大于2情況下對更多未知數(shù)模上多項式方程進行求解.得出當小比特私鑰d≤0(Nγ)時，可以用LLL算法求解模上多項式方程的方法恢復小私鑰，其中公因子d1=O(Nγ)。這種情況其實是Boneh等人所求解的模上多項式方程的一個更為普遍地情況. 本文還繼續(xù)分析了即使密鑰較大的情況下，暴露部

6、分比特時，仍可以用格約化的.LLL算法進行有效分析.這種分析其實是對Bl(o)mer和May等人用LLL算法對RSA分析在橢圓曲線和圓錐曲線上密碼體制的擴展，即如果暴露了一定量的高位比特密鑰時。是能夠恢復橢圓曲線和圓錐曲線上密碼體制的私鑰的未知低比特部分； 當已知私鑰的d=O(Nβ)高位比特時.如果β≤1/2，而未知的低位部分O(N4γ+3/4-β-δ)≤d0≤O(N3/4+β-4γ-δ)時，我們是可以恢復私鑰的； 當已

7、知私鑰的d=O(Nβ)高位比特時，如果β≥1/2，而如果未知的低位部分O(N4γ+3/4-δ-β)≤d0≤O(N9/4-4γ-δ)時，我們是可以恢復私鑰的； 同理，如果暴露了一定量的低位比特密鑰，密鑰未知高比特部分也是能夠恢復的t已知私鑰的d=O(Nβ)低比特時。如果未知的高位部分d0≤O=(N3/4-2γ-1/4 )，是可以恢復私鑰的。 本文還把Hinek,Teske等人分析n是平衡素數(shù)乘積的方法擴展到橢圓曲線和圓錐曲

8、線的RSA密碼體制中.當n有r個平衡因子的情況下，短私鑰時是可以恢復私鑰的。 如果私鑰比較大。但是已知其高位或低位的部分比特，如果滿足一定條件，也可以恢復那部分未知比特的： 當已知私鑰的d=O(Nβ)高位比特時，其中β≤1/r，如果未知的低位部分(O)(N4γ+3/2-3/2τ-β-δ)≤d0≤(O)(N1/2+3/2τ+β-4γ-δ)，我們是可以恢復私鑰的未知比特的；當已知私鑰的~d=(O)(Nβ)高位比特時，其中β≥