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

廖彬宇 賴曉風(fēng)

摘要：RSA算法具有很好的保密性，在信息安全領(lǐng)域廣泛使用，但是算法的運(yùn)算效率緩慢，在2種提升計算速度算法的基礎(chǔ)上提出了RSA綜合分解算法。該算法結(jié)合了2種算法的優(yōu)點(diǎn)而產(chǎn)生，性能有進(jìn)一步的提升。與傳統(tǒng)的RSA算法相比，改進(jìn)的RSA算法在計算速度上有著明顯的提升，還擁有良好的可擴(kuò)展性，因此該算法具有較好的實(shí)際意義。

關(guān)鍵詞：安全；效率；RSA算法；RSA綜合分解算法；提升

中圖分類號：TP309文獻(xiàn)標(biāo)志碼：A文章編號：1008-1739（2018）14-65-3

Research on Improvement of RSA Algorithm

LIAO Binyu， LAI Xiaofeng

（College of Computer， China West Normal University， NanChong Sichuan 637009， China）

0引言

在現(xiàn)代社會中，由于科學(xué)的進(jìn)步和計算機(jī)技術(shù)的提升，指數(shù)級的信息充斥著我們的周圍，信息安全的問題在科學(xué)技術(shù)發(fā)展過程中變得越來越突出，因此信息安全成為了人們非常關(guān)注的問題。許多科學(xué)家提出了各種各樣對網(wǎng)絡(luò)中信息進(jìn)行保護(hù)的方法，應(yīng)用最廣泛的是由美國MIT的Rivest、Shamir和Adleman在1978年提出來的RSA加密解密算法[1-2]，該算法是公鑰密碼體制中的代表。公鑰密碼體制是一種非對稱的密碼體制，算法的加密密鑰是公開的，而解密密鑰只有信息的接收者知道。RSA算法[3]的安全性是由大整數(shù)因子分解的困難程度來保障的，當(dāng)模數(shù)的位數(shù)在2 048位時，安全性能夠得到很好的保障，但是提升安全性的同時卻降低了計算的速度，針對這一問題，本文提出了一種改進(jìn)方法來提升效率。

1 RSA算法

算法的主要步驟如下：

（1）密鑰的產(chǎn)生

選擇2個隨機(jī)大素數(shù)和；②然后計算=×，（ ）=（ -1）（ -1）；③接著隨機(jī)選擇一個整數(shù)，滿足gcd（，（ ））=1；④其次利用歐幾里得擴(kuò)展算法來計算關(guān)于模的乘法逆元，即≡1 mod（（ ））；⑤最后公開、作為加密密鑰，保密、、、（ ），將、作為解密密鑰。

（2）加密算法

（3）解密算法

經(jīng)過加密算法得到了密文，然后利用解密密鑰（，）計算得到明文=mod。

2 RSA算法的改進(jìn)基礎(chǔ)

2.1模數(shù)的多次分解算法

多次分解RSA算法定義如下[6]：

①隨機(jī)選個素數(shù)1，2，…，；

②計算=1*2*…*，（ ）=（1-1）*（2-1）*…*（ -1）；

③隨機(jī)選擇整數(shù)滿足gcd （，（ ））=1；

④計算，使?jié)M足≡1 mod （（ ））；

⑤公開{，}作為加密密鑰，保密1，2，…，，（ ），解密密鑰為{，}；

⑥加密算法：=mod，解密算法：=mod。

2.2負(fù)載均衡算法

為了改進(jìn)大整數(shù)冪乘，在文獻(xiàn)[7]中提出了明文大整數(shù)分解的方法，該方法思想如下，這里以加密算法進(jìn)行說明。

①設(shè)明文可以分解為多個小整數(shù)1，2，…，的乘積，即=1×2×…×，那么加密算法就變?yōu)? （1×2×…×） （mod ），進(jìn)一步變形為=1e

2e…（mod ）。

