◆程雨芊

（山東大學(xué)（威海）網(wǎng)絡(luò)與信息管理中心 山東 264200）

基于并行編程模型的SPECK 2n算法實(shí)現(xiàn)與優(yōu)化

◆程雨芊

（山東大學(xué)（威海）網(wǎng)絡(luò)與信息管理中心 山東 264200）

SPECK 2n算法是一種典型的輕量級分組密碼算法，具有較強(qiáng)的靈活性和安全性，廣泛應(yīng)用于數(shù)據(jù)加密，以保證數(shù)據(jù)的完整性和可靠性。為了應(yīng)對大數(shù)據(jù)的加密，本文提出一種基于 MPI+OpenMP的混合并行編程模型，可以充分利用分布式存儲模型和共享存儲模型的特點(diǎn)來優(yōu)化加密過程，并基于山東大學(xué)（威海）超級計(jì)算中心集群進(jìn)行測試。實(shí)驗(yàn)結(jié)果表明，優(yōu)化后的并行SPECK 2n算法達(dá)到了較高的加速比，能夠有效處理大數(shù)據(jù)量的實(shí)時加密，極大地提高了計(jì)算效率。

并行編程；密碼算法；分布式存儲模型；共享存儲模型

0 引言

SPECK 2n系列密碼算法是由美國國家安全局（NSA）設(shè)計(jì)，在 2013年發(fā)布的具有 Feistel結(jié)構(gòu)的輕量級分組密碼算法[1]。SPECK系列分組密碼算法的分組長度為32、48、64、96或128比特，密鑰長度為64、72、96、128、144、192或256比特，即分組長度和密鑰長度可變，有利于在不同的軟件平臺上實(shí)現(xiàn)，具有很強(qiáng)的應(yīng)用靈活性。同時 SPECK算法有較強(qiáng)的安全性，雖然針對 SPECK系列密碼算法已經(jīng)有了一些安全性分析結(jié)果，如Farzaneh Abed等人提出的飛去來器攻擊和矩形攻擊[2]、Alex Biryukov等人提出的差分攻擊[3]以及由Itai Dinur改進(jìn)的差分攻擊[4]等，但目前還沒有全輪數(shù)的SPECK算法安全性分析。

在大數(shù)據(jù)快速發(fā)展的形勢下，如何保證大數(shù)據(jù)的安全性和可靠性，是很多數(shù)據(jù)型企業(yè)所關(guān)心的問題。SPECK 2n算法作為輕量級的分組密碼算法，主要用于對數(shù)據(jù)的快速實(shí)時加密，對加密的效率有一定的要求，因此并行化的SPECK 2n算法實(shí)現(xiàn)逐漸受到重視。

高性能計(jì)算作為一個新興科學(xué)，致力于研究高效能的并行計(jì)算，對于科學(xué)實(shí)驗(yàn)?zāi)M計(jì)算和大數(shù)據(jù)分析等起到了推動作用。利用高性能計(jì)算可以提高計(jì)算效率，節(jié)約時間和資源，滿足大數(shù)據(jù)環(huán)境下的計(jì)算需求。高性能計(jì)算的實(shí)現(xiàn)方式主要有兩種，一種是充分利用CPU本身的資源進(jìn)行并行計(jì)算，如OpenMP多線程并行、MPI多進(jìn)程并行等；另一種是利用加速卡進(jìn)行輔助計(jì)算，如NVIDIA公司的GPU加速卡和Intel公司的MIC加速卡等。

本文提出一種基于MPI+OpenMP并行編程模型的SPECK 2n算法實(shí)現(xiàn)，將待加密的明文數(shù)據(jù)進(jìn)行分塊，然后使用MPI進(jìn)程并行和OpenMP線程并行嵌套完成加密算法。經(jīng)實(shí)驗(yàn)驗(yàn)證，將多進(jìn)程并行與多線程并行結(jié)合起來的層次化并行方法能夠取得較好的加密效率。

1 并行編程模型介紹

并行編程模型根據(jù)內(nèi)存模型的不同，主要分為共享存儲模型和分布式存儲模型兩種。共享存儲的并行編程模型具有單一內(nèi)存地址、易編程、可擴(kuò)展性較差等特點(diǎn)，適合中小規(guī)模的計(jì)算，主要實(shí)現(xiàn)的方式有OpenMP、PThread、X3H5等；分布式存儲的并行編程模型又稱為消息傳遞模型，具有地址空間獨(dú)立、編程復(fù)雜、可擴(kuò)展性較好等特點(diǎn)，適合大規(guī)模的并行計(jì)算，主要的實(shí)現(xiàn)方式有MPI、PVM等。消息傳遞模型與多線程編程模型組合而成的混合編程模型更適用于大數(shù)據(jù)環(huán)境下的多層次、可擴(kuò)展的并行算法[5-6]。

