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

廖彬宇 賴曉風(fēng)

摘要：RSA算法具有很好的保密性，在信息安全領(lǐng)域廣泛使用，但是算法的運(yùn)算效率緩慢，在2種提升計(jì)算速度算法的基礎(chǔ)上提出了RSA綜合分解算法。該算法結(jié)合了2種算法的優(yōu)點(diǎn)而產(chǎn)生，性能有進(jìn)一步的提升。與傳統(tǒng)的RSA算法相比，改進(jìn)的RSA算法在計(jì)算速度上有著明顯的提升，還擁有良好的可擴(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ì)算機(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位時(shí)，安全性能夠得到很好的保障，但是提升安全性的同時(shí)卻降低了計(jì)算的速度，針對這一問題，本文提出了一種改進(jìn)方法來提升效率。

1 RSA算法

算法的主要步驟如下：

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

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

（2）加密算法

（3）解密算法

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

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

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

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

①隨機(jī)選個(gè)素?cái)?shù)1，2，…，；

②計(jì)算=1*2*…*，（ ）=（1-1）*（2-1）*…*（ -1）；

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

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

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

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

2.2負(fù)載均衡算法

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

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

2e…（mod ）。

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

③假設(shè)明文分解為9個(gè)子明文（1，…，9），現(xiàn)有3個(gè)進(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)算。

④但是這里存在一個(gè)問題，分解后的各個(gè)整數(shù)大小是不一樣的，有較大的整數(shù)，也有較小的整數(shù)。如果較小的整數(shù)分配在同一個(gè)進(jìn)程中，較大的整數(shù)分配在同一個(gè)進(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)行等待，額外地增加等待時(shí)間。因此負(fù)載均衡算法就是讓每個(gè)進(jìn)程的任務(wù)分配更加合理，盡可能任務(wù)大小一致。

3 RSA綜合分解算法

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

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

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

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

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

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

①隨機(jī)選個(gè)素?cái)?shù)1，2，…，；

②計(jì)算=1*2*…*，（ ）=（1-1）*（2-1）*…*（ -1）；

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

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

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

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

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

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

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

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

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

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

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

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

5結(jié)束語

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

參考文獻(xiàn)

[1]陳春玲，齊年強(qiáng)，余瀚.RSA算法的研究和改進(jìn)[J].計(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è)計(jì)工程，2017，25（20）：83-85，89.

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

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