基于數(shù)論的RSA算法研究

《基于數(shù)論的RSA算法研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、基于數(shù)論的RSA算法研究【摘要】基于數(shù)論的公鑰密碼體制的RSA算法是最完善的加密算法.通過RSA算法基本原理可以將大數(shù)的幕模運(yùn)算轉(zhuǎn)換為小數(shù)幕模運(yùn)算，并對(duì)一些模塊進(jìn)行適當(dāng)?shù)母倪M(jìn)，從而提出快速求解加密和解密的計(jì)算方法，提高RSA的運(yùn)算速度?！娟P(guān)鍵詞】公鑰密碼算法RSA算法幕模運(yùn)算【基金項(xiàng)目】河南省教育廳科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目資助計(jì)劃(14A110016)o【中圖分類號(hào)】029【文獻(xiàn)標(biāo)識(shí)碼】A【文章編號(hào)】2095-3089(2014)05-0137-021.前言RSA公鑰密碼算法是美國(guó)麻省理工學(xué)院的三位學(xué)者Rivest.Shamir和Adieman在1978年提出的［1］,既可以用于加密，又可

2、用于數(shù)字簽名，它安全，易懂，易實(shí)現(xiàn)，是目前廣泛應(yīng)用的一種密碼算法。其理論基礎(chǔ)是數(shù)論中的大合數(shù)因子分解困難性，即求兩個(gè)人素?cái)?shù)之積，在計(jì)算機(jī)上很容易實(shí)現(xiàn)。但是要將一個(gè)大合數(shù)分解成兩個(gè)素?cái)?shù)的乘積，在計(jì)算機(jī)上很難實(shí)現(xiàn)。由于RSA算法采用的幕模運(yùn)算耗時(shí)太多，大量的數(shù)據(jù)處理時(shí)速度很慢，所以提高RSA的運(yùn)算效率便成為非常重要的研究?jī)?nèi)容［4］。2?基本定義與定理定義1：若a,b,c都是整數(shù)，且a

3、b,a

4、c,那么a就是b和c的公因數(shù)。在所有公因數(shù)中最大一個(gè)，稱為最大公因數(shù)，并記為gcd(b,c)[3]o定義2：若a和b的最大公因數(shù)是1,即gcd(b,c)=l,則稱a和b互素⑵。定義3：設(shè)a,beZ,n

5、HO如果n

6、(a-b),則稱a和b模n同余，記為a三b(modn),整數(shù)n稱為模數(shù)[3]。定義4：元素xeZn有乘法逆元xT,當(dāng)?shù)珒H當(dāng)x和n的最大公因子是1,即gcd(x,n=l),即x和n互質(zhì)。如果x的逆元存在，必定滿足xXx-lmodn二1[3]。定理1：若a?和n互素，則a(n)=lmodn,稱為歐拉定理(簡(jiǎn)稱Euler定理)。證明：設(shè)Zn={al,a2,...a*(n)}是模n的一個(gè)群集，由于gcd(a,n)=l,根據(jù)同余性質(zhì)ab=albl(modn),故aZn={aal,aa2,...aa4)(n)}也是模n的一個(gè)群集，即?al=H(aal)(modn)。因此a<1)(

7、n)=lmodn0定理2：若是p素?cái)?shù)，a是正整數(shù)且gcd(a,p)=l則ap-1三lmodp,稱為費(fèi)爾瑪定理。(簡(jiǎn)稱Fermat定理)[1]。定理3：設(shè)n是一正整數(shù)，小于n但與n互質(zhì)的正整數(shù)的個(gè)數(shù)稱為n的歐拉函數(shù)，記為4)(n),若n是素?cái)?shù)，則顯然有<1)(n)=n-l[1]o推論1：若n是兩個(gè)素?cái)?shù)p和q的乘積，則<1>(n)=4)(p)Xe(q)=(p-l)X(q-1)推論2：對(duì)任意非負(fù)整數(shù)a和正整數(shù)b有g(shù)cd(a,b)=gcd(b,amodb)。證明：因?yàn)閎是正整數(shù)，所以可將a表示為a=kb+r=rmodb,amodb=r,其中為k一整數(shù)，所以amodb=a-kb,設(shè)d是a,b的公

8、因子，即d

9、o,d

10、b,所以d

11、kb,由d

12、a和d

13、kb得d

14、(amodb),因此a是b和amodb的公因子。所以得出a,b的公因子集合與b,amodb的公因子集合相等，兩個(gè)集合的最大值也相等。3.RSA公鑰算法描述3.1密鑰選擇RSA加密算法的密鑰選擇方法是該算法的核心，RSA密鑰的選擇和牛成方法保證了RSA公鑰加密算法的安全性。先選擇兩個(gè)素?cái)?shù)p和q。這兩個(gè)素?cái)?shù)的乘積就是RSA密鑰中的正整數(shù)n,即n二pXq,如果p和q足夠大,那么乘積n也就足夠大，如再分解p和q困難性極大，這樣就可以滿足了公鑰密碼系統(tǒng)的耍求，根據(jù)歐拉函數(shù)計(jì)算出*(n)=(p-l)(q-l)o然后，隨機(jī)選収整數(shù)0,滿足

15、1

16、式兩邊同乘以e將等式轉(zhuǎn)化為dXe二lmod?(n)。根據(jù)模運(yùn)算性質(zhì)可知dXe=k4)(n)+l,其中k是一個(gè)大于等于的整數(shù)。根據(jù)加密公式和模運(yùn)算性質(zhì)可知cdmodn=(me)dmodn^mk4)(n)+lmodn,利用指數(shù)運(yùn)算性質(zhì)mXmk(n)modn=mXlmodn二m。3.4計(jì)算問題通過分析RSA算法的求解過程，可知RSA通過乘法與除法加以實(shí)現(xiàn)的?？上攵?，RSA算法將執(zhí)行大量的乘除法運(yùn)算，從而導(dǎo)致RSA算法的加密與解密速度十分慢［6］。因