RSA體制通過解密指數(shù)d分解模N的分析.pdf

1、作為第一個(gè)廣泛應(yīng)用的公鑰密碼體制，RSA的安全性一直是密碼學(xué)界研究的熱點(diǎn)。密碼學(xué)家對RSA公鑰密碼體制的安全性進(jìn)行了全面的分析。1990年Winner在中證明了，對于每一個(gè)RSA公私鑰對，只要滿足d＜1/3N1/4，那么可以使用連分?jǐn)?shù)的方法在多項(xiàng)式時(shí)間內(nèi)分解N=p·q。之后，Coppersmith利用格理論以及LLL算法的相關(guān)結(jié)論提出了一種求同余方程小根的方法，該方法被Boneh、Durff以及May用于分析RSA安全性，并得到了和Wi

2、nner相似的結(jié)論。經(jīng)過May等人的研究，Coppersmith方法已經(jīng)形成一套規(guī)范化的步驟，被廣泛應(yīng)用于RSA安全性分析。
　　 關(guān)于RSA安全性有一個(gè)比較有名的基本問題就是已知公私鑰對（N，e,d)是否可以分解N=p·q，該問題有一個(gè)概率多項(xiàng)式時(shí)間的算法，但是確定性多項(xiàng)式時(shí)間的算法直到2007年才被J.Coron和A.May找到。Coron和May給出了通過利用Coppersmith方法在多項(xiàng)式時(shí)間分解N=p·q的過程，整個(gè)

3、算法的時(shí)間復(fù)雜度是(O)(log9N)。
　　 在Coron的文章中，他使用了同余方程組U=e·d-1=0modφ，φ(N)=N-s=0 modφ，s=p+q-1，并假設(shè)已知s的高位比特s0，即s=(x)0+s0X，0≤(x)0＜X對于某個(gè)已知的X。利用上述同余方程組，Coron構(gòu)造了如下一系列多項(xiàng)式gij(x)=xi·（x-N+x0X）j·Um-j，for{0≤j≤m,i=0 j=m，1≤i≤k可以看出對于所有的(i，j)都有

4、gij(x0)=0 modφm.通過對上述方程利用LLL算法求解，Coron證明了當(dāng)e·d≤ N2的時(shí)候，可以在確定性多項(xiàng)式時(shí)間內(nèi)分解N.
　　 本文在上述結(jié)論基礎(chǔ)上進(jìn)一步考慮了p,q間關(guān)系以及對上述結(jié)論的影響。通常情況下，為了防止N被常見的因子分解算法順利的分解，RSA參數(shù)選擇的過程對N有嚴(yán)格的要求。其中之一就是p和q是平衡的，即p和q有相同的比特長度，或者p-q比較小。可以看出由于p·q=N，在這種情況下s=p+q-2(√)

5、N比較小。假設(shè)s=Nδ，U=e·d=Nα，本文證明在α，δ滿足關(guān)系α·δ＜1時(shí)，N在確定多項(xiàng)式時(shí)間內(nèi)可以分解。
　　 本文通過構(gòu)造兩個(gè)不同的同余方程分別得到上述結(jié)論。考慮RSA關(guān)系式e·d=k(N-p-q+1)=1.假設(shè)A=N+1-2(√)N，第一種方法利用了同余方程k(A-s)=1 mod U,構(gòu)造目標(biāo)求解方程fU(x，y)=x(y-A)-1，然后采用提到的方法構(gòu)造了以下一系列方程gi1i2(x，y)=xi1yi2/lkfU(

6、x，y)kUm-k，(詳細(xì)定義可見第2章相關(guān)內(nèi)容）可以看出對于以上方程都有解(k,s)。對上述方程通過LLL算法求解，通過相應(yīng)的分析即可得到本文的結(jié)論。本文的第二種方法采用了類似Coron文章中的同余方程，文中簡單介紹了相關(guān)過程，然后對新的參數(shù)條件進(jìn)行分析得到和方法一同樣的結(jié)論。
　　 在論文的第3章分析了一種RSA的變種，這個(gè)新的RSA方案中采用了prq形式的RSA模，這里同樣假設(shè)p，q平衡的情況。在這個(gè)方案中φ(N)=pr-

7、1(p-1)(q-1)=N-pr-1(p+q-1)，假設(shè)U=e·d=Nα，可構(gòu)造同余方程1+k·(pr-1(p+q-1）-N)=0 mod U相應(yīng)的目標(biāo)求解方程為fU（x，y，z）=x(y(z-1)-N）+1，通過這個(gè)方程求小值解（k，pr-1，p+q）.論文找出了(r)和α之間的關(guān)系，在這種關(guān)系下，通過解密指數(shù)d分解N存在多項(xiàng)式時(shí)間確定性算法。在原始RSA體制中，一般情況下都滿足條件α·δ＜1，所以結(jié)論較好。在模prq形式的RSA變種