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

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

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

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

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

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

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

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

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