陸玉陽

摘要：RSA加密算法在進(jìn)行復(fù)雜判斷和大數(shù)運算時，計算時間往往花費較多，對計算機的運行速度、存儲容量等方面具有較高的要求。MPI能夠提供較快的數(shù)值計算和數(shù)據(jù)處理能力，提供高性能并行計算。該文通過在RSA加密算法中MPI的應(yīng)用，通過實踐證明MPI并行計算可以改進(jìn)RSA算法，提高加密速度、減少容量需求等。

關(guān)鍵詞：RSA；MPI；加密；并行計算

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2015）28-0040-03

Application of MPI in RSA encryption algorithm

LU Yu-yang

（Xuzhou College of Industrial Technology， Xuzhou 221140， China）

Abstract： RSA encryption algorithm in the complex judgment and operation of large Nbers， calculating the time tend to spend more， the computer run faster， have higher requirements in terms of storage capacity. MPI provides fast Nerical calculation and data processing capability， providing high performance parallel computing. Based on RSA encryption algorithm in application of MPI， MPI parallel computing can improve the RSA algorithm proved by practice， increase speed， reduce capacity requirements， and so on.

Key words： RSA；MPI； encryption； parallel computing

公鑰密碼算法包括RSA算法、Diffie-Hellman算法、ElGamal算法、背包算法以及橢圓曲線密碼算法等，RSA加密算法作為公開密鑰密碼體現(xiàn)中的一個典型，其應(yīng)用最為廣泛，RSA加密算法既可加密，也可用于數(shù)字簽名。RSA加密算法在進(jìn)行復(fù)雜判斷和大數(shù)運算時，計算時間往往花費較多，對計算機的運行速度、存儲容量等方面具有較高的要求，針對RSA加密算法的運行速度而且盡可能少耗費資源一直是密碼學(xué)領(lǐng)域研究的熱點問題。

MPI（消息傳遞接口Message Passing Interface），MPI是一個庫，而不是一門語言，具有巨大的數(shù)值計算和數(shù)據(jù)處理能力，提供高性能并行計算，即通過把一個大的計算問題分解成許多彼此獨立且有相關(guān)的子問題，然后把他們散列到各個節(jié)點機上并行執(zhí)行從而最終解決問題的一種方法。并行計算的提示有效地改進(jìn)了RSA加密算法的缺點。本文以RSA加密算法為出發(fā)點，通過MPI的應(yīng)用，通過實驗有效地證明了在RSA加密算法中MPI能夠提升加密速度、降低容量需求，提高數(shù)據(jù)的安全性。

1 RSA加密算法

RSA（RonaldRivist、AdiShamir和LenAdlemar三人的名字共同命名）是一種應(yīng)用較為廣泛的公鑰算法，也是他們開發(fā)出的第一個公鑰密碼體制，并在未來的20多年時間內(nèi)得到了充分肯定。RSA是以分組的方式對明文進(jìn)行加密，RSA密鑰產(chǎn)生過程如下：

①它隨機地選擇兩個大質(zhì)數(shù)p和q（需保密）；

②p*q=n；

③在任找一個數(shù)m，要求滿足m

④計算得到d=m-1mod[（p-1）*（q-1）]；這里d是私密指數(shù)，m代表公開指數(shù)；

⑤獲得公匙（n，m），私匙（n，d）；

⑥刪除p和q；

加密算法實現(xiàn)原理就是將明文數(shù)據(jù)分解成比n小的數(shù)據(jù)塊用公開指數(shù)作乘方取模運算：c=me mod n（其中m代表明文塊，c代表密文塊）；解密過程恰恰相反：即把密文數(shù)據(jù)塊依托私密指數(shù)進(jìn)行乘方取模運算：m=cd mod n。網(wǎng)絡(luò)攻擊者有公匙：e和n，為了獲得私匙d，則會對n行因數(shù)分解來獲得p、q，最終算出d是最好的RSA攻擊方法。若采用推斷（p-1）（q-1）或直接窮舉d則會慢很多。因此實現(xiàn)RSA加密算法的運行速度而且盡可能少耗費資源一直是待解決的問題。

2 并行計算環(huán)境MPI

