基于 GPU的 M D6算法快速實現(xiàn)

李立新,葉 劍,余 洋

(信息工程大學(xué)電子技術(shù)學(xué)院,鄭州 450004)

基于 GPU的 M D6算法快速實現(xiàn)

李立新,葉 劍,余 洋

(信息工程大學(xué)電子技術(shù)學(xué)院,鄭州 450004)

安全散列算法(SHA)已經(jīng)被廣泛地應(yīng)用于電子商務(wù)等信息安全領(lǐng)域.為了滿足安全散列算法計算速度的需要,本文通過對SHA-3算法的候選算法——MD 6算法的并行性分析,在 GPU平臺上快速實現(xiàn)了 MD 6算法,其最快實現(xiàn)速度是 CPU速度的 5倍,為快速高效的實現(xiàn)安全散列算法提供了有效的途徑.

圖形處理器;SHA算法;MD6算法;線程構(gòu)建模塊;計算統(tǒng)一設(shè)備架構(gòu)

隨著人類進(jìn)入信息化社會,信息安全已成為人們在信息空間中生存與發(fā)展的重要保證.密碼學(xué)和信息安全技術(shù)在最近二十多年來,越來越受到人們的重視,對信息進(jìn)行認(rèn)證的現(xiàn)代安全協(xié)議:例如數(shù)字簽名、消息認(rèn)證等也得到了快速廣泛的使用.對安全散列算法應(yīng)用的需求也越來越大.

2005年 Wang[1]找到對 SHA-1散列函數(shù)的差分攻擊方法.當(dāng)前安全性更強(qiáng)的 SHA-2算法的設(shè)計與SHA-1相同,所以,潛在危險仍然存在.因此,NIST(美國國家標(biāo)準(zhǔn)與技術(shù)研究所)近日宣布[2],將借鑒AES加密算法的模式,通過公開的方式征集新的散列算法,即SHA-3.MD6算法是 SHA-3最佳的中間候選算法之一.

GPU(graphic processing unit,記為 GPU)即圖形化處理器,是現(xiàn)代顯卡中重要的一個部分,其地位與CPU在主板上的地位一致,主要任務(wù)是加速圖形處理速度,隨著 GPU計算能力的飛速提高(高端 GPU計算性能已經(jīng)達(dá)到 Teraflops級別,相當(dāng)于一個高性能計算集群系統(tǒng),遠(yuǎn)大于主流 CPU的計算能力),GPU的應(yīng)用已經(jīng)不僅僅局限于圖形化處理,在科學(xué)計算、地質(zhì)、生物、物理模擬等計算密集型領(lǐng)域也得到了廣泛應(yīng)用[3-5].當(dāng)前,在 GPU上實現(xiàn)密碼算法已經(jīng)成為一個新的研究熱點[6-8].本文研究了如何利用 GPU高效、廉價地實現(xiàn) MD6算法.

1 MD6算法介紹[1]

MD6是 SHA-3的候選算法之一.它是由 Ronald L.Rivest提出的.在這一節(jié)中,將敘述 MD6密碼算法的工作原理,并且找出它所具有的并行性.MD6算法的安全性在文獻(xiàn)[1]有相應(yīng)的證明.

1.1 基本原理

MD6算法將長度小于 264比特的消息作為輸入?yún)⒘?輸出結(jié)果為 d(0＜d≤512)比特的摘要值.d的默認(rèn)值為 256,但它可以變化.此外,MD6算法的很多參量都有默認(rèn)值,但也可以變化.

密鑰 K 默認(rèn)值為空(長度為 0).它作為哈希函數(shù)的輸入密鑰.

層次 L MD6算法實質(zhì)上是 4個子結(jié)點一組的 Merkle樹.樹的高度指定為 L,其默認(rèn)值為 64(此時Merkle樹是一棵完整的樹).如果 L值為 0,將按順序壓縮數(shù)據(jù).如果 L值小于 64,MD6將使用混合模式:首先基于 Merkle樹,從層次 0到層次 L,隨后,在每個層次內(nèi)按順序壓縮數(shù)據(jù).

其他參數(shù) 壓縮函數(shù)中使用的常量(像 Q或 ti)也可以改變.

1.2 運算模式

