改進的負載均衡RSA算法

廖彬宇

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

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

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

1 RSA算法描述

算法具體運算過程如下[5]：

1.1 密鑰的產(chǎn)生

①選擇兩個隨機大素數(shù)p和q；

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

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

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

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

1.2 加密算法

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

1.3 解密算法

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

2 負載均衡RSA算法

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

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

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

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

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

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

（6）所有進程完成計算后，再對各個任務的計算結(jié)果進行乘積運算。

3 改進的負載均衡RSA算法

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

該算法步驟如下：

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

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

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

（4）每個進程獨立完成任務的計算。

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

4 改進的負載均衡RSA算法性能分析

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

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

則未改進的負載均衡算法的任務如下：

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

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

所以最大任務為k2=45881e 。

改進的負載均衡算法的任務如下：

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

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

所以最大任務為k2==17963e。

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

5 結(jié)語

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

參考文獻：

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

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

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

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

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

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

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

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

[9] 唐笑林.高效RSA算法的研究與并行實現(xiàn)[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)編輯：代影】