RSA加密算法的研究

李瑩 趙瑞 曹宇 張天宇 劉霏凝

摘要：隨著互聯網和通信技術的發展，信息安全問題日益受到重視，基于數據加密的信息安全技術得到了迅速的發展。數據加密就算法而言，分為對稱加密和非對稱加密兩類。RSA是應用最廣泛的非對稱算法之一，具有安全性高、易于實現等特點，但運算速度很慢，只能用于一些少量數據。針對RSA運算效率慢的問題，提出了中國剩余定理和蒙哥馬利模乘法相結合的方法來優化模冪，用三素數代替傳統的二重素數。實驗結果表明，優化算法具有較高的速度和可行性。

關鍵詞： 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 引 言

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

1 密碼學

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

2 RSA算法

2.1 算法原理

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

2.1.1 密鑰生成

在數據加密之前完成，密鑰生成過程如下：

步驟1 為保證數據的完整性，將通過考慮2個不同的隨機素數（如具有相似位長的g和h）來選擇輸入。

步驟2 計算i = g * h。

步驟3 計算歐拉函數：（i） = （g-1）*（h-1）。

步驟4 選擇一個整數a，1 < a <（i）和最大公約數， （i）是1?，F在，將其作為公鑰指數發布。

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

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

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

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

2.1.2 加密

將原始數據轉換為密碼數據的過程被定義為加密。建議的加密程序如下：

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

步驟2 可逆協議用于將用戶數據映射到稱為填充方案的整數。

步驟3 對所需的數據進行加密，得到的密碼數據C由C=me（mod i）給出。

2.1.3 解密

將密碼數據轉換為原始數據的過程被定義為解密。建議的解密程序如下：

步驟1 向用戶提出請求。

步驟2 使用生成的私鑰和加密的數據來驗證用戶的真實性。

步驟3 用戶將數據解密為m = Cd （mod i）。

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

2.2 RSA算法的改進及應用

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

2.2.1 三素數RSA算法基本原理

在傳統雙素數RSA密碼算法[8]的基礎上，取3個素數，仍建立算法，描述如下：

（1）隨機選取3個不同的大素數p、q、r，計算n=pqr，（n）=（p-1）（q-1）（r-1）。

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

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

2.2.2 利用蒙哥馬利模乘法和中國剩余定理進行優化

由表2可知，利用中國剩余定理進行雙素數RSA優化的效率是傳統算法的3.36倍，接近理論值3.47。使用中國剩余定理和蒙哥馬利模乘法的三素數RSA算法的效率是傳統算法的5.4倍，是雙素數RSA算法的1.6倍。結果表明，改進后的RSA算法可以大大提高速度。

4 結束語

本文主要研究了常用非對稱加密算法RSA。研究中，探討分析了其研究現狀，改進了算法的不足之處，通過比較2個素數和3個素數之間的運行效率，可以看出安全性能的提高，證明了改進算法的優勢。

參考文獻

[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]. 計算機工程， 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.