MPI（Message Passing Interface）是一個消息傳遞編程標(biāo)準(zhǔn)，它是一個全球性質(zhì)的參考標(biāo)準(zhǔn)。MPI的制定整合了幾乎所有消息傳遞系統(tǒng)的優(yōu)點，并在相關(guān)方面做了較大的改進(jìn)和發(fā)展，最終獲得一個為并行程序的開發(fā)使用的平臺。MPI系統(tǒng)是一個由所有具有標(biāo)準(zhǔn)接口說明的消息傳遞函數(shù)所構(gòu)成的函數(shù)庫，MPI標(biāo)準(zhǔn)中定義了一組函數(shù)接口用于進(jìn)程間的消息傳遞，通信的性能對基于消息傳遞的應(yīng)用來說至關(guān)重要，若不全力實現(xiàn)MPI，造成通信開銷會十分昂貴，程序并行將豪無放逐意義。MPI標(biāo)準(zhǔn)的制定僅解決了并行程序的可移性問題，而最為關(guān)鍵的問題是在為MPI實現(xiàn)的高效與否。

針對網(wǎng)絡(luò)中已經(jīng)確定帶寬上限和延遲下限，不同的協(xié)議和API向用戶提供的功能和性能不同。根據(jù)API、協(xié)議，可將帶寬、延遲空間劃分為以下五類：

高延遲/窄帶寬（存在較多拷貝和緩沖的標(biāo)準(zhǔn)TCP/IP協(xié)議棧）

高延遲/中等帶寬（改進(jìn)的TCP/IP協(xié)議棧）

中等延遲/中等帶寬（建立在相對較慢的驅(qū)動之上，采用無拷貝TCP/IP協(xié)議棧的MPI實現(xiàn)，如MPICH）

④ 低延遲/寬帶寬（有硬件支持的優(yōu)化了的MPI實現(xiàn)）

⑤ 超低延遲/窄帶寬（主動消息，遠(yuǎn)程put/get）

在TCP/IP協(xié)議之上無法建立高速的MPI，為了實現(xiàn)MPI的高效，put/get協(xié)議往往會被人們所選擇。

3 RSA加密算法中MPI的應(yīng)用

由于RSA加密算法在實現(xiàn)時有一定的困難，結(jié)合并行計算環(huán)境MPI在并行處理方面的優(yōu)點，提出對RSA加密算法進(jìn)行改進(jìn)，采用基于MPI的消息傳遞系統(tǒng)，實現(xiàn)算法運行的速度以及其安全性的提高。具體改進(jìn)后的RSA算法實現(xiàn)如下：

RSA算法在實現(xiàn)過程中后繼操作基本上都依賴于前一步的運算結(jié)果，因此在實現(xiàn)數(shù)據(jù)交換和通信過程中如果全部采用并行計算，往往導(dǎo)致系統(tǒng)開銷消耗增大，實現(xiàn)起來相對較難，最終影響系統(tǒng)效率。鑒于以上問題在實現(xiàn)過程中建議采用更加實際的局部并行處理方法。即主要對隨機產(chǎn)生質(zhì)數(shù)過程、計算逆元的過程、歐拉函數(shù)的計算以及加密時的大數(shù)取模過程采用并行處理。RSA加密中有兩個關(guān)鍵問題：

1）選定互質(zhì)P和Q

判定素數(shù)，一般定義是：素數(shù)是除了能被1和它本身整除而不能被其他任何數(shù)整除的數(shù)。用2到n-1這些數(shù)去除n，如果所有數(shù)除不盡，即判定n是素數(shù)，否則只要其中有一個數(shù)能整除，即判定n不是素數(shù)。該辦法適用范圍較小，對于判定大素數(shù)來說，則結(jié)果不可取，故對于大數(shù)（超過百位以上的整數(shù)）p和整數(shù)q（q

2）計算逆元

逆元算法：如果ab≡1（modm）， 則稱b是a的模m逆，記作a的模m逆是方程ax≡1（modm）的解，兩個數(shù)互質(zhì)一定有逆元。求逆元可以使用輾轉(zhuǎn)相除法，但是只有兩個數(shù)都是質(zhì)數(shù)的時候才有逆元。逆元計算相對困難，本文計算逆元以歐幾里得算法為例。

#include

voidmain（）

{ Int temp；int a，b；

scanf（"%d"，&a）；

scanf（"%d"，&b）；

printf（"the greatest common factor of%dand%dis"，a，b）；

while（b！=0）

{

temp=b；b=a%b；a=temp；

}

printf（"%d＼n"，a）；

getchar（）；

getchar（）；

}

分析發(fā)現(xiàn)，有4個調(diào)用單元在系統(tǒng)中被確定，通過單元模塊的有效組合來實現(xiàn)系統(tǒng)。建立系統(tǒng)時，為了讓消息傳遞及計算簡便，每一位數(shù)據(jù)存放都采用數(shù)組，每個整型數(shù)組的一位都存放一個需要計算的數(shù)的每一位。以系統(tǒng)模塊中2個隨機大素數(shù)的乘積為例：

