廖彬宇

摘要：隨著科技快速發(fā)展，人們非常重視信息安全。而RSA密碼體制是信息安全領(lǐng)域使用非常廣泛的算法。由于RSA算法的安全性是依靠大整數(shù)冪乘，所以在安全性和效率之間存在著一定的問題。為了提高算法的效率，該文提出了一種對(duì)負(fù)載均衡RSA算法的改進(jìn)方法。與負(fù)載均衡RSA算法相比，改進(jìn)的負(fù)載均衡RSA算法在計(jì)算速度上有著一定程度的提升。

關(guān)鍵詞：RSA算法；效率；安全；負(fù)載均衡RSA算法；提升

中圖分類號(hào)：TP309 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）25-0025-02

The Improved Load-balancing RSA Algorithm

LIAO Bin-yu

（College of Computer ， China West Normal University ， Nanchong 637009 ， China）

Abstract：With the rapid development of science and technology， people attach great importance to information security. The RSA cryptosystem is a very widely used algorithm in the field of information security. Because the security of the RSA algorithm relies on large integer power， there is a certain problem between security and efficiency. In order to improve the efficiency of the algorithm， this paper proposes an improved method for load-balancing RSA algorithm. Compared with the load-balancing RSA algorithm， the improved load-balancing RSA algorithm has a certain degree of improvement in calculation speed.

Key words： RSA algorithm； efficiency； security： load-balancing RSA algorithm：improvement

隨著科技的發(fā)展，社會(huì)的進(jìn)步，在網(wǎng)絡(luò)中產(chǎn)生了異常龐大的數(shù)據(jù)量，而信息的安全性則變得越來越重要，因此對(duì)信息進(jìn)行保密的密碼正在飛速發(fā)展。由美國 MIT 的 Rivest、Shamir 和Adleman 在 1978 年提出來的RSA加密解密算法[2]是使用最廣泛的密碼之一，該密碼是屬于非對(duì)稱密碼體制，公鑰是公開的，私鑰是保密的，且兩個(gè)密鑰不一致。RSA算法[4]的安全性是由大整數(shù)因子分解的困難程度來保障的，整數(shù)越大，分解難度越大，也越能保障安全性，但是提升安全性的同時(shí)卻降低了計(jì)算的速度，針對(duì)這一問題，負(fù)載均衡RSA算法能夠有效提升計(jì)算速度，而本文提出了一種對(duì)負(fù)載均衡RSA算法的改進(jìn)方法來進(jìn)一步提升效率。

1 RSA算法描述

算法具體運(yùn)算過程如下[5]：

1.1 密鑰的產(chǎn)生

①選擇兩個(gè)隨機(jī)大素?cái)?shù)p和q；

②然后計(jì)算 n = p × q，Φ （ n） = （ p - 1） （ q - 1） ；

③接著隨機(jī)選擇一個(gè)整數(shù) e，滿足 gcd（ e，Φ（ n） ） = 1；

④其次利用歐幾里得擴(kuò)展算法來計(jì)算e關(guān)于模n的乘法逆元d，即 ed≡1 mod （Φ （ n）） ；

⑤最后公開 n、e 作為加密密鑰，保密 p、q、d、Φ （ n） ，將 n、d 作為解密密鑰。

1.2 加密算法

對(duì)明文M進(jìn)行加密，利用公鑰（n，e）進(jìn)行計(jì)算得到密文 C= Me mod n。

1.3 解密算法

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

2 負(fù)載均衡RSA算法

為了改進(jìn)大整數(shù)冪乘，在文獻(xiàn)[9]中提出了一種負(fù)載均衡算法，以加密過程來說明負(fù)載均衡算法的操作過程：

（1）假設(shè)明文M可以分解為多個(gè)小整數(shù)相乘的形式，形式為 M=M1×M2×…×Mn，那么加密過程C=Me（mod n）就變?yōu)镃=（M1×M2×…×Mn）e（mod n），進(jìn)一步變形為C=M1eM2e… Mne（mod n）。