MPI消息傳遞模型適合并行計(jì)算粒度大的算法，要求用戶適當(dāng)?shù)胤纸庥?jì)算數(shù)據(jù)，不同的節(jié)點(diǎn)之間可以進(jìn)行靈活地進(jìn)行數(shù)據(jù)交換。MPI主要使用函數(shù)接口實(shí)現(xiàn)并行環(huán)境初始化以及消息傳遞等功能。OpenMP多線程編程模型適合細(xì)粒度的并行算法，利用編譯指導(dǎo)語句#pragma實(shí)現(xiàn)線程的Fork-Join以及參量的屬性設(shè)置，共享的內(nèi)存可以避免不必要的數(shù)據(jù)交換，提高算法的執(zhí)行效率。因此 MPI+OpenMP并行編程模型能夠同時結(jié)合分布式存儲和共享存儲的優(yōu)勢，充分利用計(jì)算集群的節(jié)點(diǎn)間和節(jié)點(diǎn)內(nèi)的兩級并行來進(jìn)行算法實(shí)現(xiàn)。

2 SPECK 2n算法

2.1 SPECK 2n算法介紹

SPECK 2n系列密碼算法是由Ray Beaulieu等人在2013年提出的一種輕量級分組密碼算法，密鑰長度和分組長度均不固定，可以根據(jù)具體的安全性要求、性能要求以及應(yīng)用環(huán)境等來選擇合適的分組長度和密鑰長度。SPECK 2n系列密碼算法的十個典型實(shí)例算法如表1，其中n表示字長，單位為比特（bit），m表示主密鑰的字?jǐn)?shù)，α和β表示循環(huán)移位的參量，T為加密的輪數(shù)；分組長度即為輸入明文和輸出密文的比特?cái)?shù)，密鑰長度為主密鑰的比特?cái)?shù)，α、β和T是加密算法函數(shù)中的參數(shù)。

表1 SPECK 2n算法的參數(shù)設(shè)置

SPECK 2n算法主要包括兩個部分：加密主函數(shù)和密鑰擴(kuò)展函數(shù)。加密主函數(shù)用來進(jìn)行明文的加密操作，輸出相應(yīng)的密文；密鑰擴(kuò)展函數(shù)將輸入的主密鑰擴(kuò)展成T個輪密鑰，用于主函數(shù)運(yùn)算。加密主函數(shù)由T輪的輪函數(shù)組成，SPECK 2n算法的輪函數(shù)主要由循環(huán)移位操作、異或運(yùn)算和域上的模加運(yùn)算組成，第i輪加密函數(shù)為：

其中Xi和Yi是第i輪加密的輸入分組，Xi+1和Yi+1是第i輪加密的輸出分組，Ki表示第i輪的子密鑰，長度均為n比特；>>>和<<<表示按比特位的循環(huán)右移和循環(huán)左移，表示域上的加法運(yùn)⊕算， 表示按比特位的異或操作。

SPECK 2n系列密碼算法的密鑰擴(kuò)展函數(shù)利用輪函數(shù)來生成輪密鑰，輸入為主密鑰輸出為T個輪密鑰用于每一輪的加密運(yùn)算。對于所有的計(jì)算ki和li的公式如下：

2.2 并行SPECK 2n算法的基本原理

根據(jù)SPECK 2n算法的輪函數(shù)結(jié)構(gòu)可以看出，SPECK 2n算法先將數(shù)據(jù)進(jìn)行分塊，然后每個數(shù)據(jù)塊分別進(jìn)行對應(yīng)輪數(shù)的加密計(jì)算，除了對密鑰擴(kuò)展函數(shù)、主密鑰和輪密鑰比特進(jìn)行讀取外，各個數(shù)據(jù)塊間的加密操作互不影響，加密順序也無依賴性。因此，對于密鑰相同的待加密數(shù)據(jù)，可以進(jìn)行節(jié)點(diǎn)內(nèi)的并行加密運(yùn)算；對于密鑰不同的待加密數(shù)據(jù)，可以進(jìn)行節(jié)點(diǎn)間的并行加密運(yùn)算。

3 基于并行編程模型的SPECK 2n算法

