RSA算法的研究和改進(jìn)

陳春玲，齊年強(qiáng)，余 瀚

(南京郵電大學(xué) 計算機(jī)學(xué)院，江蘇 南京 210003)

RSA算法的研究和改進(jìn)

陳春玲，齊年強(qiáng)，余 瀚

(南京郵電大學(xué) 計算機(jī)學(xué)院，江蘇 南京 210003)

為了提高RSA算法的安全性，避免RSA密碼體制中的模n被因子分解，導(dǎo)致私鑰d泄露，采取消除密鑰中n的分布方法以及對三個因素因子的加密方法。采用消除密鑰中n的分布方法可以成功避免在公布的公鑰和保密的私鑰中出現(xiàn)n，防止攻擊者通過因子分解法分解出公鑰中n的因子，推導(dǎo)出解密密鑰d；采用三因子的加密算法，即使攻擊者知道了φ(n)，但對于分解n的三個素數(shù)沒有一個具體的公式，所以加大了分解的困難性，并且因?yàn)榇笏財?shù)適當(dāng)減小了位數(shù)，降低了計算量。實(shí)驗(yàn)結(jié)果表明，該方法提高了RSA算法的安全性，時間復(fù)雜度與傳統(tǒng)RSA算法相同。

RSA；安全性；公鑰；私鑰；時間

0 引 言

在RSA算法中兩個密鑰之間存在一種數(shù)學(xué)上的聯(lián)系?；谶@個事實(shí)，如果某個人發(fā)現(xiàn)了這種數(shù)學(xué)聯(lián)系并成功獲取了私鑰，這樣體制就會被破壞。算法中公鑰和私鑰都包含大數(shù)n，n可以被分解為因子p和q。眾所周知，公鑰是公開的，因此，如果某人猜到了n的因子那就很容易獲取私鑰。為了阻止該事件的發(fā)生，算法中嘗試消除私鑰和公鑰中n的分布，在n上運(yùn)用一種數(shù)學(xué)變換，通過使用X來替代n，使得攻擊者無法分解到n的因子。文中同時提出了三因子的RSA加密算法，指的是選取三個素數(shù)因子a1、a2、a3，它們的乘積為n，即n=a1×a2×a3。該算法可以降低大素數(shù)選擇所需要的時間，適當(dāng)?shù)販p少大素數(shù)的位數(shù)，降低計算量。

1 傳統(tǒng)RSA密碼算法的研究與分析

RSA算法[1]是1978年由三位數(shù)學(xué)家Rivest、Shamir和Adleman根據(jù)Whitfield與Martin Hellman的理論框架設(shè)計出的一種非對稱加密算法。RSA密碼體制的安全性取決于其加密算法的數(shù)學(xué)函數(shù)的求逆困難性，稱之為大數(shù)因子分解的困難性[2-4]。RSA包含了產(chǎn)生密鑰、加密信息和解密信息三個步驟：

步驟1：產(chǎn)生密鑰。

選取兩個大素數(shù)p和q，p≠q。計算乘積：

n=p×q

(1)

得到歐拉函數(shù)：

φ(n)=(p-1)×(q-1)

(2)

選擇隨機(jī)整數(shù)e，使得GCD(e,φ(n))=1且1

計算:

d=e-1Modφ(n)

(3)

其中，d為e的關(guān)于模φ(n)的乘法逆元,滿足ed=1Modφ(n)。

公鑰為(e,n)，私鑰為(d,n)。

步驟2：加密信息。

發(fā)送者通過式(4)來加密信息M。

C=MeMod(n)

(4)

其中，C是加密后產(chǎn)生的密文。

步驟3：解密信息。

接收者通過式(5)來解密密文C。

M=CdMod(n)

(5)

其中，M是加密前的信息。

傳統(tǒng)RSA算法密鑰生成過程時間主要是求取最大公約數(shù)的時間及計算公鑰和私鑰模乘法逆元的時間[5-6]。求取最大公約數(shù)采用歐幾里得算法，其時間復(fù)雜度為O(φ(n)/2)，模乘法逆元的計算方法采用窮舉法，時間復(fù)雜度為O(φ(n))，因此密鑰生成的時間復(fù)雜度為O(3φ(n)/2)。加密解密計算的時間主要是模冪運(yùn)算的時間，即形式為XnMod(m)的函數(shù)運(yùn)算時間，其采用遞歸法實(shí)現(xiàn)，時間復(fù)雜度為O(n)。所以傳統(tǒng)RSA算法密鑰生成的時間復(fù)雜度為O(φ(n)/2)，加密算法時間復(fù)雜度為O(e)，解密算法時間復(fù)雜度為O(d)。

