RSA加密算法的研究

李瑩 趙瑞 曹宇 張?zhí)煊? 劉霏凝

摘要：隨著互聯(lián)網(wǎng)和通信技術(shù)的發(fā)展，信息安全問題日益受到重視，基于數(shù)據(jù)加密的信息安全技術(shù)得到了迅速的發(fā)展。數(shù)據(jù)加密就算法而言，分為對(duì)稱加密和非對(duì)稱加密兩類。RSA是應(yīng)用最廣泛的非對(duì)稱算法之一，具有安全性高、易于實(shí)現(xiàn)等特點(diǎn)，但運(yùn)算速度很慢，只能用于一些少量數(shù)據(jù)。針對(duì)RSA運(yùn)算效率慢的問題，提出了中國剩余定理和蒙哥馬利模乘法相結(jié)合的方法來優(yōu)化模冪，用三素?cái)?shù)代替?zhèn)鹘y(tǒng)的二重素?cái)?shù)。實(shí)驗(yàn)結(jié)果表明，優(yōu)化算法具有較高的速度和可行性。

關(guān)鍵詞： RSA; 中國剩余定理; 蒙哥馬利模乘法

【Abstract】 With the development of Internet and communication technology， more and more attention has been paid to information security.In terms of algorithm， data encryption can be divided into symmetric encryption and asymmetric encryption.RSA is one of the most widely used asymmetric algorithms， and has the characteristics of high security， being easy to implement， but the operation speed is very slow， which can only be used for some small amount of data encryption.In order to solve the problem of slow arithmetic efficiency of RSA， a method combining Chinese residual theorem and Montgomery modular multiplication is proposed to optimize modular power and replace traditional double prime number with triple prime number. Experimental results show that the optimization algorithm has high speed and feasibility.

【Key words】 ?RSA;Chinese remainder theorem; Montgomery model multiplication

0 引 言

隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展，互聯(lián)網(wǎng)上共享的數(shù)據(jù)量有了顯著增長。處理大數(shù)據(jù)的需求也日漸增多，在安全性上就面臨諸多挑戰(zhàn)。在當(dāng)今信息時(shí)代，互聯(lián)網(wǎng)上的數(shù)據(jù)容易遭遇各種攻擊，每個(gè)人都希望能夠保護(hù)好自己的隱私。因此，維護(hù)用戶類數(shù)據(jù)的安全性即已成為目前的研究熱點(diǎn)。具體來說，該項(xiàng)研究主要包括新加密算法研發(fā)和安全系統(tǒng)設(shè)計(jì)。其中，加密算法通常分為2類，分別是對(duì)稱加密和非對(duì)稱加密。當(dāng)下研究指出，RSA算法是數(shù)據(jù)加密應(yīng)用最廣泛的一種非對(duì)稱加密算法，具有安全性高、易于實(shí)現(xiàn)等特點(diǎn)，不僅可對(duì)數(shù)據(jù)進(jìn)行加密，而且可以對(duì)數(shù)據(jù)進(jìn)行身份驗(yàn)證。在RSA算法中，公鑰的加密是已知的，而私鑰的解密是私密的，因此復(fù)雜性機(jī)制的加密和解密在整體上是由密鑰中需要分解[1]的質(zhì)數(shù)的數(shù)量決定。而要實(shí)現(xiàn)安全的數(shù)據(jù)傳輸，就要對(duì)質(zhì)數(shù)進(jìn)行因數(shù)分解。此時(shí)將需要較長的計(jì)算時(shí)間和強(qiáng)大的計(jì)算能力，所以對(duì)于質(zhì)數(shù)的解密是必不可少的。相比之下，只對(duì)2個(gè)質(zhì)數(shù)進(jìn)行因數(shù)分解，2個(gè)質(zhì)數(shù)通常很容易被打破[2]。因此，提出了使用3個(gè)質(zhì)數(shù)來減少處理時(shí)間并提高安全性[3]。在本次研究中，主要在對(duì)非對(duì)稱加密算法中的RSA算法原理進(jìn)行分析的基礎(chǔ)上，針對(duì)RSA算法的優(yōu)缺點(diǎn)以及存在的問題，采用中國剩余定理和蒙哥馬利模乘法進(jìn)行優(yōu)化，提出RSA的改進(jìn)算法，并在Java平臺(tái)上實(shí)現(xiàn)。

1 密碼學(xué)

