RSA加密算法的密鑰長(zhǎng)度和執(zhí)行效率之間的矛盾是RSA加密算法進(jìn)一步發(fā)展的瓶頸，為了解決這一瓶頸問題，有專家提出了一種用四個(gè)短密鑰，將密文分為四個(gè)模塊，并運(yùn)用中國剩余定理將高位寬大數(shù)的模冪運(yùn)算轉(zhuǎn)化為對(duì)低位寬相對(duì)較小的數(shù)進(jìn)行模冪運(yùn)算來快速實(shí)現(xiàn)解密的方法，來平衡加密和解密的計(jì)算成本，這就是我們今天要介紹的四素?cái)?shù)RSA加密算法。

一、RSA加密算法工作原理

1、RSA加密算法密鑰的產(chǎn)生

RSA加密算法是一種比較典型的加密算法，它的安全性依賴于大數(shù)分解和素性檢測(cè)理論的基礎(chǔ)。兩個(gè)大數(shù)的乘積容易算出，但要是將這個(gè)乘積分解兩個(gè)大數(shù)因數(shù)的計(jì)算量是非常大的，根據(jù)人們的經(jīng)驗(yàn)，在實(shí)際計(jì)算當(dāng)中是不能實(shí)現(xiàn)的，因此可以確定算法的安全性。以下就是密鑰產(chǎn)生步驟：

（1）隨機(jī)選取兩個(gè)大的不同的質(zhì)數(shù)p和q (保密，建議取100位以上十進(jìn)制數(shù))，計(jì)算N =p*q(公開)和φ（n）=（p-1）（q-1）(不公開)

（2）隨即選取加密密鑰e(公開)，且滿足0<e<x，gcd（e,φ（n）)=1。

（3）求出密鑰d，滿足de≡1(mod(φ（n）)(不公開)。這樣就產(chǎn)生了公鑰(e,n)和私鑰(d,n)。

2、RSA加密算法的加密和解密

RSA加密算法中，加密和解密使用不同的密鑰，即使加密密鑰是公開的，但仍是推導(dǎo)不出解密密鑰,，他們的過程是不可逆的。利用RSA加密第一步需將明文數(shù)字化，并取長(zhǎng)度小于log2n位的數(shù)字做明文塊。

加密算法：c=(E)m=m^e_(modn)

解密算法： m=(D)c=c^d_(modn)

在密鑰管理方面，由于一對(duì)密鑰中的一個(gè)密鑰是對(duì)外公開的，甚至可在網(wǎng)絡(luò)服務(wù)器中注冊(cè)，這樣對(duì)密鑰的管理非常容易方便。RSA是研究的最廣泛的公鑰加密算法，提出近三十年的時(shí)間，經(jīng)歷了各種攻擊，逐漸被各界接受。同時(shí)它也存在一定的缺點(diǎn)，比如運(yùn)行速度慢，產(chǎn)生密鑰比較麻煩等等。

二、四素?cái)?shù)RSA加密算法的基本原理

在傳統(tǒng)的RSA加密算法基礎(chǔ)上，四個(gè)素?cái)?shù)的RSA加密與解密算法依然成立。

四素?cái)?shù)RSA算法實(shí)現(xiàn)步驟

（1）隨機(jī)選取四個(gè)不同的大素?cái)?shù)p,q,r,s(不公開)，計(jì)算n=p*q*r*s(公開)及φ（n）=（p-1）（q-1）(不公開)。

（2）隨即選取加密密鑰e (公開)，且滿足0 <e <x，gcd（e,φ（n）)=1。

（3）求出密鑰d，滿足de≡1(mod(φ（n）)(不公開)。

（4）加密和解密過程和傳統(tǒng)的雙素?cái)?shù)RSA加密算法完全一樣，仍為：

加密算法：c=(E)m=m^e_(modn)

解密算法： m=(D)c=c^d_(modn)

三、四素?cái)?shù)RSA加密算法解密過程中中國剩余定理的應(yīng)用

應(yīng)用中國剩余定理，四素?cái)?shù)的RSA加密算法中的模冪運(yùn)算可以轉(zhuǎn)化為以下運(yùn)算過程：

1、計(jì)算：Cp=comdp,Cq=comdq,Cr=comdr,Cs=coms

2、算出：Dp=dmod(p-1),Dq=dmod(q-1),Dr=dmod(r-1),Ds=dmod(s-1)

得出：M1=Cp(modp），M2=Cq(modq），M3=Cr(modr），M4=Cs(mods）

3、計(jì)算：M=(M1(qrs)p-1modn+M2(prs)q-1modn+M3(pqs)r-1modn+M4(pqr)s-1modn）modn，即得出明文：M。

四、四素?cái)?shù)RSA加密算法的試驗(yàn)仿真

運(yùn)用四素?cái)?shù)RSA加密算法進(jìn)行解密是要進(jìn)行四次指數(shù)長(zhǎng)度為n/4bits位的指數(shù)模運(yùn)算c^d_(modn)，傳統(tǒng)的RSA加密算法計(jì)算時(shí)所用的時(shí)間復(fù)雜度為0(logd _log2n)，當(dāng)d很大與n同數(shù)量級(jí)時(shí)，復(fù)雜度可以認(rèn)為是0(log3n)，這樣效率提高是顯而易見的。

理論上，效率提高的倍數(shù)為:,當(dāng)k=4，n=2048bits時(shí)，α可以提高到4.02倍。

下面以n=2048bit為例子，隨機(jī)選取p,q,r,s大整數(shù)，運(yùn)用中國剩余定理，得到的一組試驗(yàn)數(shù)據(jù)。

從上面數(shù)據(jù)上可以看出，四素?cái)?shù)RSA算法的解密速度是傳統(tǒng)RSA的2.69倍，是三素?cái)?shù)RSA的1.90倍，可以得出四素?cái)?shù)RSA算法可以提高解密的效率。由于包含其他的運(yùn)算和外界的一些客觀條件，試驗(yàn)得出的數(shù)據(jù)會(huì)比理論數(shù)據(jù)低些。

四素?cái)?shù)RSA加密算法即可以保證整數(shù)足夠大，有可以保證體制的安全性。今后還要對(duì)n到底為多大時(shí)才不會(huì)導(dǎo)致效率和安全性下降做進(jìn)一步的深入地研究。

admin

收藏 海報(bào)分享