rsa加密算法的改進(jìn)

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