RSA數(shù)據(jù)加密算法分析與改進(jìn)

孫赫+李少波

摘要：針對制造物聯(lián)中數(shù)據(jù)的安全快速交換問題，該文提出了一種RSA的算法改進(jìn)方案。RSA算法的核心是模冪運(yùn)算，保證算法的可靠性。但是由于算法的復(fù)雜性導(dǎo)致運(yùn)行速度慢。該文提出多素數(shù)及加速冪乘運(yùn)算改進(jìn)算法，并通過一種計算架構(gòu)（CUDA）實(shí)現(xiàn)算法，結(jié)果表明，改進(jìn)算法的效率更高。

關(guān)鍵詞：RSA算法；CUDA； 算法改進(jìn)；模冪運(yùn)算

中圖分類號：TP309.7 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2016）33-0045-04

Abstract： The problem of rapid exchange for manufacturing complex contact data security， this paper proposes a RSA algorithm improvement scheme. The core of the RSA algorithm is modular power algorithm， which ensures the reliability of the algorithm. However， due to the complexity of the algorithm， the running speed is slow. In this paper， we put forward a new algorithm to improve the multi prime and accelerate power multiplication， and the algorithm is implemented by a computing architecture （CUDA）. The results show that the improved algorithm is more efficient.

Key words： Rivest-Smir-Adleman（RSA）algorithm；CUDA；improve Algorithm； mode power operation

隨著工業(yè)4.0的邁入，中國制造2025[1]與之不謀而合，應(yīng)運(yùn)而生。人們正在全面進(jìn)入“互聯(lián)網(wǎng)+”時代，中國制造2025“互聯(lián)網(wǎng)+工業(yè)”是“互聯(lián)網(wǎng)+”的重要組成部分之一?，F(xiàn)階段通過大規(guī)模定制和網(wǎng)絡(luò)協(xié)同配置的各方面資源、數(shù)據(jù)越來越多，制造業(yè)企業(yè)的實(shí)時數(shù)據(jù)安全處理、傳輸和儲存的要求也會越來越高，保障數(shù)據(jù)的實(shí)時安全傳輸是這個時代迫切需要的?？梢哉f加密技術(shù)無疑是保障數(shù)據(jù)安全傳輸?shù)闹匾胧┲弧SA公鑰密碼是1978年Ron Rivest， Adi Shamirh和LenAdleman提出來的，源于三個作者的首字母，該算法是公鑰加密的行業(yè)標(biāo)準(zhǔn)[2]。RSA加密算法理論基礎(chǔ)是兩個大素數(shù)相乘，然而計算機(jī)技術(shù)的進(jìn)步使得比較短的RSA密鑰可以被攻破。所以，RSA的密鑰在不斷的加長。我國山東大學(xué)的研究人員季凱和他的破解團(tuán)隊成員劉強(qiáng)等人宣布找到了這樣的一種快速素因子分解算法，并且公布了算法，但是并沒有得到最終的證實(shí)?，F(xiàn)在國內(nèi)外在RSA算法的研究上主要集中在算法的優(yōu)化和程序的優(yōu)化上，在算法優(yōu)化方面主要集中在模冪和模乘的快速算法上，最傳統(tǒng)的方法。就是把乘方后求模的運(yùn)算改為一邊乘方一邊求模的運(yùn)算，這種方法最大化避免大數(shù)的乘方運(yùn)算。在一定程度上提高RSA的效率[3]-[5]。

現(xiàn)階段應(yīng)用最為廣泛的加密算法有MD5算法、DES算法及RSA算法[6]-[8]。MD5是將任意長度的“字節(jié)串”變換成一個128bit的大整數(shù)，并且它是一個不可逆的字符串變換算法。DES算法把64位的明文輸入塊變?yōu)?4位的密文輸出塊。而RSA算法是第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法，RSA的安全性一直未能得到理論上的證明，但是它經(jīng)歷了各種攻擊，至今未被完全攻破。較之MD5、DES算法，RSA算法的安全性更高，它的安全性基于數(shù)論中的大素數(shù)分解，該體制是采用足夠大的整數(shù)作模數(shù)。但是大整數(shù)分解問題運(yùn)用了大量的模乘和冪運(yùn)算時間都比較長，所以RSA密碼體制有顯著的缺點(diǎn)就是運(yùn)算效率低下，運(yùn)算時間過長等缺點(diǎn)。那么提高RSA的算法效率是研究RSA密碼體制的重點(diǎn)。

