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

陸玉陽(yáng)

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

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

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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)中的一個(gè)典型，其應(yīng)用最為廣泛，RSA加密算法既可加密，也可用于數(shù)字簽名。RSA加密算法在進(jìn)行復(fù)雜判斷和大數(shù)運(yùn)算時(shí)，計(jì)算時(shí)間往往花費(fèi)較多，對(duì)計(jì)算機(jī)的運(yùn)行速度、存儲(chǔ)容量等方面具有較高的要求，針對(duì)RSA加密算法的運(yùn)行速度而且盡可能少耗費(fèi)資源一直是密碼學(xué)領(lǐng)域研究的熱點(diǎn)問題。

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

1 RSA加密算法

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

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

②p*q=n；

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

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

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

⑥刪除p和q；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2）計(jì)算逆元

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

#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個(gè)調(diào)用單元在系統(tǒng)中被確定，通過單元模塊的有效組合來(lái)實(shí)現(xiàn)系統(tǒng)。建立系統(tǒng)時(shí)，為了讓消息傳遞及計(jì)算簡(jiǎn)便，每一位數(shù)據(jù)存放都采用數(shù)組，每個(gè)整型數(shù)組的一位都存放一個(gè)需要計(jì)算的數(shù)的每一位。以系統(tǒng)模塊中2個(gè)隨機(jī)大素?cái)?shù)的乘積為例：

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

第一階段：初始化

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

第二階段：計(jì)算

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

第三階段：匯總

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

以下為MPI主要代碼：

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

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

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）；

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

ResultArray[j][k]=result；

}

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

4 結(jié)論

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

參考文獻(xiàn)：

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

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

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

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

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

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

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