并行計(jì)算就是使用多計(jì)算機(jī)或多處理機(jī)的計(jì)算機(jī)來(lái)求解問(wèn)題，它要比使用一臺(tái)計(jì)算機(jī)的計(jì)算速度快很多，同時(shí)并行計(jì)算為求解巨大規(guī)模的問(wèn)題提供了機(jī)會(huì)，因?yàn)檫@些大規(guī)模的問(wèn)題所往往需要更多的計(jì)算步驟和更大的存儲(chǔ)容量，正是多計(jì)算機(jī)或多處理機(jī)系統(tǒng)所擁有的。為了實(shí)現(xiàn)消息傳遞并行計(jì)算，現(xiàn)在存在幾種方案或特定系統(tǒng)，其中比較流行的就是PVM（并行虛擬機(jī)）和MPI（消息傳遞接口）。 MPI是提倡的消息傳遞并行程序設(shè)計(jì)的標(biāo)準(zhǔn)之一，MPI2．O規(guī)范除支持消息傳遞外，還支持MPI的IIO規(guī)范和進(jìn)程管理規(guī)范，加上其擁有移植性好，效率高，功能強(qiáng)等諸多優(yōu)點(diǎn)，因此MPI正成為并行程序設(shè)計(jì)事實(shí)上的工業(yè)標(biāo)準(zhǔn)。

偽隨機(jī)信號(hào)既有隨機(jī)信號(hào)所具有優(yōu)良的相關(guān)性，又有隨機(jī)信號(hào)所不具備的規(guī)律性。這兩個(gè)特點(diǎn)，使得它既易于從干擾信號(hào)中被識(shí)別和分離出來(lái)，又可以方便的產(chǎn)生和重復(fù)，因此偽隨機(jī)序列在密碼學(xué)、通信、雷達(dá)、導(dǎo)航等方面均有廣泛的應(yīng)用。目前由于網(wǎng)絡(luò)的發(fā)展極為迅速，網(wǎng)絡(luò)安全成為復(fù)雜而龐大的問(wèn)題，雖然DES、RSA和數(shù)字簽名等加密技術(shù)部分解決了當(dāng)前的安全需求，但它們均存在并行度不足，沒(méi)有充分利用網(wǎng)絡(luò)的優(yōu)勢(shì)等缺點(diǎn)。因此，我們對(duì)基于M PI的偽隨機(jī)序列并行加密算法進(jìn)行探討，研究如何利用MPI實(shí)現(xiàn)偽隨機(jī)序列的并行產(chǎn)生或加密，為密碼學(xué)的研究提供一種新的方向。

一、MPI簡(jiǎn)介

1、MPI的定義

對(duì)MPI的定義是多種多樣，但不外乎下面3個(gè)方面，它們限定了MPI的內(nèi)涵和外延：

(1)MPI是一個(gè)庫(kù)，而不是一門語(yǔ)言。許多人認(rèn)為MPI是一種并行語(yǔ)言，這是不準(zhǔn)確的。但是按照并行語(yǔ)言的分類，可把FORTRAN+MPI或C+MPI看做是一種在原來(lái)串行語(yǔ)言基礎(chǔ)之上擴(kuò)展后得到的并行語(yǔ)言oMPI庫(kù)可以被FORT RAN77/C/Fortran90/C++調(diào)用，從語(yǔ)法上說(shuō)，它遵守所有對(duì)庫(kù)函數(shù)或過(guò)程的調(diào)用規(guī)則，與一般的函數(shù)或過(guò)程沒(méi)有區(qū)別。

(2)MPI是一種標(biāo)準(zhǔn)或規(guī)范的代表，而不是特指某一個(gè)對(duì)它的具體實(shí)現(xiàn)。迄今為止，所有的并行計(jì)算機(jī)制造商都提供對(duì)MPI的支持，可以在網(wǎng)上免費(fèi)得到MPI在不同并行計(jì)算機(jī)上的實(shí)現(xiàn)，一個(gè)正確的MPI程序可以不加修改地在所有的并行機(jī)上運(yùn)行。

(3)MPI是一種消息傳遞編程模型，并成為這種編程模型的代表和事實(shí)上的標(biāo)準(zhǔn)。MPI雖然很龐大，但是它的最終目的是服務(wù)于進(jìn)程間的通信。

2、MPI的實(shí)現(xiàn)