在1976年，W.Diffie和M.E.Hellmam發(fā)表了具有劃時代意義的“密碼學(xué)的新方向”一文，提出了公鑰密碼體制思想，為近代密碼學(xué)的發(fā)展指明了方向。它的出現(xiàn)是密碼學(xué)研究領(lǐng)域中的一項重大突破，也是現(xiàn)代密碼學(xué)誕生的標(biāo)志之一[9]。本文針對物聯(lián)制造數(shù)據(jù)的安全快速傳輸問題，提出了對RSA算法的改進(jìn)。首先對非對稱加密算法RSA進(jìn)行了原理分析，進(jìn)而提出了算法的改進(jìn)和實(shí)現(xiàn)。

1 公開RSA加密算法

RAS算法是現(xiàn)今普遍使用的一種公開秘鑰算法，其本質(zhì)上是一種基于因數(shù)分解的非對稱加密算法，其核心原理就是利用兩個素數(shù)[10]。包含：一個是公鑰以及一個是私鑰，公鑰是唯一解密通過私鑰加密的密文，同時，私鑰也是唯一解密通過公鑰加密的密文，那么這就解決了數(shù)據(jù)的在傳輸過程中由于密鑰的丟失，導(dǎo)致安全性受到威脅的問題。其加密算法流程如下：

從上述流程中不難看出中不難看出傳統(tǒng)的RSA算法采用的公鑰是n=p*q；并通過指數(shù)e二進(jìn)制化后迭代，然后求模運(yùn)算。

2 RAS算法的優(yōu)化

2.1 RSA算法優(yōu)化原則

由于傳統(tǒng)的RSA的安全性依靠于算法過程中的大素數(shù)的因子分解的難度，也就造成了該算法采用的冪指剩余計算太耗時（在加密解密過程要計算大整數(shù)模冪乘）[11]。優(yōu)化原則：（1）提高安全性，最大素數(shù)p和q至少應(yīng)該是在100位以上的十進(jìn)制數(shù)；（2）e的適當(dāng)減小會加快解密速度，但是太小會威脅安全性。

2.2 優(yōu)化RSA算法

2.2.1 多因子優(yōu)化

利用多個素數(shù)因子對算法進(jìn)行加速，此處選取三個素數(shù)因子，可以降低素數(shù)選取需要的時間，通過中國剩余定理[12]得出適當(dāng)?shù)臏p少素數(shù)的位數(shù)，可以降低計算量。那么基本算法描述如下：

首先選擇三個保密大素數(shù)：p、q及r。計算n=p*q*r，[φ（n）=（p-1）（q-1）（r-1）]，[φ（n）] 為歐拉函數(shù)，選擇整數(shù)e，有[gcd（φ（n），e）=1] ，計算[d*e=1modφ（n）]，以{e，n}為公開鑰，{p，q，r}為密鑰，與傳統(tǒng)RSA相比較，若明文m大于n，則需將m分塊使得每一塊數(shù)據(jù)都小于n-1，進(jìn)而進(jìn)行c=m^emod n。

2.2.2 冪指運(yùn)算優(yōu)化

傳統(tǒng)的RAS算法指數(shù)e的比特序列長度很大，需要在計算過程中多次迭代，因此找出最短的指數(shù)序列減少迭代次數(shù)是加速該算法的手段之一。那么，采用將指數(shù)e進(jìn)行2^k進(jìn)制化的方式達(dá)到加速算法的目的。

3 改進(jìn)RSA算法實(shí)現(xiàn)

3.1 改進(jìn)RSA模冪單元分析

3.2 基于CUDA的算法實(shí)現(xiàn)

3.3 具體實(shí)現(xiàn)方法

4 數(shù)據(jù)的驗證分析

基于物聯(lián)制造實(shí)驗室，運(yùn)用由NVIDIA公司開發(fā)的GeForce GTX960對采集的數(shù)據(jù)進(jìn)行驗證，首先對改進(jìn)算法的加密過程進(jìn)行了數(shù)據(jù)分析如下：

基于CUDA對RSA算法加密進(jìn)行數(shù)據(jù)驗證。最下方的曲線為所求曲線，從圖中可以得出最下方的在加密過程中完全優(yōu)于另外曲線。所以在采用三因子素數(shù)及冪指優(yōu)化算法可以在很大程度上提高加密效率。

