rsa加密算法的改進

rsa加密算法的改進

1計算最小pq、qqn的算法步驟sra是目前的國際標準。它的基礎是數(shù)據(jù)分布的困難。安全性依賴于大數(shù)據(jù)分布的困難，具有很強的保密性，在身份認證中得到了廣泛應用。RSA加密算法的過程是:(1)取兩個素數(shù)p和q;(2)計算n=pq,φ(n)=(p-1)(q-1);(3)隨機選取整數(shù)e,滿足gcd(e,φ(n))≡1;(4)計算d,滿足de≡1(modφ(n))。從以上的算法可以得到公鑰e、私鑰d、模n,其中e和n公開,私鑰d則自己保存,p、q和φ(n)作為中間結果不公開。加密算法:c=E(m)=me(modn)解密算法:m=D(c)=cd(modn)RSA加解密運算采用的都是模冪運算,其加解密的速度也取決于模冪運算,安全性取決于模n的素數(shù)分解。2rsa加密的步驟在RSA算法中,所涉及的運算都是大數(shù)運算,包括大數(shù)的賦值、加減、移位、清零等基本運算,以及建立在大數(shù)基本運算基礎上的乘除、取模、模冪、求最大公約數(shù)、乘法逆元等運算。從層次上看,大數(shù)運算基本可分成三層,第一層即最底層是大數(shù)的加減法和移位運算;第二層是大數(shù)的乘除法等運算;第三層是模冪、求最大公約數(shù)、乘法逆元等復雜運算,是RSA加密系統(tǒng)成功的關鍵,特別是模冪運算,其效率決定了RSA的效率。本文將RSA算法的改進主要放在模冪運算上。2.1窗口插裝閥的組合在普通模冪和Montgomery模冪處理中,都采用了“反復平方乘”運算,很明顯,對每個指數(shù)二進制位,為0時只需要一次乘法運算,為1時則需要兩次乘法運算(一次平方、一次乘法)。在指數(shù)運算改進中,只能從二進制位為1時附加的一次乘法運算著手,盡量減少指數(shù)二進制位為1產(chǎn)生的乘法運算,利用滑動窗口技術將一定大小的窗口范圍內(nèi)的二進制位組合在一起(要求窗口的最前、最后位必須為1,指數(shù)最高的一個區(qū)域窗口的最后位可以為0,這樣可以減少乘方運算),用一個乘法運算來代替。這部分處理首先調(diào)用模冪指數(shù)處理函數(shù)對指數(shù)部分進行預處理。指數(shù)處理函數(shù)根據(jù)指數(shù)E,返回的BYTE型指針和BYTE指針區(qū)域中的最高指數(shù)位Start_P。模冪改進算法中必須增加一個輔助的大整數(shù)數(shù)組A,數(shù)組的大小必須與窗口的大小相適應,在本文實現(xiàn)的程序中數(shù)組A的大小取32,A[i]=p12i+1modpb,p1為指數(shù)運算的底數(shù),pb為模數(shù),對于二進制指數(shù),如果每個BYTE>0,則取A[BYTE/2]與結果相乘,具體的算法與原運算基本相同。結果分析:對于一個二進制位為1000位的指數(shù),設0、1的概率相同,則原來需要1500次模乘(平方運算1000次,乘法運算500次),改進以后最多需要1194次模乘(其中包括輔助數(shù)組的運算32次,平方運算995次,乘法運算167次),理論上總體性能可提高20%。2.2、都是以uint為單位的表達且u從Montgomery模乘運算的實現(xiàn)過程中的“s=Tn′modR”可以發(fā)現(xiàn),由于R取了一個特殊的數(shù)據(jù),設R以UINT為單位表示的長度為len,則對R取模只要保留低len-1個單元即可,因此可以將Montgomery模乘運算的取模結合到乘法運算中實現(xiàn),基本思想如下:設α、β都是以UINT為單位表示的大數(shù),長度都為m,即可以表示如下:α=αm-1αm-2……α1α0β=βm-1βm-2……β1β2則根據(jù)乘法原則:αβ=∑i,j=0mαiβjBOXi+jαβ=∑i,j=0mαiβjBΟXi+j其中BOXi+j表示在整個大數(shù)當中的位置。由于對R取模只要保留低的len-1個單元,所以計算乘法時只要計算低len-1個單元即可,而不必計算全部:αβmodR=∑i,j=0i+j<lenαiβjBOXi+jR=∑i,j=0i+j<lenαiβjBΟXi+j在Montgomery模乘運算中所采用的大數(shù)長度一般比R少一個單元,假設都為len-1,則乘法和取模結合在一起需要len2/2的塊乘法運算,這比先乘再取模的常規(guī)方法(需要(len-1)2塊乘法運算)的計算量減少了大約一半。2.3提高大數(shù)的采用速度在Montgomery模冪運算中,調(diào)用Montgomery模乘時兩個乘數(shù)有2/3的概率相同,即A=B。在整個Montgomery模乘運算中,A×B是比較復雜的運算,因此提高大數(shù)的平方速度,對整個RSA計算十分有利。設α=αm-1αm-2……α1α0,其中αi都是UINT型數(shù)據(jù),則:α2=2×∑0≤j≤i0<i<m?1αiαjBOXi+j+∑i=0m?1α2iBOX2iα2=2×∑0≤j≤i0<i<m-1αiαjBΟXi+j+∑i=0m-1αi2BΟX2i改進的大數(shù)平方運算需要(m+1)×m/2次乘法塊運算,比常規(guī)的大數(shù)乘法(需要m2次乘法塊運算)減少了幾乎一半的復雜度。而且在運算過程中,還可以將取模運算結合在一起,運算過程中只要保留一定的單元即可。3加密算法的成員RSA加密算法是在大數(shù)運算的基礎上實現(xiàn),整體功能封裝在如下的類CRsa中。類CRsa包含的4個成員變量中,e、d、n分別為RSA加密算法的公鑰、私鑰和模,nlen為模n的16進制位數(shù)。SetEN、SetDN函數(shù)根據(jù)兩個CString輸入?yún)?shù)設定e、n或d、n,并根據(jù)n的16進制位數(shù)給出nlen值。在RSA加密或解密之前必須給出相應參數(shù)。3.1密鑰參數(shù)的計算RSA密鑰參數(shù)的獲取通過類CRsa的成員函數(shù)GetKey完成,GetKey函數(shù)根據(jù)輸入的兩個素數(shù)P、Q和公鑰e的要求長度elen計算密鑰參數(shù)。由于所使用的是基于Miller-Rabin測試的概率性素數(shù),因此在獲取RSA密鑰參數(shù)以后,計算(eemodn)dmodn,根據(jù)最后的結果判斷密鑰參數(shù)獲取是否正常。3.2不同輸出接口的處理RSA加密采用模冪函數(shù)完成。類CRsa中封裝了兩個加密函數(shù),兩個加密函數(shù)基本處理過程相同,只是針對不同的輸入輸出接口。以輸入?yún)?shù)為字符串的加密函數(shù)為例,首先使用加密函數(shù)將輸入字符串以每個字符用兩個16進制位表示轉化為一個大整數(shù),再使用加密函數(shù)將大整數(shù)轉換為字符串,每個16進制位用1個字符表示,最后輸出結果。3.3輸出接口接口函數(shù)RSA解密與RSA加密基本一致,同樣采用模冪函數(shù)完成,類CRsa中封裝了兩個解密函數(shù),針對不同的輸入輸出接口實現(xiàn)。與加密過程不同的是,在模冪運算之前,每次取nlen個字符轉化為一個大整數(shù),每個字符(16進制數(shù)的ASCII碼)轉化為一個16進制數(shù),在模冪運算之后,將得到的結果轉化為字符串輸出,每個UINT單元轉化為4個字符。4計數(shù)響應面測試對RSA算法的測試,在DELLPC機上完成,其環(huán)境配置為:CeleronCPU2.4G、內(nèi)存512M、WindowsServer2003,程序用VC++6.0編寫。測試分兩部分進行,素數(shù)獲取的速度測試結果見表1,RSA加密的速度見表2。素數(shù)獲取速度采用連續(xù)產(chǎn)生100個要求長度的素數(shù)取平均。加密速度采用連續(xù)1000次運算取平均。MEB、SMEB、SME分別為Montgomery模冪運算、指數(shù)改進的Montgomery模冪運算、模