MPI的實(shí)現(xiàn)包括MPICH、LAM、IBM MPL等多個(gè)版本，最常用和穩(wěn)定的是MPICH。MPICH含三層結(jié)構(gòu)，最上層是MPI的API，基本是點(diǎn)到點(diǎn)通信和在點(diǎn)到點(diǎn)通信基礎(chǔ)上構(gòu)造的集群通信(Collective Communication)；中間層是ADI(Abstract Device InteIface)層，其中device可以簡(jiǎn)單地理解為某一種底層通信庫(kù)，ADI是對(duì)各種不同的底層通信庫(kù)的不同接口的統(tǒng)一標(biāo)準(zhǔn)；底層是具體的底層通信庫(kù)oMPICH的1.0.12版本以下都采用第一代ADI接口的實(shí)現(xiàn)方法，利用底層d evice提供的通信原語(yǔ)和有關(guān)服務(wù)函數(shù)實(shí)現(xiàn)所有的ADI接口，可以直接實(shí)現(xiàn)，也可以依靠一定的模板間接實(shí)現(xiàn)。自1.0.13版本開始，MPICH采用第二代ADI接口。

3、MPI的通信模式

MPI共有四種通信模式：標(biāo)準(zhǔn)通信模式(standard mode)，緩存通信模式(bufferedmode)，同步通信模式（synchronous- mode）和就緒通信模式（ready- mode）。這幾種通信模式對(duì)應(yīng)于不同的通信需求，MPI為用戶提供功能相近的不同通信方式，為用戶編寫高效的并行程序提供了可能。這幾種通信模式主要是根據(jù)以下不同的情況來(lái)區(qū)分的：

①是否需要對(duì)發(fā)送的數(shù)據(jù)進(jìn)行緩存？

②是否只有當(dāng)接收調(diào)用執(zhí)行后才可執(zhí)行發(fā)送操作？

③什么時(shí)候發(fā)送調(diào)用可正確返回？

④發(fā)送調(diào)用正確返回是否意味著發(fā)送已完成？即發(fā)送緩沖區(qū)是否可被覆蓋？

發(fā)送數(shù)據(jù)是否已到達(dá)接收緩沖區(qū)？針對(duì)這些不同的情況，MPI給出了不同的通信模式。

從表中可以看出，對(duì)于非標(biāo)準(zhǔn)的通信模式，只有發(fā)送操作，而沒(méi)有相應(yīng)的接收操作。MPI對(duì)不同的通信模式，在調(diào)用的命名上就區(qū)別開來(lái)，標(biāo)準(zhǔn)通信模式不加特殊的字母，而對(duì)其他三個(gè)通信模式提供三個(gè)附加的發(fā)送函數(shù)，用一個(gè)字母前綴表示通信模式：B用于緩存通信模式，S用于同步通信模式，R用于就緒通信模式。

在MPI采用標(biāo)準(zhǔn)通信模式時(shí)，是否對(duì)發(fā)送的數(shù)據(jù)進(jìn)行緩存是由MPI自身決定，而不是由并行程序員來(lái)控制的；當(dāng)用患對(duì)標(biāo)準(zhǔn)通信模式不滿意，希望直接對(duì)通信緩沖區(qū)進(jìn)行控制時(shí)可采用緩存通信模式；同步通信模式的開始不依賴于接收進(jìn)程相應(yīng)的接收操作是否已經(jīng)啟動(dòng)，但是同步發(fā)送卻必須等到相應(yīng)的接收進(jìn)程開始后才可以正確返回。因此，同步發(fā)送返回后，意味著發(fā)送緩沖區(qū)中的數(shù)據(jù)已經(jīng)全部被系統(tǒng)緩沖區(qū)緩存，并且已經(jīng)開始發(fā)送，這樣當(dāng)同步發(fā)送返回后，發(fā)送緩沖區(qū)可以被釋放或重新使用；在就緒通信模式中，只有當(dāng)接收進(jìn)程的接收操作已經(jīng)啟動(dòng)時(shí)，才可以在發(fā)送進(jìn)程啟動(dòng)發(fā)送操作，否則，當(dāng)發(fā)送操作啟動(dòng)而相應(yīng)的接收還沒(méi)有啟動(dòng)時(shí)，發(fā)送操作將出錯(cuò)。對(duì)于非阻塞發(fā)送操作的正確返回，并不意味著發(fā)送己完成，但對(duì)于阻塞發(fā)送的正確返回，則發(fā)送緩沖區(qū)可以重復(fù)使用。具體采用何種模式，就要根據(jù)實(shí)際的需要，因地制宜，才能取得最佳的優(yōu)化和高效的結(jié)果。

二、偽隨機(jī)序列并行加密算法