在傳統(tǒng)的RSA公鑰密碼體制中一共出現(xiàn)了六個變量：p、q、n、φ(n)、e、d。但是在加密端只能知道n和e，在解密端可以知道p、q、n和d。其中可以將密文解密成明文的密鑰是d，即解密密鑰。如果d被泄露了，那么加密是無效的。

在加密端，在已知n和e的情況下如何推導(dǎo)出解密密鑰d。

由式(3)知，推導(dǎo)d需要知道公鑰e和φ(n)。

由式(2)知，只有知道p和q，才能算出φ(n)。

由式(1)知，要想知道p和q，必須對n進(jìn)行大整數(shù)的因子分解。

所以在RSA密碼體制中，如果模n被因子分解，那么其私鑰d也會被泄露出去[7-9]。雖然至今還未能在理論和事件中證明有分解大整數(shù)的有效辦法，但大數(shù)因子分解未被證明是NP問題，且隨著計算機(jī)計算能力的提高，原來被認(rèn)為不可能分解的某些大整數(shù)可能會被成功分解，這對RSA密碼體制的安全性構(gòu)成了潛在的威脅[10]。

為了確保RSA加密算法的安全性，只有不斷地增加密鑰長度。目前，一般要求密鑰長度在2 014bit位到2 048bit位之間，甚至更高。

2 RSA算法的改進(jìn)

改進(jìn)的RSA算法引進(jìn)了對三個素數(shù)因子的RSA加密算法[11-12]和兩個以上的步驟來消除密鑰中的n。引進(jìn)的三個素數(shù)因子雖然增加了素數(shù)因子的個數(shù)，但是減少了素數(shù)因子的位數(shù)，消除密鑰中的n可以使攻擊者無法通過因式分解n分解得到因子p和q。所以，一定程度上使得RSA算法更加安全。算法包括三個部分：產(chǎn)生內(nèi)部密鑰(n已經(jīng)被消除)、加密信息和解密信息。

步驟1：產(chǎn)生密鑰。

選擇大素數(shù)a1、a2、a3，a1≠a2≠a3。計算乘積：

n=a1×a2×a3

(6)

得到歐拉函數(shù)：

φ(n)=(a1-1)×(a2-1)×(a3-1)

(7)

根據(jù)a1、a2、a3的大小關(guān)系，計算X來替代n：

如果a1>a2>a3或者a1>a3>a2，解出X得：

GCD(X,n)=1,n-a1

(8)

如果a2>a1>a3或者a2>a3>a1，解出X得：

GCD(X,n)=1,n-a2

(9)

如果a3>a1>a2或者a3>a2>a1，解出X得：

GCD(X,n)=1,n-a3

(10)

將求得的X代入式(11)，求解出k2：

(11)

現(xiàn)在，公鑰是(k1,X)，私鑰是(k2,X)。

步驟2：加密信息。

發(fā)送者通過公鑰(k1,X)來加密信息M，公式為：

C=Mk1Mod(X)

(12)

其中，C是加密后產(chǎn)生的密文。

步驟3：解密信息。

接收者通過私鑰(k2,X)來解密密文C，公式為：

(13)

其中，M是加密前的信息。

根據(jù)上述步驟，可以設(shè)計出改進(jìn)RSA算法密鑰生成的流程，見圖1。

通過用X替換n成功消除了n。這讓算法變得相對安全，因?yàn)楣粽邿o法通過X分解到a1、a2和a3。

RSA算法的約束是，加密時所取的信息值必須小于大數(shù)的值，即小于n的值[13]。

圖1 改進(jìn)RSA密鑰生成算法流程圖

再者，能夠通過另外一層的加密擴(kuò)展該算法，但是這種大于一層的加密只能運(yùn)用于二因子的RSA算法，并不適用于三因子的RSA算法。這個可以在計算完X通過重復(fù)改進(jìn)算法中的式(8)～(10)并且得到k2來實(shí)現(xiàn)。

但是這一次需要采用獲取答案的四次方根。這個方法可以應(yīng)用更多次，只要取得的值滿足所有的約束。