在實現(xiàn)大數(shù)相乘時，通過MPI消息傳遞的方式將乘數(shù)和被乘數(shù)發(fā)送給每1個進(jìn)程上，接著設(shè)置1個步長，用于每臺機器在并行計算時計算相應(yīng)位。以ABCD×EFGH為例。

第一階段：初始化

經(jīng)過消息發(fā)送，使得每個進(jìn)程中都存放了乘數(shù)和被乘數(shù)：ABCD及EFGH。

第二階段：計算

設(shè)定MPI步長，步長等于乘數(shù)的位數(shù)/開設(shè)的進(jìn)程數(shù)所得的商。本例為4除以2得2，即步長為2.具體計算過程是：用第1個進(jìn)程與2求模余1的位數(shù)上的數(shù)，第2個進(jìn)程計算與2求模余0的位數(shù)上的數(shù)，單個進(jìn)程單獨計算后得到各自的結(jié)果。

第三階段：匯總

通過MPI消息將單個進(jìn)程的結(jié)果發(fā)送至1號進(jìn)程完成匯總，接著進(jìn)行進(jìn)位的調(diào)整，得到最終結(jié)果。

以下為MPI主要代碼：

MPI_Init（&argc，&argv）； /*MPI初始化*/

MPI_Comm_rank（MPI_COMM_WORLD，&rank）； /* 獲得標(biāo)識*/

MPI_Comm_size（MPI_COMM_WORLD，&size）； /*MPI系統(tǒng)大小*/

If（rank==0）） /* 假設(shè)是0進(jìn)程*/

……

MPI_Barrier（MPI_COMM_WORLD）；

T1=realtime（）；

MPI_Bcast（FirstArray，N*N，MPI_INT，0，MPI_COMM_WORLD）；

MPI_Bcast（SecondArray，N*N，MPI_INT，0，

MPI_COMM_WORLD）；

……

for（j=0；j

for（k=0；k

{

Int myresult，result；

Result=ResultArray[j][k]；

MPI_Reduce（&myresult， &result，1，MPI_INT，MPI_SUM，0，MPI_COMM_WORLD）；

/*反饋計算結(jié)果到1號進(jìn)程*/

ResultArray[j][k]=result；

}

其他幾個功能函數(shù)的設(shè)計思想與上述類似，就是充分利用MPI在多臺機器或多個進(jìn)程中的消息傳遞機制，將本來需要在1臺機器上或1個進(jìn)程上完成的作業(yè)，分發(fā)到多臺機器或多個進(jìn)程中，提高整體加密速度。如圖1所示 算法流程圖。

4 結(jié)論

在現(xiàn)實的工作中，往往需要處理較多的保密數(shù)據(jù)，在網(wǎng)絡(luò)上進(jìn)行傳輸時必須充分考慮其安全性。MPI在為運行并行程序和用戶構(gòu)造時提供了便利的程序開發(fā)平臺，特別是其采用的消息傳遞機制，適應(yīng)于各種同構(gòu)或異構(gòu)網(wǎng)絡(luò)平臺。通過在RSA加密算法中MPI的應(yīng)用，不僅達(dá)到了高效、準(zhǔn)確、安全的數(shù)據(jù)傳輸、數(shù)據(jù)加密等要求，而且對于MPI的數(shù)據(jù)傳送的快速、資源利用率的提高等優(yōu)點也充分得到體現(xiàn)。

參考文獻(xiàn)：

[1] 都志輝.高性能計算并行編程技術(shù)_MPI并行程序設(shè)計[M].北京：清華大學(xué)出版社，2001.

[2] 韓健，張樂，蔡瑞英.計算環(huán)境MPI在RSA加密中的應(yīng)用[J]. 南京工業(yè)大學(xué)學(xué)報，2003，3：49-51，61.

[3] 黃光明.基于DES_RSA加密算法的改進(jìn)與實現(xiàn)[D].東北師范大學(xué)，2013.

[4] 吳明航.DES和RSA混合加密算法的研究[D].哈爾濱工業(yè)大學(xué)，2013.

[5] 高雪寒.大數(shù)相除快速算法在RSA中的應(yīng)用與研究[D].陜西師范大學(xué)，2014.

[6] 賀令亞.RSA加密算法的研究與實現(xiàn)[D].中南大學(xué)，2009.

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