②從式子中可以看出1，2…相互之間沒有聯(lián)系，是獨(dú)立的存在，憑借這一特點(diǎn)，可以將每一部分逐個分配到計算進(jìn)程中。

③假設(shè)明文分解為9個子明文（1，…，9），現(xiàn)有3個進(jìn)程（1，2，3）。進(jìn)程1進(jìn)行1、2、3的冪乘運(yùn)算，2進(jìn)行4，

5和6的冪乘運(yùn)算，按順序分配，3則進(jìn)行7、8和9的冪乘運(yùn)算。

④但是這里存在一個問題，分解后的各個整數(shù)大小是不一樣的，有較大的整數(shù)，也有較小的整數(shù)。如果較小的整數(shù)分配在同一個進(jìn)程中，較大的整數(shù)分配在同一個進(jìn)程中，導(dǎo)致分配了較小整數(shù)的進(jìn)程較早完成任務(wù)，分配了較大整數(shù)的進(jìn)程較晚完成任務(wù)。然而最終的乘積運(yùn)算需要等到所有的進(jìn)程任務(wù)完成后才能進(jìn)行，所以會導(dǎo)致某些進(jìn)程提前完成任務(wù)后進(jìn)行等待，額外地增加等待時間。因此負(fù)載均衡算法就是讓每個進(jìn)程的任務(wù)分配更加合理，盡可能任務(wù)大小一致。

3 RSA綜合分解算法

由于模數(shù)是一個大整數(shù)，那么在密鑰生成階段利用來求解加密密鑰和解密密鑰的計算速度是低效的。此外如果在加密運(yùn)算當(dāng)中的明文也是一個龐大的整數(shù)，那么算法的加密運(yùn)算就是關(guān)于大整數(shù)的冪乘，同樣解密運(yùn)算也是關(guān)于大整數(shù)的冪乘，這樣就會導(dǎo)致冪乘運(yùn)算異常的復(fù)雜，并且計算速度非常的緩慢。

因此在模數(shù)的多次分解算法和負(fù)載均衡算法的基礎(chǔ)上，提出RSA綜合分解算法。通過對RSA算法的了解，算法過程可以大致分為密鑰生成及加密和解密2個階段。

①密鑰生成：要完成信息的保密工作，必須先要有密鑰，如果能提升密鑰生成速度，則可以減少算法執(zhí)行的時間，而模數(shù)的多次分解算法則是在密鑰生成階段進(jìn)行的改進(jìn)。

②加密和解密：對明文的加密和對密文的解密是該階段的主要工作。而負(fù)載均衡算法分解明文并盡可能均勻地分配到計算進(jìn)程中，以此來提升加密和解密速度，縮短計算時間。

RSA算法的運(yùn)算過程是由密鑰生成和加密解密組成，必須首先生成密鑰才能進(jìn)行加密解密，因此算法的2個階段是遞進(jìn)關(guān)系。算法總的執(zhí)行時間是由2個階段的運(yùn)算時間相加而來，即密鑰生成的運(yùn)算時間加上加密解密的運(yùn)算時間，所以提升2個階段的運(yùn)算時間，無疑能有效地提升算法總的執(zhí)行時間。

因此，基于該思想，把密鑰生成階段的改進(jìn)和加密解密階段的改進(jìn)結(jié)合起來生成RSA綜合分解算法。以加密過程為例，該算法描述如下：

①隨機(jī)選個素數(shù)1，2，…，；

②計算=1*2*…*，（ ）=（1-1）*（2-1）*…*（ -1）；

③隨機(jī)選擇整數(shù)滿足gcd （，（ ））=1；

④計算，使?jié)M足≡1 mod （（ ））；

⑤公開{，}作為加密密鑰，保密1，2，…，，（ ），解密密鑰為{，}；

⑥把明文分解成多個小整數(shù)，即=1×2×…×，而1，2，…，是素數(shù)；

⑦分解之后，對每個小整數(shù)進(jìn)行排序，順序滿足1≤2≤…≤；