改進(jìn)的RSA算法密鑰生成以及加解密算法所采用的方法是一樣的，但是步驟上有所不同。密鑰生成算法增加了根據(jù)a1、a2、a3的大小替換n的X的計算，時間復(fù)雜度為O(2φ(n))，加密算法的時間復(fù)雜度為O(k1)；解密算法在模冪運(yùn)算結(jié)果的基礎(chǔ)上增加了平方根運(yùn)算，因?yàn)槠椒礁\(yùn)算的時間復(fù)雜度為常數(shù)階，因此解密算法的時間復(fù)雜度為O(k2)。

3 實(shí)驗(yàn)結(jié)果與分析

以計算φ(n)的攻擊方法為例，如果在傳統(tǒng)的RSA加密算法中，攻擊者可以計算出來φ(n)，就能夠分解出n的素數(shù)因子。這是由于φ(n)=(p-1)(q-1)=pq-(p+q)+1=n-(p+q)+1→p+q=n+1-φ(n)且pq=n，那么可以構(gòu)造一元二次方程x2-(n+1-φ(n))x+n=0，方程的根就是p和q[14-15]。

例如：如果n=221，φ(n)=192，那么，一元二次方程x2-30x+221=0的兩個根為x1=13，x2=17。因此，n=13×17=221。

改進(jìn)的RSA算法中，在已知公鑰的前提下，無法知道公鑰中的n，因此無法通過方程分解出n的因子；再者，采用三個素數(shù)因子的RSA算法，就算攻擊者知道了φ(n)，但是對于分解n的三個素數(shù)因子沒有一個具體的公式去求解，所以分解的困難度會大大增加，提高了算法的安全性。

表1和表2分別為RSA算法和改進(jìn)RSA算法在時間上的差異。以滴答(1ms等于10 000滴答)為單位，并只用單層加密，即使用X作為系數(shù)。因?yàn)榇怂惴▽Ｗ⒂赗SA算法的安全方面，密鑰的生成以及加解密方面增加了計算量，所以時間會有一些增加。

表1 RSA算法的時間

表2 改進(jìn)RSA算法的時間

圖2是RSA算法和改進(jìn)RSA算法之間產(chǎn)生密鑰的時間對比，以滴答為單位。

密鑰的產(chǎn)生過程在時間上有很多的變化，因?yàn)槎嘤嗟囊恍┘用懿襟E或消除n的分布消耗了時間。

圖3為RSA算法和改進(jìn)RSA算法之間加密和解密的時間對比，以滴答為單位。

圖2RSA算法和改進(jìn)RSA算法之間

圖3RSA算法和改進(jìn)RSA算法之間

信息的加密和解密存在時間上的差異，因?yàn)榻饷芩惴òl(fā)生了改變。后者更加復(fù)雜并會消耗更多時間。

圖4為RSA算法和改進(jìn)RSA算法之間的總體時間對比，以滴答為單位。

圖4 RSA算法和改進(jìn)RSA算法之間的總時間對比

根據(jù)上述對傳統(tǒng)的RSA算法和改進(jìn)算法的時間復(fù)雜度的分析，兩種算法的時間復(fù)雜度級別相同，又因?yàn)樵黾拥臅r間并不影響密鑰生成以及加解密的過程，消耗的時間并不是很高，因此可以忍受。

4 結(jié)束語

由于改進(jìn)RSA算法克服了傳統(tǒng)RSA算法因素數(shù)選擇問題位數(shù)要求越來越多使得素數(shù)產(chǎn)生效率下降、n被因子分解密碼體制安全性下降等缺點(diǎn)[16]，所以，改進(jìn)RSA算法具有獨(dú)特的優(yōu)勢，實(shí)現(xiàn)了對信息的安全加密。由于在最初的RSA算法中加入三個素數(shù)因子并且消除n，用來替代n最新生成的數(shù)不僅可以在公鑰和私鑰中使用，而且還能成功避免受到因子分解的攻擊，使得RSA算法更加安全，但是在時間上會有一些增加，因此還需要對密鑰生成、信息的加解密速度和時間進(jìn)行深入研究。

[1]DiffieW,HellmanME.Newdirectionsincryptography[J].IEEETransactionsonInformationTheory,1976,22(6):644-654.