計(jì)算機(jī)安全在信息安全中起著重要的作用。密碼學(xué)是計(jì)算機(jī)系統(tǒng)中保護(hù)數(shù)字?jǐn)?shù)據(jù)的第一種方法，廣泛應(yīng)用于數(shù)字電視廣播、數(shù)字貨幣、手機(jī)等日常生活的各個(gè)方面，以維護(hù)消息的機(jī)密性和防止信息篡改及竊聽?？偠灾?，密碼學(xué)的歷史就是密碼分析的歷史。由于新的密碼分析方法的發(fā)布，或者計(jì)算機(jī)和網(wǎng)絡(luò)的突破性進(jìn)展，即使是那些被認(rèn)為絕對(duì)安全的密碼，最終也會(huì)暴露在風(fēng)險(xiǎn)之中（受到危害），而這反過來又推動(dòng)了加密技術(shù)的新發(fā)展。在當(dāng)下研究中，RSA非對(duì)稱加密算法即是密碼學(xué)常用的加密算法。

2 RSA算法

2.1 算法原理

RSA算法是由Rivest、Shamir和Adleman開發(fā)的一種非對(duì)稱加密算法，在此算法中公鑰和私鑰將會(huì)配合使用。迄今為止，RSA算法已然成為使用最廣泛的公鑰算法，究其原因即在于其易于實(shí)現(xiàn)及良好的安全性。使用RSA算法來開發(fā)密鑰，每條消息都被映射成整數(shù)，通常被定義為分組密碼，當(dāng)用戶解密數(shù)據(jù)時(shí)，密鑰則用于驗(yàn)證，該過程增強(qiáng)了存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)完整性，為用戶提供更好的安全性。在研究工作中，用戶數(shù)據(jù)在存儲(chǔ)到服務(wù)端之前將使用RSA算法進(jìn)行加密，繼而使用RSA算法生成私鑰，只有擁有數(shù)據(jù)的用戶才知道該算法。RSA算法中涉及的步驟分為密鑰生成、加密和解密。對(duì)此擬做闡釋分述如下。

2.1.1 密鑰生成

在數(shù)據(jù)加密之前完成，密鑰生成過程如下：

步驟1 為保證數(shù)據(jù)的完整性，將通過考慮2個(gè)不同的隨機(jī)素?cái)?shù)（如具有相似位長的g和h）來選擇輸入。

步驟2 計(jì)算i = g * h。

步驟3 計(jì)算歐拉函數(shù)：（i） = （g-1）*（h-1）。

步驟4 選擇一個(gè)整數(shù)a，1 < a <（i）和最大公約數(shù)， （i）是1。現(xiàn)在，將其作為公鑰指數(shù)發(fā)布。

步驟5 確定如下：d = a-1（mod（i））即d是a mod（i）乘法逆元。

步驟6 d作為私鑰組件，d * a = 1 mod（i）。

步驟7 公鑰由模i和公鑰指數(shù)（a， i）組成。

步驟8 私有密匙由模i和私有指數(shù)d組成，而私有指數(shù)將被（i， d）保密。

2.1.2 加密

將原始數(shù)據(jù)轉(zhuǎn)換為密碼數(shù)據(jù)的過程被定義為加密。建議的加密程序如下：

步驟1 公鑰（a，i）傳輸給用戶。

步驟2 可逆協(xié)議用于將用戶數(shù)據(jù)映射到稱為填充方案的整數(shù)。

步驟3 對(duì)所需的數(shù)據(jù)進(jìn)行加密，得到的密碼數(shù)據(jù)C由C=me（mod i）給出。

2.1.3 解密

將密碼數(shù)據(jù)轉(zhuǎn)換為原始數(shù)據(jù)的過程被定義為解密。建議的解密程序如下：

步驟1 向用戶提出請(qǐng)求。

步驟2 使用生成的私鑰和加密的數(shù)據(jù)來驗(yàn)證用戶的真實(shí)性。

步驟3 用戶將數(shù)據(jù)解密為m = Cd （mod i）。

步驟4 通過改變填充方案，為用戶計(jì)算m提供了原始數(shù)據(jù)。

2.2 RSA算法的改進(jìn)及應(yīng)用

RSA[4]系統(tǒng)是在眾多領(lǐng)域得到應(yīng)用和普及的公鑰密碼系統(tǒng)之一。RSA運(yùn)算本質(zhì)上是一個(gè)模指數(shù)運(yùn)算。RSA算法中大數(shù)因子分解的模指數(shù)運(yùn)算是一項(xiàng)耗時(shí)的工作，始終制約著RSA算法的發(fā)展。該算法的安全級(jí)別依賴于在短時(shí)間內(nèi)因式分解一個(gè)大整數(shù)。針對(duì)這一問題，許多學(xué)者提出了不同的優(yōu)化算法，其中，中國剩余定理（CRT）對(duì)解密的有效性是顯而易見的。證明了考慮中國剩余定理的計(jì)算代價(jià)，對(duì)偶素?cái)?shù)CRT-RSA的運(yùn)算速度分別是原算法的3.32倍（1 024位模）和3.47倍（模型為2 048位）[5]的運(yùn)算速度。雖然速度令人滿意，但存在安全問題。因此，將原有的雙素?cái)?shù)RSA算法改為三素?cái)?shù)，然后進(jìn)行加密操作[6-7]，這里將展開如下研究論述。