MD6算法的運算模式基于 4個子結(jié)點一組的Merkle樹.從圖1可以看出MD6Merkle樹具有并行性,實際上,Merkle樹每個結(jié)點都可以并行計算.每個結(jié)構(gòu)體的計量單位是“字”,在本文中表示 8字節(jié)(64位).

圖1 MD 6Merk le樹Fig.1 MD 6Merkle tree

將待做哈希文件的數(shù)據(jù)表示成樹的葉子,如果輸入文件不能滿足每片葉子 16個“字”(相當(dāng)于 128個字節(jié)或者 1 024位),可以用 0填補(bǔ).此外,每個結(jié)點有 4個子結(jié)點,如果必要的話,將用 0填充結(jié)點,以此來創(chuàng)建虛構(gòu)結(jié)點.每個模塊由 4個結(jié)點組成,被壓縮后將得到 16個“字”的結(jié)點.

在算法中,首先創(chuàng)建 Merkle哈希樹,當(dāng)只剩下一個根結(jié)點時,將停止做哈希運算.摘要值為樹根的截斷值(即最后的 d位值,也就是最后的 256位值).

1.3 壓縮函數(shù)

壓縮函數(shù)的每個輸入為 89個“字”的向量,其具體表示如圖 2所示.

圖2 壓縮函數(shù)的輸入數(shù)據(jù)Fig.2 The input data of compression function

K為 8個“字”的密鑰(如沒有使用密鑰,K值為 0).

U為結(jié)點 ID號,其大小為 1個“字”,壓縮函數(shù)的輔助輸入,指示分塊的位置,由表示結(jié)點所在的層次的一個字節(jié)以及表示結(jié)點所在層內(nèi)具體位置的 7個字節(jié)組成.具體結(jié)構(gòu)如圖 3所示.

圖3 結(jié)點 ID U的結(jié)構(gòu)Fig.3 The structure of node ID U

V為控制字,其大小為 1個“字”,壓縮函數(shù)的輔助輸入,其中,r為圈數(shù),L為樹的最大高度,對于最后一次壓縮而言 z等于 1(這時所有的結(jié)點均被壓縮到根結(jié)點),另外,p為填充的 0的個數(shù),keylen為密鑰的長度,d為摘要的大小.具體細(xì)節(jié)如圖 4所示.B為 64個“字”的數(shù)據(jù)塊,與 4個 16個“字”的結(jié)點相匹配.

在 MD6算法中,壓縮函數(shù)將完成 r圈運算(默認(rèn)值為 104),每圈運算有 16個獨立的循環(huán)組成(可能具有并行性).這 16個獨立循環(huán)由大約 15個邏輯運算或移位組成.每圈從上一圈計算的 89個字輸出結(jié)果計算出 16個字輸出結(jié)果(這 89個字的初始值如圖 2所示(壓縮函數(shù)的輸入)).最后一圈計算的 64個字的輸出結(jié)果作為壓縮函數(shù)的輸出結(jié)果.

圖4 控制字V的結(jié)構(gòu)Fig.4 The structure of control word V

1.4 參考實現(xiàn)

基于基數(shù)列表的 MD6算法實現(xiàn)中存儲器的消耗為 log4n.樹的每層由 4個模塊組成,當(dāng)樹的該層填滿時,將通過壓縮這 4個模塊來去除這一層,并將結(jié)果填充到下層次.

這一版本并沒有直接的并行性,實現(xiàn)的 MD6算法采用的是逐層壓縮數(shù)據(jù).開始階段存儲了整個消息,算法中的存儲器使用代價為 O(n).使用了 2個數(shù)組:一個用于工作層,另一個用于工作層的下一層(由模塊壓縮結(jié)果填充),大小是前一數(shù)組的 4倍.

當(dāng)下層次填滿時,它將變?yōu)楣ぷ鲗?將分配一個新的數(shù)組(大小是前一數(shù)組的 4倍)用于新工作層的下一層.為了使本算法具有更好地并行性,需要重復(fù)執(zhí)行運算模式.雖然代碼在壓縮函數(shù)(沒有修正)上花費了大量的時間,但我們的代碼比 Rivest的版本更高效.在測試機(jī)上實現(xiàn)的平均速度為 27.5MB/s.

2 基于 CPU的 MD6算法的并行實現(xiàn)

2.1 Intel TBB簡介[8]