（2）經(jīng)過變換之后，明文M被分解為多個(gè)部分，這樣就可以把每個(gè)部分均衡地分配到計(jì)算進(jìn)程中，然后每個(gè)進(jìn)程獨(dú)立完成運(yùn)算。

（3）假設(shè)明文分解為12個(gè)子明文（M1，…，M12），現(xiàn)有3個(gè)進(jìn)程（K1，K2，K3），每個(gè)進(jìn)程平均分配4個(gè)任務(wù)。那么進(jìn)程 K1 進(jìn)行 M1，M2，M3 ，M4的冪乘運(yùn)算，K2 進(jìn)行 M5，M6，M7，M8 的冪乘運(yùn)算，K3則進(jìn)行 M9，M10，M11，M12 的冪乘運(yùn)算。

（4）由于分解后各個(gè)數(shù)的大小不一致，所以這樣分配存在一個(gè)問題，有可能較大的四個(gè)整數(shù)分配到了同一個(gè)進(jìn)程中，較小的四個(gè)整數(shù)分配到了同一個(gè)進(jìn)程中。那么就會(huì)導(dǎo)致其中一個(gè)或幾個(gè)進(jìn)程的計(jì)算量巨大，而其他的進(jìn)程計(jì)算量較小，這就使任務(wù)分配不夠均衡。而最終的乘積運(yùn)算要等到所有任務(wù)結(jié)束之后才會(huì)進(jìn)行，那么計(jì)算量較小的任務(wù)就會(huì)一直等待計(jì)算量較大的任務(wù)完成運(yùn)算，徒增等待時(shí)間。

（5）因此對(duì)分解后的數(shù)進(jìn)行排序，滿足M1≤M2≤M3≤......≤M12，把M1分配給第一號(hào)進(jìn)程，把M2分配給第二號(hào)進(jìn)程，把M3分配給第三號(hào)進(jìn)程，M4分配給第一號(hào)進(jìn)程，M5分配給第二號(hào)進(jìn)程，分配規(guī)則為Mi分配給i（mod k）。

（6）所有進(jìn)程完成計(jì)算后，再對(duì)各個(gè)任務(wù)的計(jì)算結(jié)果進(jìn)行乘積運(yùn)算。

3 改進(jìn)的負(fù)載均衡RSA算法

這里對(duì)負(fù)載均衡RSA算法的分配方法進(jìn)行改進(jìn)，開始步驟和上文一致，首先需要把明文M分解為M1，M2，M3.....Mn，然后按照從小到大的順序排列好，順序如M1≤M2≤…≤Mn。接著開始分配，把M1分配給第一個(gè)進(jìn)程，M2分配給第二個(gè)進(jìn)程，按照順序逐個(gè)分配。最后在原來分配方法的基礎(chǔ)上提出改進(jìn)，這個(gè)分配方法能夠提升計(jì)算效率。

該算法步驟如下：

（1）把明文M分解成多個(gè)小素?cái)?shù)的乘積形式，即 M=M1×M2×…×Mn。

（2）然后對(duì)各個(gè)小整數(shù)進(jìn)行排序，排序滿足M1≤M2≤…≤Mn。

（3）排序結(jié)束后開始給進(jìn)程分配任務(wù)，分配規(guī)則為：假設(shè)有n個(gè)小素?cái)?shù)，有k個(gè)進(jìn)程，令a=n （mod k），然后先放置從M1開始的a個(gè)數(shù)，剩下的n-a個(gè)數(shù)剛好可以使k個(gè)進(jìn)程完全分配。接著從第（a+1）個(gè)數(shù)開始分配給第一個(gè)進(jìn)程，第（a+2）個(gè)數(shù)分配給第二個(gè)進(jìn)程，逐個(gè)分配，直到第n個(gè)數(shù)分配結(jié)束。最后把從M1開始的a個(gè)數(shù)從第一個(gè)進(jìn)程開始依次往后分配給進(jìn)程。

