|
1. RSA 算法概述 公開密鑰算法是在1976年由當時在美國斯坦福大學的迪菲(Diffie) 和赫爾曼(Hellman)兩人首先發(fā)明的，但目前最流行的RSA 是由分別取自三位發(fā)明此算法的數(shù)學家RonaldRivest,Adi Shamir 和Len Adleman的名字的第一個字母來構成的。[1] RSA 已被國際上一些標準化組織如ISO、ITU 等作為標準采用,現(xiàn)在流行的PGP 也采用RSA 算法作為其解密和數(shù)字簽名算法。它是第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法。 但RSA 的安全性一直未能得到理論上的證明。RSA 的安全性依賴于大數(shù)難于分解這一特點。據(jù)猜測，從一個密鑰和密文推斷出明文的難度等同于分解兩個大素數(shù)的積。并且 RSA的加密算法速度與對稱加密算法相比，其速度非常緩慢的。因此，研究快速的 RSA 算法是十分有意義的。至今，人們在此方面已經(jīng)作了很多的研究，提出了許多快速的RSA 算法。其中分塊模冪算法[2]，冪等價代換的改進[3]及 SMM 算法[4]等都極大的提高了 RSA 加密算法的速度。 2. RSA 算法的基本原理 RSA 體制用戶i 的公開加密變換Ei 和保密的解密變換Di 的產(chǎn)生:(1)隨機選取素數(shù)pi 和qi；(2)計算ni= piqi,Ф(ni)=(pi-1)(qi-1)；(3)隨機選取整數(shù)ei 滿足(ei,Ф(ni)) =1;(4)利用歐幾里得算法計算di,滿足eidi≡1 MOD Ф(ni);(5)公開ni,ei 作為Ei,記為Ei=< ni,ei>,保密pi,qi,di,Ф(ni)作為Di,記為Di= 3. RSA 算法的舉例
要對2 運用RSA 算法進行加密，因為RSA 的原則是被加密的信息應該小于p 和q 的較小者，因此取p=5, q=3，求得n=p*q=5*3=15，m=(p-1)*(q-1)=(5-1)*(3-1)=8，然后生成較小的數(shù)e,使e 與8 互質(zhì),2 不對,3 是最小的,于是e=3 最后生成d,使d*e MOD m=1 , d*3 MOD8=1,d*3 除以8 余數(shù)為1，于是算出d=3，所以求出公鑰e=3,n=15.私鑰d=3,n=15.密鑰計算完畢。加密:c=pe%n=23%15=8%15=8, 于是密文為8. 把8 傳出去。同時應把公鑰也傳出去,好在收到時知道對應的是那個私鑰。解密過程:接收者收到密文和公鑰,找到對應的私鑰:p=cd%n=83%15,經(jīng)過運算，余數(shù)為2。
4.1 RSA 算法的改進 由于RSA 算法是基于大數(shù)分解的理論，應用了費爾馬小定理[123123123]，在兩個素數(shù)qi 和pi 的乘積n 被分解是最主要的攻擊方法，因此提出了三重RSA 算法：用戶j 的公開加密變換Ej 和保密的解密變換Dj 的產(chǎn)生:
(1)隨機選取三個素數(shù)pj、qj 和rj；
(2)計算nj= pj*qj*rj,Ф(nj)=(pj-1)(qj-1)(rj-1)；
(3)隨機選取整數(shù)ej 滿足(ej,Ф(nj)) =1;
(4)利用歐幾里得算法計算dj,滿足ei*di≡1 MOD Ф(nj);
(5)公開nj,ej 作為Ej,記為Ej=< nj,ej>,保密pj,qj,rj,dj,Ф(nj)作為Dj,記為Dj=< pj,qj,rj,dj,Ф(nj)>。加密算法:c = Ej(m) = mej(MOD nj),解密算法:m = Dj(c) = cdj(MOD nj),在RSA 算法中,包含兩個密鑰:加密密鑰PK 和解密密鑰SK,加密密鑰公開。
由于三重的RSA 算法成立，原來的RSA 算法也成立，因此推斷N 重RSA 算法即：用戶x 的公開加密變換Ex 和保密的解密變換Dx 的產(chǎn)生:
(1)隨機選取N 個素數(shù)p1、p2……pn；
(2)計算nx= p1*p2……*pn,Ф(nx)=(p1-1)*(p2-1)*……*(rj-1)；
(3)隨機選取整數(shù)ex 滿足(ex,Ф(nx)) =1;
(4)利用歐幾里得算法計算dx,滿足ex*dx≡1 MOD Ф(nx);
(5)公開nx,ex 作為Ex,記為Ex=< nx,ex>,保密p1,p2,……,pn,Ф(nx)作為Dx,記為Dx= 下面對N 重RSA 算法給與證明。
應用2.2中提出的定理1：
若p, q是相異質(zhì)數(shù), d*e==1 MOD (p- 1)(q- 1), a 是任意一個正整數(shù)b==aeMOD p*q,c==bdMOD p*q, 則c==a MOD p*q。
可以得出推論1：
若p1,p2,……,pn是相異質(zhì)數(shù), d*e==1 MOD (p1- 1)*(p2- 1)*……*（pn-1）, a 是任意一個正整數(shù)b==aeMOD p1*p2*……*pn, c==bdMOD p1*p2*……*pn, 則c==a MODp1*p2*……*pn。
證明推論1的過程中過程如下:
由n（n>=2）個質(zhì)數(shù)時，推論1成立。
當n+1時d’*e’==1 MOD(p1- 1)*(p2- 1)*……*pn*（p(n+1)-1）a’是任意一個正整數(shù)
b’==a’e’MOD p1*p2*……*pn*p(n+1), ①
c’==b’d’MOD p1*p2*……*pn*p(n+1) ②
由于里面的a’、b’、p1,p2,……,pn, p(n+1)都是已知數(shù)，就c’是未知數(shù)，所以可以求得c’==b’d’MOD p1*p2*……*pn*p(n+1)因此可以知道推論1 成立。
可以證明N 重RSA 算法的正確性,因為N 重RSA 算法是正確的所以三重的RSA 算法想當然是正確的。
4.2 RSA 改進算法的性能
RSA 算法使用方便，尤其是公開密鑰的特征使得用戶在數(shù)據(jù)傳輸之前無需交換密鑰，就算是和多個用戶進行秘密通信，也沒有必要記住所有的密鑰，N 個用戶通信，要有N 對密鑰，每個用戶只需記住自己的密鑰，并到公共存儲區(qū)去取得其他公鑰就可以了。但是由于RSA 算法的實現(xiàn)是以大素數(shù)來為基礎，依賴于計算機的速度和容量，效率比較低。根據(jù)統(tǒng)計，對相同數(shù)據(jù)塊的加密，對稱算法比RSA 算法的效率要高幾十倍。
改進的N 重RSA 算法中，由于所取得素數(shù)比較多，取多少個也是有應用N 重RSA 算法的用戶決定的，所以就可以把所取得素數(shù)的大小取得小一點，這樣就提高了計算機的運算速度，加快了RSA 算法的運算效率。由于N 重RSA 算法根本沒有違背RSA 算法，所以其安全性也是毋庸置疑的。
4.3 RSA 改進算法舉例
要對2 運用N=3 的N 重RSA 算法進行加密，取p1=5, p2=3,p3=7，求得n=p1*p2*p3=105，m=(p1-1)*(p2-1)*(p3-1)=(5-1)*(3-1)*(7-1)=48，然后生成較小的數(shù)e,使e 與48 互質(zhì),2 不對,5是最小的,于是e=5 最后生成d,使d*e MOD m=1 , d*5 MOD 48=1,d*3 除以48 余數(shù)為1，于是算出d=29 ， 所以求出公鑰e=5,n=105. 私鑰d=29,n=105. 密鑰計算完畢。加密:c=pe%n=25%105=8%105=8, 于是密文為8。把8 傳出去。同時應把公鑰也傳出去,好在收到時知道對應的是那個私鑰。解密過程:接收者收到密文和公鑰,找到對應的私鑰:p=cd%n=829%105,經(jīng)過運算，余數(shù)為2。
上面運用了N=3 時的N 重RSA 算法，在這種非對稱的RSA 加密算法中，充分利用了大數(shù)分解的思想，這樣在改進的N 重RSA 算法中加進了多個是相乘，由于這樣每次都有可能有不同多個數(shù)得出的結論來完成的加密密鑰和公鑰的計算，所以在更大程度上也保證的算法的安全性和保密性。
5. 小結
本文是在對傳統(tǒng)的RSA 算法的充分研究和深刻理解上，對RSA 算法效率低的問題進行=了改進得到了基于原有算法的N 重RSA 算法。在增加了素數(shù)的情況下降低了所選素數(shù)的個數(shù)，以達到小數(shù)相乘運算速度比大數(shù)相乘效率高的特點。由于N 重RSA 算法還是在原有的RSA 算法的基礎上，因此它的安全性和保密性都和原來的RSA 算法是一樣的，因此在應用上還是和原有的RSA 算法是相同的，所以N 重RSA 算法是否等同于大數(shù)分解依然不能得到理論上的證明。在N重RSA算法中,傳送保密信息的主要工作密鑰參數(shù)p1, p2……pn, ex, dx,都具有一次使用的特征,即每次通信使用到的這些工作密鑰參數(shù)都在隨機變化。在某種意義上,它接近于一次一密的密碼體制[6],顯然它的保密性要遠優(yōu)于工作密鑰在一個較長時間內(nèi)固定不變的原有的RSA 算法。并且減少了每一個隨機產(chǎn)生素數(shù)的位數(shù)，因此也在一定義以上加快了RSA 算法計算機實現(xiàn)的效率問題。但是由于在幾個小素數(shù)相乘后得到的還是一個較大的數(shù)，所以還是沒有從根本上解決RSA 算法基本只用于較少的數(shù)字加密，例如數(shù)字簽名上的問題。 |
|
|