在多核的平臺上開發(fā)并行化程序,必須合理地利用系統(tǒng)的資源,如與內(nèi)核數(shù)目相匹配的線程,內(nèi)存的合理訪問次序,最大化重要緩存.有時候用戶使用(系統(tǒng))低級的應(yīng)用接口創(chuàng)建、管理線程,很難保證程序處于最佳狀態(tài).線程構(gòu)建模塊(TBB)可以很好地解決上述問題.TBB由 Intel提供 C++模板庫(主要用于多處理器/多核框架編程),由一套數(shù)據(jù)結(jié)構(gòu)包裝而成.在具體使用過程中,程序員不必關(guān)注于線程管理,只需專注于任務(wù)本身.而不像使用 POSIX線程或 Boost線程時,必須管理創(chuàng)建,同步以及結(jié)束每個線程.在 TBB庫內(nèi),計算將被看成任務(wù),通過高速緩存器自動分發(fā)到所有可利用的資源上.

2.2 基于 TBB的 MD6算法實現(xiàn)

采用廣度優(yōu)先算法從左到右遍歷整棵樹,對于每層來說,可以并行計算所有模塊的字,而 TBB用于管理不同處理器/核上的分布式計算.

在計算機(jī) A上對 850MB文件作哈希運算測試,發(fā)現(xiàn)每個核內(nèi)運行處理器的數(shù)目影響哈希的速率.在雙核計算機(jī)上,本算法的實現(xiàn)速度是計算機(jī) A上實現(xiàn)速度的 2倍.

由圖 5可以看出,當(dāng)每個核內(nèi)運行的處理器數(shù)目達(dá)到 8個時,性能不再隨著運算處理器數(shù)目的增加而線性增加.原因是計算機(jī)上存儲器的總線帶寬已經(jīng)處于飽和狀態(tài).當(dāng)每個核內(nèi)運行 16個處理器時,本算法的實現(xiàn)速度只提高了 8倍.

圖5 基于TBB的 MD 6算法對不同文件作哈希運算的速率Fig.5 The rate of MD6 base on TBB

3 基于 GPU的 MD6算法

3.1 CUDA

CUDA(computer unified device architecture,簡稱CUDA)是 NVIDIA公司為其 GPU開發(fā)的通用并行計算架構(gòu),它不需要借助圖形學(xué) API就可以使用類 C語言進(jìn)行通用計算的開發(fā)環(huán)境和軟件體系.此外,CUDA還包括專門為 NVIDIA公司 GPU進(jìn)行優(yōu)化實現(xiàn)的大量基礎(chǔ)算法,

如圖 6所示,在 CUDA架構(gòu)下,執(zhí)行的最小單位是線程.數(shù)個線程可以組成一個線程塊.一個線程塊中的線程能存取同一塊共享內(nèi)存,而且可以快速進(jìn)行同步的動作.每個線程塊所能包含的線程數(shù)目是有限的.然而,執(zhí)行相同程序的線程塊,可以組成柵格.不同線程塊中的線程無法存取同一個共享的內(nèi)存,因此,無法直接互通或進(jìn)行同步.所以,不同線程塊中的線程能合作的程度比較低.

圖6 柵格、線程塊和線程之間的關(guān)系Fig.6 Grid、Block and Thread

如圖 7所示,在 CUDA架構(gòu)下,每個線程都有自身的一塊寄存器和本地存儲器.同一個線程塊中的每個線程則有共享的一塊共享存儲器.此外,所有的線程都共享一塊全局存儲器、常量存儲器和紋理存儲器.不同的柵格則有各自的全局存儲器、常量存儲器和紋理存儲器.

3.2 基于 GPU的 MD6算法實現(xiàn)

3.2.1 模塊間的并行性

在第一個 CUDA版本的 MD6算法中,將并行壓縮每個模塊,每個多處理器必須將 4個結(jié)點壓縮成一個結(jié)點,這和 TBB版本相似.每個線程負(fù)責(zé)將每個模塊壓縮成大小為一個“字”的模塊.這一版本實現(xiàn)的平均速率約為 3.2MB/s,即它的實現(xiàn)速度比 CPU版本的實現(xiàn)速度慢了 10倍,這很大程度上是由于沒有充分利用 MD6算法的并行性.

圖7 CUDA的內(nèi)存模型Fig.7 Memory Model of CUDA

3.2.2 壓縮函數(shù)的并行性