在香農(nóng)證明了一次一密的密碼體制是不可破的之后，這一結(jié)果大大的刺激了密碼學(xué)的研究。若能以一種方式產(chǎn)生一偽隨機(jī)序列，則利用這樣的序列就可進(jìn)行加密，這就是序列密碼體制。序列密碼的加密過(guò)程是先把報(bào)文、語(yǔ)音、圖像和數(shù)據(jù)等原始明文轉(zhuǎn)換成明文數(shù)據(jù)序列，然后將它同密鑰序列進(jìn)行逐位加密生成密文序列發(fā)送給接收者。接收者用相同的密鑰序列對(duì)密文序列進(jìn)行解密來(lái)恢復(fù)明文序列。序列密碼不存在數(shù)據(jù)擴(kuò)展和錯(cuò)誤傳播，實(shí)時(shí)性好，加密、解密容易，是一種廣泛應(yīng)用的密碼系統(tǒng)，在密碼學(xué)理論和應(yīng)用中一直占重要地位。

密鑰流產(chǎn)生器實(shí)際上是一個(gè)算法，產(chǎn)生的密鑰流通常是0~1數(shù)據(jù)流，因此稱為流碼。密鑰流具有周期性，而且周期應(yīng)盡可能的大，至少要和明文相等，并且具有隨機(jī)性，是密碼分析對(duì)它無(wú)法預(yù)測(cè)。為了使序列密碼達(dá)到要求的安全保密性，密鑰序列應(yīng)具有偽隨機(jī)性準(zhǔn)則：

①序列周期充分長(zhǎng)，通常不小于1016bit；

②良好的隨機(jī)統(tǒng)計(jì)特性，即序列中每位接近均勻分布；

③序列線性不可預(yù)測(cè)性充分大。

目前比較常用的偽隨機(jī)序列并行算法有兩種：n級(jí)線性反饋移位寄存器( LFSR)偽隨機(jī)序列的并行算法和組合前饋網(wǎng)絡(luò)偽隨機(jī)序列的并行算法。我們分別介紹如下。

1、n級(jí)線性反饋移位寄存器

（1）反饋移位寄存器

一般的反饋移位寄存器的基本結(jié)構(gòu)如圖2所示。

圖2可以看成是一個(gè)r級(jí)反饋移位寄存器，它由串聯(lián)的n個(gè)二元移位寄存器及一個(gè)開關(guān)網(wǎng)絡(luò)構(gòu)成，其中aj-1，aj-2，...，aj-r分別是第1級(jí)，第2級(jí)，..2，第r級(jí)寄存器。每個(gè)二元寄存器是一個(gè)雙穩(wěn)態(tài)觸發(fā)器，它的兩種狀態(tài)分別記為“O”和“1’’，每個(gè)觸發(fā)器看成一級(jí)。開關(guān)網(wǎng)絡(luò)是具有r個(gè)輸入端和一個(gè)輸出端的組合門電路，它可由含有r個(gè)邏輯變?cè)獂1，X2，...，Xr的布爾函數(shù)：Xr+ 1=f（x1，X2，...，Xr）來(lái)表示，這個(gè)函數(shù)稱為該組合門電路的反饋邏輯函數(shù)。反饋邏輯函數(shù)在反饋移位寄存器中起決定作用，它是由r個(gè)邏輯變?cè)ㄟ^(guò)“與”、“或”、“非’’、“模2加”等邏輯運(yùn)算連接起來(lái)的關(guān)系式。

（2）線性反饋移位寄存器(LFSR)

如果用n元布爾函數(shù)f(x1，X2，...，Xn)可以表示為n個(gè)變?cè)獂1，X2，...，Xn的線性齊次函數(shù)f(x1，X2，...，Xn)=c1xn+C2Xn-1+…+CnX1，其中C1=O或1，則以f(x1，X2，...，Xn)為反饋的移位寄存器稱為線性反饋移位寄存器。圖3是一個(gè)n級(jí)線性反饋移位寄存器，與反饋移位寄存器類似，它由串聯(lián)的n個(gè)二元移位寄存器及一個(gè)開關(guān)網(wǎng)絡(luò)構(gòu)成其中ai+n-1，ai+n-2，...，ai分別是第1級(jí)第2極，...，第n級(jí)寄存器。

多項(xiàng)式f(x1，X2，...，Xn)=co+cixn-1，...，CnX(co=ci=1)稱為L(zhǎng)FSR的連接多項(xiàng)式。當(dāng)一級(jí)線性移位寄存器產(chǎn)生的序列周期長(zhǎng)度為2n—1時(shí)，這個(gè)序列成為m序列。

2、組合前饋網(wǎng)絡(luò)