下面將基于CUDA模式下對大整數(shù)模冪的運(yùn)算性能對三種算法分別進(jìn)行對1024 和2048位從運(yùn)算次數(shù)進(jìn)行解密分析：

改進(jìn)RSA算法的解密過程基于CUDA完。在CUDA模式下，令y={2，128，512，1024，2048…}為運(yùn)算次數(shù)。y值的增加會使并行的線程塊增加，運(yùn)算的速度會越來越快。這里達(dá)到2048位運(yùn)算依然流暢進(jìn)行，但是隨著位數(shù)的時候會由于GPU本身的最大計算能力而下降。因為線程塊越多意味著對儲存器的訪問次數(shù)越多，從而降低計算能力。但是從2張比較圖可以看出改進(jìn)后的RSA算法（最下方曲線）的解密效率同樣很高。

5 結(jié)束語

在數(shù)據(jù)與工業(yè)的密切結(jié)合的時代里，改進(jìn)加密算法用以保障數(shù)據(jù)的安全十分重要。本文首先對傳統(tǒng)BR算法進(jìn)行了闡述，然后提出改進(jìn)RSA算法，并且對改進(jìn)算法進(jìn)行了模冪單元分解，然后基于CUDA將模冪單元運(yùn)算加載到GPU上的線程塊進(jìn)行了解密分析。結(jié)果分析表明，通過在GPU上對傳統(tǒng)BR和冪指算法的對比，在·改進(jìn)的RSA算法的運(yùn)算效率顯著提升。

參考文獻(xiàn)：

[1] 黃群慧， 賀俊. 中國制造業(yè)的核心能力、功能定位與發(fā)展戰(zhàn)略——兼評《中國制造2025》[J]. 中國工業(yè)經(jīng)濟(jì)， 2015（6）：5-17.

[2] A distributed algorithm to find safe RSA keys[M]// Distributed Programming Paradigms with Cryptography Applications. Springer Berlin Heidelberg， 1994：37-60.

[3] ALFRED J.MENEZES[加]. 應(yīng)用密碼學(xué)手冊[M]. 電子工業(yè)出版社， 2005.

[4] 周玉潔， 馮登國. 公開密鑰密碼算法及其快速實(shí)現(xiàn)[M]. 國防工業(yè)出版社， 2002.

[5] 孫寶林， 楊球， 吳長海. RSA公開密鑰密碼算法及其在信息交換中的應(yīng)用[J]. 武漢理工大學(xué)學(xué)報（交通科學(xué)與工程版）， 2000， 24（2）：169-172.

[6] 魏曉玲. MD5加密算法的研究及應(yīng)用[J]. 信息技術(shù)， 2010（7）：145-147.

[7] 夏淑華. 基于DES和RSA加密算法的數(shù)據(jù)安全傳輸技術(shù)的研究[J]. 制造業(yè)自動化， 2011， 33（2）：180-182.

[8] 步山岳. RSA加密算法分析與實(shí)現(xiàn)[J]. 信息安全與通信保密， 2007（10）：80-81.

[9] 任偉. 現(xiàn)代密碼學(xué)[M]. 北京郵電大學(xué)出版社， 2014.

[10] Kalpana P， Singaraju S. Data Security in Cloud Computing using RSA Algorithm[J]. 2012.

[11] Xin， Zhou， Xiaofei， et al. Research and implementation of RSA algorithm for encryption and decryption[C]// Strategic Technology （IFOST）， 2011 6th International Forum on. IEEE， 2011：1118 - 1121.

[12] 楊坤偉， 李吉亮， 張瑞麗. 中國剩余定理在密碼學(xué)中的應(yīng)用研究[J].計算機(jī)技術(shù)與發(fā)展，2014（1）：238-241.

[13] T?lke B J. Implementation of a Lattice Boltzmann kernel using the Compute Unified Device Architecture developed by nVIDIA， Computing and Visualization in Science 1–11[J]. 2010.

[14] 孫迎紅， 童元滿， 王志英. RSA算法的CUDA高效實(shí)現(xiàn)技術(shù)[J]. 計算機(jī)工程與應(yīng)用， 2011， 47（2）：84-87.

[15] Sun D Z， Huai J P， Cao Z F. A comment on “An efficient common-multiplicand-multiplication method to the Montgomery algorithm for speeding up exponentiation”[J]. Information Sciences， 2013， 223（223）：331-334.