單機(jī)環(huán)境下，串行的SPECK 2n算法主要采用迭代方式實(shí)現(xiàn)，多次讀取更新密鑰比特來進(jìn)行不同密鑰的明文數(shù)據(jù)的加密計(jì)算。算法計(jì)算的核心內(nèi)容是輪函數(shù)的實(shí)現(xiàn)，對于所有明文數(shù)據(jù)分組，進(jìn)行T輪的計(jì)算，得到密文數(shù)據(jù)分組。本文采用MPI分布式存儲模型優(yōu)化數(shù)據(jù)分塊和輪函數(shù)，進(jìn)而再結(jié)合OpenMP共享存儲模型進(jìn)一步改進(jìn)SPECK算法。

3.1 基于MPI的并行SPECK 2n算法

根據(jù)SPECK 2n算法輪函數(shù)的特點(diǎn)，基于MPI的并行SPECK算法實(shí)現(xiàn)主要對輸入數(shù)據(jù)進(jìn)行分塊處理，由主進(jìn)程進(jìn)行整體的邏輯控制，開啟多個進(jìn)程并發(fā)執(zhí)行每個數(shù)據(jù)分組的輪函數(shù)計(jì)算。相同密鑰的數(shù)據(jù)加密算法分為兩個部分：第一部分是根據(jù)主密鑰生成輪密鑰，第二部分是使用輪密鑰進(jìn)行數(shù)據(jù)加密。每一部分?jǐn)?shù)據(jù)加密完成后，要將明文和密文數(shù)據(jù)對應(yīng)輸出到文件，以便于進(jìn)行算法結(jié)果的驗(yàn)證。

3.2 基于MPI+OpenMP的并行SPECK 2n算法

在上述基于MPI并行的SPECK 2n算法的基礎(chǔ)之上，當(dāng)同一密鑰加密的數(shù)據(jù)量很大時，可以構(gòu)建基于MPI和OpenMP的混合編程模型，同時實(shí)現(xiàn)多進(jìn)程和多線程的編程。每個MPI進(jìn)程內(nèi)部發(fā)散出多個線程，同時對多個數(shù)據(jù)分組進(jìn)行重復(fù)的輪函數(shù)運(yùn)算，可以極大地提高計(jì)算效率。

計(jì)算數(shù)據(jù)分塊的主要依據(jù)是加密所使用的密鑰和SPECK 2n實(shí)例算法的字長等參量，對于不同密鑰加密的數(shù)據(jù)，可以采用MPI多進(jìn)程并行的方式；對于同一密鑰加密的數(shù)據(jù)，可以采用OpenMP多線程并行，減少密鑰交換次數(shù)和密鑰擴(kuò)展函數(shù)的使用次數(shù)。

4 測試環(huán)境與結(jié)果分析

4.1 測試環(huán)境介紹

山東大學(xué)（威海）超級計(jì)算中心集群采用 CPU+GPU+MIC 的三重異構(gòu)架構(gòu)，計(jì)算節(jié)點(diǎn)+胖節(jié)點(diǎn)混合的體系結(jié)構(gòu)。配置了1臺管理節(jié)點(diǎn)和1臺登錄節(jié)點(diǎn)。計(jì)算資源包括34臺CPU計(jì)算節(jié)點(diǎn)、1臺胖節(jié)點(diǎn)、2臺GPU節(jié)點(diǎn)和2臺MIC節(jié)點(diǎn)。集群總計(jì)856個CPU計(jì)算核心，CPU的計(jì)算能力為32Tflops（每秒計(jì)算32萬億次）， 2臺GPU節(jié)點(diǎn)計(jì)算能力為4.6Tflops，2臺MIC節(jié)點(diǎn)計(jì)算能力為4.8Tflops。集群使用了全互連無阻塞的Infiniband 56Gb FDR高速計(jì)算網(wǎng)絡(luò)和千兆的高速管理和監(jiān)控網(wǎng)絡(luò)。采用了lustre并行文件系統(tǒng)，并行存儲裸容量為200TB。

在此計(jì)算平臺上，使用 CPU計(jì)算節(jié)點(diǎn)進(jìn)行實(shí)驗(yàn)測試。每個CPU節(jié)點(diǎn)包含1個Intel(R) Xeon(R) CPU E5-2660 v3 @ 2.60GHz處理器（20個邏輯CPU），操作系統(tǒng)版本為Red Hat Enterprise Linux Server release 6.5，已配置好MPI和OpenMP的并行環(huán)境，編譯器為icpc version 15.0.1和impi 5.0.2.044，程序采用C++語言編寫，每個節(jié)點(diǎn)啟動一個MPI進(jìn)程，每個MPI進(jìn)程在OpenMP并行區(qū)域內(nèi)最多啟用8個OpenMP線程組。

