rsa的安全性分析

rsa的安全性分析

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