用前饋序列能產(chǎn)生具有良好統(tǒng)計(jì)特性的序列，它通過(guò)一個(gè)或多個(gè)m序列加上一個(gè)非線性前饋網(wǎng)絡(luò)來(lái)產(chǎn)生具有周期長(zhǎng)、隨機(jī)統(tǒng)計(jì)特性好、線性復(fù)雜度較高的序列。一般的組合前饋序列產(chǎn)生器如圖4。

其中{a1i}，{a2i}，...，{ani}的級(jí)數(shù)分別為n1，n2，...，nn的m序列，f(X1，X2，....，Xn) 為n元非線性組合函數(shù)，序列{bi}為b=f(a1i，a2i，...，ani)，稱{bi}為由序列{ aii}，{a2i}， …，{ani}及廠產(chǎn)生的組合前饋序列，f稱為組合函數(shù)。

三、加密算法實(shí)現(xiàn)

現(xiàn)在我們就用MPI在SIMD-CREW模型上實(shí)現(xiàn)n級(jí)線性反饋移位寄存器(LFSR)做個(gè)說(shuō)明。具體步驟：

(1)以管理員的身份登錄每臺(tái)主機(jī)，在所有主機(jī)上建立一個(gè)同樣的賬戶（當(dāng)然也可以每個(gè)機(jī)器使用不同的用戶名和賬戶，然后建立—個(gè)配置文件，使用命令行的方式運(yùn)行程序），然后，運(yùn)行下載的安莓享件，將MPICH安裝到每臺(tái)主機(jī)上。

(2)安裝好MPICHIJ之后，就對(duì)每臺(tái)計(jì)算機(jī)進(jìn)行注冊(cè)和配置。其中注冊(cè)必須每臺(tái)計(jì)算機(jī)都要進(jìn)行，配置只要在主控的計(jì)算機(jī)執(zhí)行就行了。注冊(cè)的目的是將先前在每臺(tái)計(jì)算機(jī)上申請(qǐng)的賬號(hào)與密碼注冊(cè)到M PICH中去，這樣M PICH才能在網(wǎng)絡(luò)環(huán)境中訪問(wèn)每臺(tái)主機(jī)。

(3)運(yùn)行MPICH提供的配置程序“M PICH Configuration toor”來(lái)配置主控機(jī)，使其能訪問(wèn)其他計(jì)算機(jī)，并讓程序能在各臺(tái)計(jì)算機(jī)上執(zhí)行。

(4)將MPICH與編譯環(huán)境整合起來(lái)。

(5)算法描述。其中n是2的冪，當(dāng)前各存儲(chǔ)器的值存儲(chǔ)于數(shù)組A[]中，連接多項(xiàng)式的系數(shù)存儲(chǔ)于數(shù)組C[]，數(shù)組B[]是輔存。以各寄存器為結(jié)點(diǎn)構(gòu)造平衡二叉樹，從葉子結(jié)點(diǎn)向根結(jié)點(diǎn)遍歷，計(jì)算反饋輸出值。

輸入：各寄存器的初值

輸出：偽隨機(jī)m序列

MPI_ Init(＆ar gc,&argv);

MPL Comm - rank(MPI_ COMM_ WORLD,

＆rank)；//當(dāng)前進(jìn)程標(biāo)識(shí)

M PI_ Comm_ size(MPI_ COM M_ WORLD,＆size);

//通信域中的進(jìn)程個(gè)數(shù)

MPL Get-processor_ name (processor_ name ＆namelen)；

for(i_1；i<=n；i++)

{ if( rank==i)

B[O，i]=A[i]&C[i]；

｝

for(h= 1; h<= log(n)/log(2);h++)

//求級(jí)聯(lián)多項(xiàng)式的值

for(i= 1;i<=n/pow(2,h);i++)

{if( rank==i)

B[ h,i]=B[h,2i- 1]^B[ h-1,2i];

}

for(i_1；i<=n；i++)

{if(rank==i)

A[i-1]=A[i]；//移位寄存器移一位

}

A[n]=B[log(n)/log(2),1];

A[o]=B[log(n)/log(2),1];

MPI_ Finalize()；

(6)加密算法復(fù)雜度分析。該算法在實(shí)現(xiàn)n級(jí)LFSR時(shí)使用孔個(gè)處理器在O(lg(n))時(shí)產(chǎn)生序列的—位。如果加密序列的長(zhǎng)度為w，那么該算法復(fù)雜度為O（Wl(n)），而串行算法需要O(wn)的時(shí)間，理論上如果處理器越多，偽隨機(jī)序列并行算法將越有效。

admin

收藏 海報(bào)分享