⑧排序結(jié)束后，對任務(wù)進(jìn)行分配，分配原則：假設(shè)有個進(jìn)程，把1分配給1，2分配給2，3分配給3，即分配給（mod）號進(jìn)程；

⑨分配完成之后即可以進(jìn)行冪乘計算了，每個進(jìn)程各自進(jìn)行；

⑩在每個進(jìn)程完成計算任務(wù)之后，再進(jìn)行總的乘積運(yùn)算，最終完成RSA加密算法的計算。

4 RSA綜合分解算法性能分析

模數(shù)的多次分解算法是將大整數(shù)分解為多個素數(shù)相乘，具體的個數(shù)可以是任意的，當(dāng)然分解的個數(shù)越多，數(shù)值就越小，這樣計算機(jī)在對這些素數(shù)進(jìn)行運(yùn)算的時候就可以提高計算速度。此外算法中分解出的多個素數(shù)，增加了模數(shù)的分解難度，提高了算法的安全性。已通過實(shí)驗(yàn)證明當(dāng)=2 048 bit時，模數(shù)的4次分解算法的解密時間是傳統(tǒng)RSA算法解密時間的2.69倍，是模數(shù)的3次分解算法的1.90倍[6]，具體數(shù)據(jù)如表1所示。

而對于負(fù)載均衡算法，原來的明文大整數(shù)就變?yōu)榱硕鄠€小整數(shù)，計算多個小整數(shù)的冪乘所花費(fèi)的時間比大整數(shù)的冪乘明顯減小，雖然分解成多個小整數(shù)需要花費(fèi)一些時間，但是與大整數(shù)冪乘相比，小巫見大巫。因此借鑒小整數(shù)冪乘速度快于大整數(shù)冪乘速度的原理，可以得出分解后的冪乘速度有著明顯提升，實(shí)驗(yàn)數(shù)據(jù)也表明負(fù)載均衡算法對計算效率有著顯著的提升[7]，具體數(shù)據(jù)如表2所示。

通過表1和表2的數(shù)據(jù)，可以知道作為密鑰生成階段的模數(shù)的多次分解算法比傳統(tǒng)RSA算法的計算時間更短，效率更高。作為加密解密階段的負(fù)載均衡算法隨著進(jìn)程的增多而逐漸縮短執(zhí)行時間。因此得出2個階段計算效率的共同提升可以進(jìn)一步提高RSA綜合分解算法的運(yùn)算效率。

5結(jié)束語

本文分析說明了模數(shù)的多次分解算法和負(fù)載均衡算法分別在密鑰生成和加密解密階段對計算效率的提升，在此基礎(chǔ)上提出RSA綜合分解算法。已通過相關(guān)實(shí)驗(yàn)數(shù)據(jù)說明該改進(jìn)算法在效率上有著進(jìn)一步的提高，具有一定的實(shí)際價值，在未來將繼續(xù)致力于改進(jìn)計算速度的研究。

參考文獻(xiàn)

[1]陳春玲，齊年強(qiáng)，余瀚.RSA算法的研究和改進(jìn)[J].計算機(jī)技術(shù)與發(fā)展，2016，26（8）：48-51.

[2]陳鵬飛，何小東.RSA算法的分析與改進(jìn)[J].電子世界，2015（13）：111-113.

[3]王樹天.RSA算法的改進(jìn)和實(shí)現(xiàn)[J].內(nèi)蒙古科技與經(jīng)濟(jì)，2015（16）：93-94.

[4]陳若寒，陳舒.RSA加密算法的研究[J].數(shù)字通信世界，2017（10）：210.

[5]葉秀芳.RSA算法的優(yōu)化策略[J].電子設(shè)計工程，2017，25（20）：83-85，89.

[6]劉平，趙煥平.改進(jìn)RSA算法的分析研究[J].計算機(jī)與現(xiàn)代化，2013（7）：84-86，90.

[7]唐笑林.高效RSA算法的研究與并行實(shí)現(xiàn)[J].計算機(jī)工程， 2013，39（2）：164-167，171.