4.2 測試結(jié)果與分析

通過對串行算法（SPECK）、基于 MPI的并行算法（MPI-SPECK）、基于 MPI+OpenMP的并行算法（MPI/OpenMP-SPECK）三種算法實(shí)現(xiàn)的性能進(jìn)行比較，來分析多層次并行加密計(jì)算的優(yōu)勢和效率。

實(shí)驗(yàn)確定以SPECK 32/64算法為例進(jìn)行測試分析，對應(yīng)的參量α和β值為7和2，輪數(shù)T為22，選取了三組不同的輸入明文數(shù)據(jù)量，分別為2MB、32MB和512MB，每組進(jìn)行7種實(shí)驗(yàn)，使用的CPU節(jié)點(diǎn)數(shù)目為單節(jié)點(diǎn)、4節(jié)點(diǎn)和8節(jié)點(diǎn)，實(shí)驗(yàn)的詳細(xì)說明如表2所列：

表2 實(shí)驗(yàn)詳細(xì)說明

實(shí)驗(yàn)對算法運(yùn)行時間進(jìn)行了記錄，結(jié)果如表3所列。

表3 算法運(yùn)行時間（單位：s）

加速比是衡量算法并行化性能和效果的標(biāo)準(zhǔn)，加速比指的是同一個算法在單處理器系統(tǒng)和并行處理器系統(tǒng)中運(yùn)行所消耗的時間的比率。根據(jù)表3列出的運(yùn)行時間，可以計(jì)算出三種數(shù)據(jù)量對應(yīng)的不同編程模型的加速比，結(jié)果如圖1所示。

對不同數(shù)據(jù)量的明文進(jìn)行加密測試實(shí)驗(yàn)表明，并行編程的加速比優(yōu)勢十分明顯。從圖1可以看出，基于MPI并行模型的計(jì)算時間較基于MIP+OpenMP混合并行模型的計(jì)算時間略高，這是由于算法實(shí)現(xiàn)中存在部分共享常量，使用OpenMP多線程并行可以避免不必要的數(shù)據(jù)交換，提高執(zhí)行效率。

圖1 運(yùn)行時間的加速比

5 結(jié)束語

本文實(shí)現(xiàn)了基于MPI+OpenMP的并行SPECK 2n算法，并通過多種實(shí)驗(yàn)驗(yàn)證，基于混合編程模型的算法實(shí)現(xiàn)具有較高的加速比，能夠充分結(jié)合分布式存儲和共享存儲的優(yōu)勢，提高計(jì)算效率。但同時層次化的并行編程模型也存在著一些問題，比如OpenMP線程在 Fork-Join時產(chǎn)生的系統(tǒng)開銷問題、MPI進(jìn)程間的數(shù)據(jù)傳輸優(yōu)化問題等。最后，感謝山東大學(xué)（威海）超級計(jì)算中心的計(jì)算支持和幫助。

[1]Ray Beaulieu, Douglas Shors, Jason Smith, etc. The SIMON and SPECK Families of Lightweight Block Ciphers[R].Cryptology ePrint Archive, 2013, Report 2013/404:http://eprint.iacr.org/.

[2]Farzaneh Abed, Eik List, Jakob Wenzel, etc. Differential Cryptanalysis of round-reduced Simon and Speck[R]. Fast Software Encryption，2015.

[3]Alex Biryukov, Arnab Roy, and Vesselin Velichkov.Differential Analysis of Block Ciphers SIMON and SPECK[R].Fast Software Encryption，2015.

[4]Itai Dinur. Improved Differential Cryptanalysis of Round-Reduced Speck[R]. Selected Areas in Cryptography-SAC 2014.

[5]唐兵,Laurent BOBELIN,賀海武.基于 MPI和 OpenMP混合編程的非負(fù)矩陣分解并行算法[J].計(jì)算機(jī)科學(xué)，2017.

[6]馮云,周淑秋.MPI+OpenMP混合并行編程模型應(yīng)用研究[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2006.

[7]宋鵬，解闖，李金山等.基于 MPI+OpenMP的三維聲波方程正演模擬[J].中國海洋大學(xué)學(xué)報(bào)自然科學(xué)版，2015.

[8]周文.基于眾核架構(gòu)的 BP神經(jīng)網(wǎng)絡(luò)算法優(yōu)化[J].電子世界，2017.