每個模塊“字”的壓縮由獨立的步驟組成,特別是每圈壓縮步驟中的 16個循環(huán)的實現(xiàn),這是程序中最耗時的部分.在這一版本的 MD6算法實現(xiàn)中,并行實現(xiàn)壓縮步驟中的 16個循環(huán),希望這樣能增加程序的性能.同時,為了最大并行化這一版本,也并行算法所有可以并行的步驟,包括數(shù)組內(nèi)的存儲器所有復(fù)制操作.

這一版本的實現(xiàn)速度為 31MB/s(是前一版本的 10倍).但這一版本并沒有比 CPU快.對于小文件,圖形化卡上存儲器復(fù)制時間消耗并沒有減輕.這說明,與存儲器訪問相比,壓縮函數(shù)要做太多的計算.為了驗證這一結(jié)論,修改了壓縮函數(shù),將壓縮函數(shù)每圈使用的 16個循環(huán)改為每圈使用 160個循環(huán),該版本的GPU實現(xiàn)比 CPU版本的實現(xiàn)快了 10倍.為了進(jìn)一步提高 MD6算法的實現(xiàn)性能,需要約束存儲器的訪問以及增加每個模塊的計算數(shù)目.

3.2.3 改進(jìn)與提高

為了增加每個模塊的線程數(shù)目,在每個線程塊內(nèi)并行壓縮幾個模塊“字”.僅需要一個 89個字的數(shù)組就可以完成壓縮函數(shù).在每個線程塊內(nèi)使用 89×N個數(shù)組(其中 N為一個線程塊內(nèi)壓縮的模塊字的數(shù)目),而不是 89+16×r個數(shù)組.在本版本的 MD6算法實現(xiàn)中,將使用多個線程壓縮多個模塊字,同時需要幾個工作數(shù)組,但共享存儲器的存儲空間有限,不能在共享存儲器存儲多個數(shù)組(多于一個).同時,由于性能上的原因,也不能在全局存儲器上存儲工作數(shù)組.換句話說,如果將全局存儲器存儲工作數(shù)組,將大幅度地降低 MD6算法實現(xiàn)的性能.因此,對于 N個模塊字,使用 N個循環(huán)數(shù)組作為工作數(shù)組.

對該版本的 MD6算法作進(jìn)一步的優(yōu)化,即使用循環(huán)數(shù)組提高 MD6算法性能.以 89為模數(shù)計算每個數(shù)組的索引.假如使用 128個字的循環(huán)數(shù)組,就只需要使用邏輯計算(按位掩碼)來計算索引,而不是使用耗時的模運算.但 128個字對于高速緩存而言太大,其性能也非常低的.所以,采用 89個字的循環(huán)數(shù)組.每個模塊使用 20×16個線程.實現(xiàn)速度達(dá)到了 83MB/s.

對最新版本的 MD6算法的實現(xiàn)作進(jìn)一步的分析后,可以將模運算的值制成表格,并將其復(fù)制到 GPU的常量存儲器內(nèi).因此,計算循環(huán)數(shù)組索引的消耗就轉(zhuǎn)化為訪問存儲器的消耗.常量存儲器內(nèi)的數(shù)據(jù)可以被高速訪問并且線程可以直接訪問這些數(shù)據(jù),這一優(yōu)化技術(shù)對 MD6算法實現(xiàn)性能的影響非常大.本版本 MD6算法實現(xiàn)的速度達(dá)到 105.6MB/s.

4 性能分析

對于每個版本的測試,測試時間都分為 2種情況:包括存儲器分配和存儲器復(fù)制部分的測試時間,以及未包括存儲器分配和存儲器復(fù)制部分的測試時間,這些時間消耗很大程度上依賴于機(jī)器自身的性能.在測試環(huán)境中計算機(jī)的存儲器復(fù)制速率為2 200MB/s.分別在 CPU和 GPU上測試了不同大小(文件大小從 2字節(jié)開始到 70MB結(jié)束)的文件作哈希的速率.各種 MD6算法實現(xiàn)版本的測試結(jié)果如圖8所示.

