RSA算法的研究和改進

陳春玲，齊年強，余 瀚

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

RSA算法的研究和改進

陳春玲，齊年強，余 瀚

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

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

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

0 引 言

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

1 傳統RSA密碼算法的研究與分析

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

步驟1：產生密鑰。

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

n=p×q

(1)

得到歐拉函數：

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

(2)

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

計算:

d=e-1Modφ(n)

(3)

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

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

步驟2：加密信息。

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

C=MeMod(n)

(4)

其中，C是加密后產生的密文。

步驟3：解密信息。

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

M=CdMod(n)

(5)

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

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

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

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

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

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

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

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

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

2 RSA算法的改進

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

步驟1：產生密鑰。

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

n=a1×a2×a3

(6)

得到歐拉函數：

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

(7)

根據a1、a2、a3的大小關系，計算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)

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

步驟2：加密信息。

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

C=Mk1Mod(X)

(12)

其中，C是加密后產生的密文。

步驟3：解密信息。

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

(13)

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

根據上述步驟，可以設計出改進RSA算法密鑰生成的流程，見圖1。

通過用X替換n成功消除了n。這讓算法變得相對安全，因為攻擊者無法通過X分解到a1、a2和a3。

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

圖1 改進RSA密鑰生成算法流程圖

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

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

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

3 實驗結果與分析

以計算φ(n)的攻擊方法為例，如果在傳統的RSA加密算法中，攻擊者可以計算出來φ(n)，就能夠分解出n的素數因子。這是由于φ(n)=(p-1)(q-1)=pq-(p+q)+1=n-(p+q)+1→p+q=n+1-φ(n)且pq=n，那么可以構造一元二次方程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。

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

表1和表2分別為RSA算法和改進RSA算法在時間上的差異。以滴答(1ms等于10 000滴答)為單位，并只用單層加密，即使用X作為系數。因為此算法專注于RSA算法的安全方面，密鑰的生成以及加解密方面增加了計算量，所以時間會有一些增加。

表1 RSA算法的時間

表2 改進RSA算法的時間

圖2是RSA算法和改進RSA算法之間產生密鑰的時間對比，以滴答為單位。

密鑰的產生過程在時間上有很多的變化，因為多余的一些加密步驟或消除n的分布消耗了時間。

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

圖2RSA算法和改進RSA算法之間

圖3RSA算法和改進RSA算法之間

信息的加密和解密存在時間上的差異，因為解密算法發生了改變。后者更加復雜并會消耗更多時間。

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

圖4 RSA算法和改進RSA算法之間的總時間對比

根據上述對傳統的RSA算法和改進算法的時間復雜度的分析，兩種算法的時間復雜度級別相同，又因為增加的時間并不影響密鑰生成以及加解密的過程，消耗的時間并不是很高，因此可以忍受。

4 結束語

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

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

[2] 胡 云.RSA算法研究與實現[D].北京:北京郵電大學,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].電子設計工程,2011,19(11):29-30.

[7] 李 青,李雄偉,金 濤.RSA算法的研究與簡單實現[J].網絡安全技術與應用,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].長春工業大學學報:自然科學版,2006,27(2):142-144.

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

[12] 謝仁康.非對稱加密二維碼防偽系統的設計[D].成都:電子科技大學,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] 劉項洋.基于RSA的隨機密鑰交換系統的研究與設計[D].合肥:合肥工業大學,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

國家自然科學基金資助項目(11501302)

陳春玲(1961-)，男，教授，碩士，研究生導師，研究方向為軟件工程、分布式組件技術、網絡信息安全及其應用；齊年強(1991-)，男，碩士研究生，研究方向為網絡安全。

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