2.2.1 三素?cái)?shù)RSA算法基本原理

在傳統(tǒng)雙素?cái)?shù)RSA密碼算法[8]的基礎(chǔ)上，取3個(gè)素?cái)?shù)，仍建立算法，描述如下：

（1）隨機(jī)選取3個(gè)不同的大素?cái)?shù)p、q、r，計(jì)算n=pqr，（n）=（p-1）（q-1）（r-1）。

（2）選取滿足一定條件的加密密鑰e，計(jì)算滿足de≡1 mod （n）的私鑰d。

（3）加密和解密過程與傳統(tǒng)算法相同。具體來說，加密算法為：c=E（m）=me mod n，解密算法為：m=D（c）=cd mod n。

2.2.2 利用蒙哥馬利模乘法和中國剩余定理進(jìn)行優(yōu)化

由表2可知，利用中國剩余定理進(jìn)行雙素?cái)?shù)RSA優(yōu)化的效率是傳統(tǒng)算法的3.36倍，接近理論值3.47。使用中國剩余定理和蒙哥馬利模乘法的三素?cái)?shù)RSA算法的效率是傳統(tǒng)算法的5.4倍，是雙素?cái)?shù)RSA算法的1.6倍。結(jié)果表明，改進(jìn)后的RSA算法可以大大提高速度。

4 結(jié)束語

本文主要研究了常用非對(duì)稱加密算法RSA。研究中，探討分析了其研究現(xiàn)狀，改進(jìn)了算法的不足之處，通過比較2個(gè)素?cái)?shù)和3個(gè)素?cái)?shù)之間的運(yùn)行效率，可以看出安全性能的提高，證明了改進(jìn)算法的優(yōu)勢(shì)。

參考文獻(xiàn)

[1] ?Shiota S， Furuta S， Hirokawa M， et al. Cryptographic communication system and cryptographic communication method： US，9608818[P]. 2017-03-28.

[2]ISWARI N M S . Key generation algorithm design combination of RSA and ElGamal algorithm[C]//2016 8th International Conference on Information Technology & Electrical Engineering. Yogyakarta， Indonesia：IEEE， 2017：1.

[3]PATIDAR R ， BHARTIYA R . Modified RSA cryptosystem based on offline storage and prime number[C]// 2013 IEEE International Conference on Computational Intelligence and Computing Research （ICCIC）. Enathi， India：IEEE， 2013：1.

[4]RIVEST R L ， SHAMIR A ， ADLEMAN L . A method for obtaining digital signatures and public key cryptosystems[J]. Communication of Association for Computing Machinery， 1978， 21（2）：120.

[5]BONEH D ， DURFEE G . Cryptanalysis of RSA with private key d less than N 0.292[M]// STERN J. Advances in cryptology — EUROCRYPT'99. Lecture Notes in Computer Science. Berlin/Heidelberg：Springer，1999，1592：1.

[6]LIU Ping ， ZHAO Huanping. Analysis and research on improved RSA algorithm[J]. Computer and Modernization， 2013（7）：84.

[7]YAN S Y. Computational number theory and modern cryptography[M]. USA：Wiley，2012.

[8]FEI Xiaofei， HU Hanying. Security of CRT based RSA algorithm[J]. Microcomputer Information， 2009，25（1-3）：54.

[9]SHAND M ， VUILLEMIN J . Fast implementations of RSA cryptography[C]//The 11th IEEE Symposium on Computer Arithmetic. Windsor：IEEE，1993：252.

[10]SKORMIN V A ， DELGADO-FRIAS J G， MCGEE D L ， et al. BASIS： A biological approach to system information security[C]// 2001 Proceedings of Information Assurance in Computer Networks： Methods， Models and Architectures for Network Security International Workshop MMM-ACNS 2001. St. Petersburg， Russia： Springer-Verlag，2001：127.

[11]薛念， 潘赟， 張宇弘， 等. 基于Montgomery模乘的RSA加密處理器[J]. 計(jì)算機(jī)工程， 2010， 36（13）：125.

[12]COUVEIGNES J M， EZOME T， LERCIER R. A faster pseudo-primality test[J].Rendiconti del Circolo Matematico di Palermo，2012，61（2）：261.