對于大文件而言,MD6算法的 GPU版本的實現(xiàn)速率比 CPU版本的實現(xiàn)速率快,同時,還發(fā)現(xiàn)存儲器分配的消耗以及存儲器復(fù)制的消耗與文件大小的關(guān)系不大.MD6算法的 GPU版本做哈希運算的最大速率是 CPU版本的 5倍:即 GPU版本為 153MB/s,而CPU版本為 29MB/s.額外的存儲器消耗是由于主機(jī)存儲器與卡存儲器之間復(fù)制數(shù)據(jù)的消耗(與文件的大小關(guān)系不大).對于 GeForce 9600GTS而言,圖形化卡的存儲器大小有限制.對于大文件,將它分離為 4個更小文件,并使用 GPU版本的 MD6算法對這 4個更小的文件作哈希運算.

圖8 基于 GPU的 MD6算法實現(xiàn)與基于 CPU的MD 6算法實現(xiàn)速度比較Fig.8 The rate of MD6 base on GPU and CPU

5 結(jié)論

對 MD6算法的并行性進(jìn)行了分析,并實現(xiàn)了基于 GPU的 MD6算法.實現(xiàn)參考版本的 MD6算法以及基于 TBB的MD6算法,并對各個版本的實現(xiàn)速度進(jìn)行了相關(guān)測試.結(jié)果表明,當(dāng)文件足夠大時,基于GPU的 MD6算法的實現(xiàn)比基于 CPU的 MD6算法的實現(xiàn)更加高效,基于 GPU的 MD6算法做哈希運算的最大速率是 CPU版本的 5倍.

[1]WANG Xiao-yun,YU Hong-bo.Efficient collision search attacks on SHA-0[C]∥Advances in Cryptology-Eurocrypt'05.Berlin:Sp ringer-Verlag,2005:19-35.

[2]RIVEST R L.Themd6 hash function.a p roposal to nist for sha-3[DB/OL].[2008-10-27].http:∥groups.csail.mit.edu/cis/md6/submitted/Supporting Documentation/md6 report.pd f

[3]NVIDIA CORPORATION.NVIDIA.NVIDIA_CUDA_Programming_Guide_2.0[DB/OL].[2009-10-27].http:∥developer.download.nvidia.com/compute/cuda/.

[4]吳恩華,柳有權(quán).基于圖形處理器(GPU)的通用計算[J].計算輔助設(shè)計與圖形學(xué)學(xué)報,2004,16(5):601-612.WU En-hua,LIU You-quan.General purpose computation on GPU[J].Journal of Computer-aide Design＆Computer Graphics,2004,16(5):601-612.(in Chinese)

[5]吳恩華.圖形處理器用于通用計算的技術(shù)、現(xiàn)狀及其挑戰(zhàn)[J].軟件學(xué)報,2004,15(10):1493-1504.WUEn-hua.State of the art and future challenge on general purpose computation by graphics processing unit[J].Journalof Software,2004,15(10):1493-1504.(in Chinese)

[6]COOK D L,IOANNIDIS J,KEROMYTIS A D,et al.CryptoGraphics:Secret Key Cryp tography Using Graphics Cards[C]∥RSA Con ference:Cryptographer's Track(CT-RSA),2005.

[7]OWENSJD,HOUSTON M,LUEBKED,etal.GPU computing[J].Proceeding of the IEEE,2008,96(5):879-899.

[8]INTEL.Threading Building Blocks Reference Manual[DB/OL].[2009-11-05].http:∥www.threadingbuildingblocks.org/up loads/81/91/Latest%20Open%20Source%20Documentation/Reference%20(Open%20Source).pdf.

(責(zé)任編輯 張士瑛)

The Fast Implementation of MD6 on GPU

LILi-xin1,YE Jian1,YU Yang1
(Institute of Electronic Technology,Information Engineering University,Zhengzhou 450004,China)

Secure Hash Algorithm(SHA)is an important tool in practice of cryptography such as digital signature,and ithasbeen widely applied in electronic businessetc.the information security fields,etc.MD6 is one of the several candidates for the SHA-3 competition.How to implementMD6 efficiently is an urgent question to be answered.This paper presentsa parallel analysis ofMD6,and a fast realization on GPU platform,so as to provide an easy way to implementing SHA quickly and efficiently.

GPU;SHA algorithm;MD6 algorithm;TBB;CUDA

TP 309

A

0254-0037(2010)05-0640-06

2009-12-10.

國家“八六三”計劃基金資助項目(2008AA 01Z404).

李立新(1967—),男,重慶人,副教授.