rsa算法實現(xiàn)數(shù)據(jù)加密、數(shù)字簽名、秘鑰交換

rsa算法實現(xiàn)數(shù)據(jù)加密、數(shù)字簽名、秘鑰交換

1n取不同體積的結(jié)論和證明1.1當(dāng)n=p#q時的證明方法假設(shè)n.p.q.r，并嘗試導(dǎo)出烏拉函數(shù)參數(shù)（n）。根據(jù)準(zhǔn)(n)的定義,我們要求小于n并且和n互質(zhì)的正整數(shù)的個數(shù)?？紤]到在小于n且和n不互質(zhì)的所有數(shù)中,有的是p的倍數(shù),有的是q的倍數(shù),有的是r的倍數(shù),有的既是p又是q的倍數(shù),有的既是q又是r的倍數(shù),還有的既是r又是p的倍數(shù)。為了表示方便,我們用S(x)表示小于n的且是x的倍數(shù)的正整數(shù)的個數(shù)?？梢钥闯鲇嬎憬Y(jié)果十分巧,正好是p、q、r歐拉函數(shù)的乘積。事實上這絕非巧合。這說明用當(dāng)n=p*q時的證明方法也同樣適用于上述情況(證明見下面1.1.2)。換言之,此時RSA算法依然成立。1.2d準(zhǔn)n算法變?yōu)?(1)選定p、q、r三個質(zhì)數(shù)(非公開)(2)計算n=p*q*r(公開)(3)選擇e使得gcd(準(zhǔn)(n),e)=1;1<e<φ(n)(公開)正確性證明:情況1:若M、p不互質(zhì),則質(zhì)數(shù)p能整除M,顯然p也能整除M^(k(p-1)(q-1)(r-1)+1),那么:M^(k(p-1)(q-1)(r-1)+1)modp=Mmodp=0情況2:若p、q互質(zhì),根據(jù)歐拉定理M^準(zhǔn)(p)modp=1,有1.3rsa算法是否適用于描述ra-觀點根據(jù)上面三個數(shù)的證明過程,很容易想到若n取m個質(zhì)數(shù)的乘積,結(jié)果會如何呢?由歸納演繹的思想,設(shè)n=a1*a2*…*am我們試著計算準(zhǔn)(n)得到這個結(jié)果之后,我們可以作出和上面類似的假設(shè),當(dāng)n取m個數(shù)的乘積時,RSA算法仍然成立,并在下面證明之1.4n整除[m算]k-1,2-1,m正確性證明:根據(jù)1.1.2中的證明方法,我們可以很容易得出因此,n整除[M^(k(a1-1)(a2-1)…(am-1)+1)-M]存在一整數(shù)x使22不同的質(zhì)數(shù)和多質(zhì)數(shù)之間的差異2.1rsa算法的運用到了一個一般的規(guī)則不論n取兩個質(zhì)數(shù)之積還是多個質(zhì)數(shù)之積,加密解密過程沒有差別。這是因為根據(jù)RSA算法的過程,在利用p、q、r…算出n之后他們就被丟掉并不再使用了。加密解密只需要用到公鑰對(e,n)和私鑰對(d,n)2.2解決時間2.2.1用一個質(zhì)數(shù)作為攻擊對象對于攻擊者來說,破解時間是有差別的。假設(shè)攻擊者采用強行猜測p、q的攻擊方法。如果他知道算法中使用的n到底是多少個質(zhì)數(shù)的乘積,那么,以n=p*q為例,他最多需要猜測n^(1/2)便能夠猜到p、q其中之一,另一個數(shù)也自然被知曉。所以破解算法時間復(fù)雜度為O(n^(1/2))。2.2.2多個質(zhì)數(shù)的解釋時間可以看到由于n比較大,隨著m的增加,猜測時間會越來越小。2.3質(zhì)數(shù)的保密程度根據(jù)上述討論,若攻擊者能夠提前知道組成n質(zhì)數(shù)的個數(shù)m,那么似乎原始的RSA公鑰算法已經(jīng)比較保險了。但是,正如本文上面所提到的,p、q、r、s…這些質(zhì)數(shù)是非公開的,并且在一次使用后丟棄。m的保密程度和p、q的保密程度是一樣的,換言之,攻擊者不知道?！鞠罗D(zhuǎn)第51頁】這就使得我們在確定n時盡可以選擇隨機個質(zhì)數(shù)的乘積變得可行。3基于gcd的攻擊仿真基于2.3的討論以及上面所有的結(jié)論,可以對RSA算法進行一些改進。在確定n時,先取1個隨機數(shù)m,再取n等于m個素數(shù)的乘積。由于攻擊者并不知道m(xù)的數(shù)值,所以其在攻擊時必須先猜測m。m最大不會超過log2(n)。當(dāng)然可以自行定義m的最大值k。改進后的算法如下:(1)選擇隨機數(shù)m;m<k<=log2(n),(非公開)(2)選定a1,a2…m個質(zhì)數(shù)(非公開)(3)n=a1*a2*a3…am(公開)(4)選擇e使得gcd(準(zhǔn)(n),e)=1;1<e<準(zhǔn)(n)(公開)limn^(1/2)+2n^(1/3)+3n^4+…+mn^(1/(m+1)),其中m趨向于log2(n)4算法的基本思想為了證明改進方案的可行性,現(xiàn)對其進行模擬(4)計算(求e的逆元,非公開)證明目標(biāo):M^edmodn=M(M可以看作明文)首先我們證明M^(k(p-1)(q-1)(r-1)+1)modp=Mmodp--算法:見1.1.2,只不過這里n=a1*a2*…*am證明目標(biāo):M^edmodn=M(M可以看作明文)若n=p*q*r,試想,若p,q,r中有一個很小,一下子被猜到了,那么n較大時退化為剛剛n=p*q的情況。若p、q、r大小差不多,那么攻擊者猜測第一個數(shù)的時間為n^(1/3),此外,他需要n^(1/3)的時間來猜測第二個數(shù),進而第三個數(shù)也被知曉,這也是他所需的最長時間。此時時間復(fù)雜度為O(2n^(1/3))。