（4）每個(gè)進(jìn)程獨(dú)立完成任務(wù)的計(jì)算。

（5）必須等到所有進(jìn)程計(jì)算結(jié)束之后，才能把各個(gè)進(jìn)程的冪乘結(jié)果進(jìn)行最后的乘積運(yùn)算得出結(jié)果。

4 改進(jìn)的負(fù)載均衡RSA算法性能分析

我們可以通過列舉簡單的例子來說明兩個(gè)算法的實(shí)用性。假設(shè)M分解成10個(gè)素?cái)?shù)（7，11，19，23，37，43，59，71，83，97），現(xiàn)在有4個(gè)進(jìn)程（k1，k2，k3，k4）。M=7*11*19*23*37*43*59*71*83*97，未改進(jìn)的負(fù)載均衡算法分配如下：

k1（7，37，83），k2（11，43，97），k3（19，59），k4（23，71）。改進(jìn)的負(fù)載均衡算法分配如下：k1（19，59，7），k2（23，71，11），k3（37，83），k4（43，97）。

則未改進(jìn)的負(fù)載均衡算法的任務(wù)如下：

k1=（7*37*83）e=21497e ，k2=（11*43*97）e=45881e，

k3=（19*59）e=1121e，k4=（23*71）e=1633e，

所以最大任務(wù)為k2=45881e 。

改進(jìn)的負(fù)載均衡算法的任務(wù)如下：

k1=（19*59*7）e=7847e，k2=（23*71*11）e=17963e，

k3=（37*83）e=3071e，k4=（43*97）e=4171e。

所以最大任務(wù)為k2==17963e。

由于最終的乘積運(yùn)算要等到所有進(jìn)程的計(jì)算任務(wù)結(jié)束之后才會(huì)進(jìn)行，所以決定執(zhí)行時(shí)間的關(guān)鍵是最大任務(wù)的計(jì)算時(shí)間。從兩個(gè)例子可以看出未改進(jìn)的負(fù)載均衡算法最大任務(wù)為k2=45881e，改進(jìn)的負(fù)載均衡算法最大任務(wù)為k2==17963e。由于改進(jìn)的負(fù)載均衡算法的最大任務(wù)相對(duì)較小，很明顯可以得出改進(jìn)的負(fù)載均衡算法可以提升計(jì)算效率。

5 結(jié)語

本文分析了RSA負(fù)載均衡算法，在此算法基礎(chǔ)上，對(duì)算法的任務(wù)分配進(jìn)行了改進(jìn)。通過列舉的例子得出該改進(jìn)算法能在一定程度上提升算法的計(jì)算效率，具有一定的實(shí)際意義。但是還可以繼續(xù)提升算法的計(jì)算速度，未來還要繼續(xù)致力于研究提升RSA算法的計(jì)算速度。

參考文獻(xiàn)：

[1] 黃健.RSA公鑰加密體制的安全性分析與改進(jìn)[J].計(jì)算機(jī)與網(wǎng)絡(luò)，2016，42（01）：70-73.

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

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

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

[5] 賈美娟，孔靚，李梓，等.RSA算法研究及其計(jì)算技巧分析[J].大慶師范學(xué)院學(xué)報(bào)，2012，32（6） ： 14-16.

[6] 趙悅.基于RSA加密解密的即時(shí)通訊系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].吉林大學(xué)，2016.

[7] 孫偉.公鑰RSA加密算法的改進(jìn)與實(shí)現(xiàn)[D].安徽大學(xué)，2014.

[8] 程曉榮，馬力，何壯壯.公鑰RSA加密算法的分析與改進(jìn)[J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用，2015（08）：44-45.

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

[10] Mahaveerakannan R， Dhas C S G. Customized RSA public key cryptosystem using digital signature of secure data transfer natural 22 number algorithm[J]. International Journal of Computer Technology & Applications， 2016， 9（5）： 2627-2632.

【通聯(lián)編輯：代影】