rsa的安全性分析

rsa的安全性分析

r.l.r.a.shamor和l.adreman提出的一套理論上最成熟、最成熟的密鑰鎖制度是由結(jié)論構(gòu)建的。RSA的理論基礎(chǔ)是數(shù)論中的歐拉定理,它的安全性是基于數(shù)論和計(jì)算復(fù)雜理論中的下述論斷:求兩個(gè)大素?cái)?shù)的乘積是計(jì)算上容易的,但是要分解兩個(gè)大素?cái)?shù)的積求出它的素因子則是計(jì)算上困難的。一、拉馬拉馬定理歐拉定理:若n,a為正整數(shù),有g(shù)cd(a,n)=1,則aφ(n)=1(modn)。其中φ(m)稱為歐拉函數(shù),它是比n小但與n互素的正整數(shù)個(gè)數(shù)。歐拉定理也有一種等價(jià)形式:aφ(n)+1=a(modn)。費(fèi)爾馬定理:如果n是素?cái)?shù),且gcd(m,n)=1,則mn-1=1(modn),費(fèi)爾馬定理還存在另一種等價(jià)形式:如果n是素?cái)?shù),m是任意正整數(shù),則mn=m(modn)。對(duì)于素?cái)?shù)n來(lái)說(shuō),φ(n)=n-1,所以費(fèi)爾馬定理實(shí)際是歐拉定理的一個(gè)推論。RSA算法采用下述加密/解密變換:1、模的乘子法(1)選擇兩個(gè)保密的大素?cái)?shù)p和q。(2)計(jì)算N=pq,φ(N)=n-1,其中φ(N)是N的歐拉函數(shù)值。(3)選擇一個(gè)整數(shù)e,滿足1<e<φ(N),且gcd(φ(N),e)=1。(4)計(jì)算私鑰d(解密密鑰),滿足ed=1(modφ(N)),d是e在模φ(N)下的乘法逆元,因e與φ(N)互素,由模運(yùn)算可知,它的乘法逆元一定存在。(5)以(e,N)為公鑰,(d,N)為密鑰,銷毀p,q,φ(N)。2、分組的兩組對(duì)應(yīng)加密時(shí)首先將明文比特串進(jìn)行分組,使得每個(gè)分組對(duì)應(yīng)得串在數(shù)值上小于N,即分組的二進(jìn)制長(zhǎng)度小于log2N。然后,對(duì)每個(gè)明文分組M,作加密運(yùn)算:C=Ek(M)=Me(modN)3、解密配置對(duì)密文分組的解密運(yùn)算為:M=Dk·(C)=Cd(modN)由歐拉定理可以證明解密運(yùn)算能恢復(fù)明文M。二、ra算法的實(shí)現(xiàn)1、或中小型企業(yè)最常使用的二進(jìn)制算法有兩種,一種是硬件資源需求較大的right-to-left二進(jìn)制法,該方法實(shí)現(xiàn)較快;一種是left-to-right二進(jìn)制法,是基于硬件資源的有效利用。前者平方和模乘運(yùn)算相互獨(dú)立,可以進(jìn)行平行處理;后者模乘運(yùn)算和平方可不間斷執(zhí)行,能夠在同一個(gè)硬件乘法器上執(zhí)行,節(jié)約面積又不影響運(yùn)算速度。算法12、smm算法的基本思想基于乘同余對(duì)稱特性的SMM算法是利用乘同余對(duì)稱特性來(lái)減少RSA加密、解密計(jì)算中乘法和求模運(yùn)算量的一種快速算法。RSA加密是對(duì)明文求冪剩余的過(guò)程,傳統(tǒng)的RSA算法是將指數(shù)表示成t位二進(jìn)制的形式,并將冪剩余變成一系列乘同余的迭代,由傳統(tǒng)實(shí)現(xiàn)算法的分析可以知道,仍以a=gemodn為例,每一步迭代必有運(yùn)算a=a2(modn)和可能有運(yùn)算a=a*g(modn)。SMM算法是在每步迭代計(jì)算中對(duì)乘數(shù)和被乘數(shù)進(jìn)行有條件的代換:如果ai-1表示第(i-1)步迭代結(jié)果,則在進(jìn)行第i步迭代時(shí),若ai-1≤(n-1)/2或g≤(n-1)/2,則保持原數(shù)不變,但是如果ai-1>(n-1)/2或g>(n-1)/2,則使用n-ai-1或(n-g)來(lái)代替ai-1或g。迭代次數(shù)取決于其漢明重量,即指數(shù)二進(jìn)制化后的非零元素個(gè)數(shù)及二進(jìn)制長(zhǎng)度。通過(guò)迭代,可使兩個(gè)相乘數(shù)保持在一個(gè)較小的范圍內(nèi),有利于提高數(shù)據(jù)的計(jì)算效能,隨著迭代次數(shù)的增加算法改善的效果將不斷提升。3、時(shí)連續(xù)的多個(gè)零的可能滑動(dòng)窗口技術(shù)可將一個(gè)二進(jìn)制數(shù)轉(zhuǎn)換成具有最少非0數(shù)字的編碼形式,再通過(guò)預(yù)處理提高運(yùn)算速度?？梢赃@樣描述:設(shè)定窗口大小為k,從大整數(shù)E的首位1開始,向右k位記為Wk-1,Wk-1后連續(xù)的若干個(gè)零(可能為0個(gè))記為Ok-1;從Ok-1后的1開始k位記為Wk-2,Wk-2后的連續(xù)若干個(gè)零記為Ok-2,如此下去,最后的1開始的若干位(可能不足k位)記為W0,若W0=k,且其后還有若干0,則其后若干0記為O0,則E可表示成為了方便的在大整數(shù)模乘運(yùn)算中使用滑動(dòng)窗口法,需要?jiǎng)?chuàng)建三個(gè)線性表X、T、L用來(lái)存儲(chǔ)相應(yīng)中間值。采用滑動(dòng)窗口技術(shù)對(duì)乘數(shù)B的二進(jìn)制形式重新編碼,非0元素存入X,滑動(dòng)窗口編碼碼元與另一乘數(shù)A的模乘的值存入T,L用以保存X中相鄰元素與A相乘的倍乘次數(shù)差。最后根據(jù)三個(gè)線性表中存儲(chǔ)的值來(lái)計(jì)算。三、提高算法如果將前文所述算法進(jìn)行選擇性組合,汲取各自優(yōu)點(diǎn),則可構(gòu)建一新型適用范圍更廣運(yùn)算速度更快的改進(jìn)算法。(以a≡gemodn為例)1、將指數(shù)e轉(zhuǎn)換為二進(jìn)制形式2、相鄰元素倍乘次數(shù)差的計(jì)算取變量x=n/2,用以基于乘同余對(duì)稱特性的SMM算法簡(jiǎn)化過(guò)程中乘數(shù)的判斷。創(chuàng)建三個(gè)線性表X、T、L。其中X用以存放其中g(shù)重新編碼后的非0元素,T用以存放(g,g3,…,g2k-1)modn的值,L用以保存X中相鄰元素與g相乘的倍乘次數(shù)差。最后根據(jù)三個(gè)線性表中存儲(chǔ)的值來(lái)計(jì)算。其具體實(shí)現(xiàn)步驟如下:(1)預(yù)計(jì)算(1)g1←g,g2←g2;(2)對(duì)i從1到2k-1-1,執(zhí)行g(shù)2i+1←g2i-1g2modn。(2)s←1,i←t;(3)當(dāng)i≥0,執(zhí)行:(1)如果ei=0,則計(jì)算s←s2,i←i-1;定理1:若數(shù)據(jù)的二進(jìn)制表示中不含有0位,則最優(yōu)寬度滿足不等式:四、同優(yōu)勢(shì)組合形成算法對(duì)基于大數(shù)模冪運(yùn)算為算法核心的RSA算法,一個(gè)重要的研究方向就是其運(yùn)算效率如何提升。以當(dāng)前實(shí)現(xiàn)算法為基礎(chǔ),充分結(jié)合各自不同優(yōu)勢(shì)進(jìn)行組合形成新的算法,能夠有效的提高運(yùn)算效率,對(duì)RSA算法的推廣應(yīng)用具有重要的意義。算法2模冪運(yùn)算可看做是模乘