[2] 胡 云.RSA算法研究與實(shí)現(xiàn)[D].北京:北京郵電大學(xué),2010.

[3]AboudSJ.AnefficientmethodforattackRSAscheme[C]//Procofsecondinternationalconferenceonapplicationsofdigitalinformationandwebtechnologies.[s.l.]:IEEE,2009:587-591.

[4]MehrotraV.AneffectivemethodforattackRSAstrategy[J].InternationalJournalonAdvancedNetworkingandApplications,2012,3(5):1362-1366.

[5]RSALaboratory.RSAalgorithmtimecomplexity[EB/OL].2009.http://www.rsa.com/rsalabs/node.aspid=2215.

[6] 靳麗君.非對稱加密體制中RSA算法的研究[J].電子設(shè)計工程,2011,19(11):29-30.

[7] 李 青,李雄偉,金 濤.RSA算法的研究與簡單實(shí)現(xiàn)[J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用,2007(6):88-91.

[8]JonssonJ,KaliskiB.Thepublic-keycryptographystandards[J].RSADataSecurity,1993,8(5):33-35.

[9]AmbedkarBR,GuptaA,GautamP,etal.AnefficientmethodtofactorizetheRSApublickeyencryption[C]//Procofinternationalconferenceoncommunicationsystemsandnetworktechnologies.[s.l.]:[s.n.],2011.

[10] 鄢喜愛,楊金民,田 華.RSA公鑰密碼算法的分析[J].長春工業(yè)大學(xué)學(xué)報:自然科學(xué)版,2006,27(2):142-144.

[11] 安吉旺,徐凱宏.基于RSA和密鑰的二維碼加密編碼的研究[J].森林工程，2014，30(2):125-129.

[12] 謝仁康.非對稱加密二維碼防偽系統(tǒng)的設(shè)計[D].成都:電子科技大學(xué),2013.

[13]MilanovE.TheRSAalgorithm,UniversityofWashington:DepartmentofMathematics[EB/OL].2013-10-08.http://www.math.washington.edu/～morrow/336_09/papers/Yevgeny.pdf.

[14]DhakarRS,GuptaAK,SharmaP.ModifiedRSAEncryptionAlgorithm(MREA)[C]//ProcofACCT.[s.l.]:[s.n.],2012.

[15]SarkarS,MaitraS.CryptanalysisofRSAwithtwodecryptionexponents[J].InformationProcessingLetters,2010,110(5):178-181.

[16] 劉項(xiàng)洋.基于RSA的隨機(jī)密鑰交換系統(tǒng)的研究與設(shè)計[D].合肥:合肥工業(yè)大學(xué),2004.

Research and Improvement of RSA Algorithm

CHEN Chun-ling,QI Nian-qiang,YU Han

(College of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

In order to improve the security of the RSA algorithm and avoid the mathematical factorization of the moduleninRSAcrytosystemwhichleadstoprivatekeydleaking,themethodofeliminatingthedistributionofnandthree-factorencryptionalgorithmareadopted.Theresultsshowthattheformercansuccessfullyavoidtheappearanceofninpublickeyandprivatekey,preventingtheattacterfromusingthemethodofmathematicalfactorizationtogetthenfactorsanddeducingthedecryptionkeyd.Adoptingthelatter,eveniftheattackerknowstheφ(n),butitdoesn’thaveaspecificformulatobreakdownthethreeprimenumberfordecompositionofn.Sothedifficultyoffactoringincreasesandthecomputationisreducedduetothereductionoflargeprimenumbers’sbits.TheexperimentalresultsindicatethatthemethodincreasesthesecurityoftheRSAalgorithmanditstimecomplexityissametothetraditionalalgorithm.

RSA;security;public key;private key;time

2015-11-23

2016-03-04

時間：2016-08-01

國家自然科學(xué)基金資助項(xiàng)目(11501302)

陳春玲(1961-)，男，教授，碩士，研究生導(dǎo)師，研究方向?yàn)檐浖こ?、分布式組件技術(shù)、網(wǎng)絡(luò)信息安全及其應(yīng)用；齊年強(qiáng)(1991-)，男，碩士研究生，研究方向?yàn)榫W(wǎng)絡(luò)安全。

http://www.cnki.net/kcms/detail/61.1450.TP.20160801.0904.026.html

TP

A

1673-629X(2016)08-0048-04

10.3969/j.issn.1673-629X.2016.08.010