席勝鑫，張文寧，周清雷，斯雪明，李 斌

(1.鄭州大學(xué)信息工程學(xué)院，河南 鄭州 450001;2.中原工學(xué)院軟件學(xué)院，河南 鄭州 450007;3.解放軍信息工程大學(xué)信息工程學(xué)院，河南 鄭州 450002)

1 引言

近年來，科學(xué)技術(shù)高速發(fā)展，與之伴隨的互聯(lián)網(wǎng)已經(jīng)深深地融入人們的生活和工作中，成為不可或缺的組成部分。網(wǎng)絡(luò)的迅速普及和信息行業(yè)的發(fā)展標(biāo)志著人類已經(jīng)正式跨入了信息化和大數(shù)據(jù)的時(shí)代。信息爆炸而產(chǎn)生的海量數(shù)據(jù)時(shí)刻充斥在日常生活當(dāng)中，而其中更是不乏各種各樣包含個(gè)人隱私和敏感信息的重要文件。在這些信息的挖掘和使用過程中，為了防止其受到竊取和篡改，人們通常采取加密的措施來保障其安全。哈希函數(shù)作為一類在信息安全領(lǐng)域廣泛使用的加密算法[1,2]，在網(wǎng)絡(luò)安全方面和密碼學(xué)領(lǐng)域具有十分重要的意義和廣泛的應(yīng)用。王小云教授在2005年宣布了破譯SHA1的研究成果，因此美國國家標(biāo)準(zhǔn)技術(shù)研究所表示，將逐步使用先進(jìn)的SHA224、SHA256、SHA384及SHA512的密碼系統(tǒng)代替SHA1密碼系統(tǒng)。由此可見，SHA512等算法將會廣泛使用[3,4]。

2013年9月21日，世界第一臺擬態(tài)計(jì)算機(jī)基于認(rèn)知的主動重構(gòu)計(jì)算體系PRCA(Proactive Reconfigurable Computing Architecture)原理驗(yàn)證樣機(jī)在中國研制成功。擬態(tài)計(jì)算指的是在執(zhí)行運(yùn)算的過程中通過自身感知、動態(tài)選擇或者生成最優(yōu)效能解算結(jié)構(gòu)集合。擬態(tài)計(jì)算的目標(biāo)是實(shí)現(xiàn)高性能、高效能的計(jì)算，其實(shí)現(xiàn)本質(zhì)是將高階函數(shù)融入計(jì)算結(jié)構(gòu)當(dāng)中，通過感知程序內(nèi)部的自變量動態(tài)可變地選用最優(yōu)部件解決計(jì)算問題[5]。在擬態(tài)計(jì)算機(jī)處理任務(wù)的過程中，其本身可以對自變量進(jìn)行感知，從而通過擬態(tài)變換的方式生成執(zhí)行所需的最優(yōu)效能解算結(jié)構(gòu)集合。擬態(tài)計(jì)算機(jī)以配置流控制的硬件作為執(zhí)行主體，其計(jì)算、存儲、互聯(lián)等物理執(zhí)行結(jié)構(gòu)屬于變體部分，在執(zhí)行過程中要求動態(tài)可變，最終達(dá)到“依靠動態(tài)可變的物理結(jié)構(gòu)，通過軟硬件結(jié)合實(shí)現(xiàn)高效能、高性能的計(jì)算”。

擬態(tài)計(jì)算機(jī)和通用計(jì)算機(jī)最大的不同之處就在于動態(tài)可變。在執(zhí)行一個(gè)計(jì)算任務(wù)的過程當(dāng)中，通用計(jì)算機(jī)會始終維持其物理結(jié)構(gòu)靜態(tài)不變，以軟件編程的控制作為主要執(zhí)行體；而擬態(tài)計(jì)算機(jī)的所有軟件和硬件變體部件都是動態(tài)可變的，在實(shí)現(xiàn)應(yīng)用處理的過程中，可以根據(jù)程序自變量動態(tài)選擇最優(yōu)的方案來實(shí)現(xiàn)各種功能等價(jià)、計(jì)算效能不同的最優(yōu)解的集合[6]。因此，擬態(tài)計(jì)算機(jī)高效能、高性能的特點(diǎn)使它非常適合于計(jì)算密集型的大數(shù)據(jù)量處理任務(wù)。在口令恢復(fù)的運(yùn)算過程中往往伴隨大量的迭代運(yùn)算，如WORD2013中的SHA512運(yùn)算、ZIP中的SHA1運(yùn)算，哈希算法的高次迭代運(yùn)算量占到口令恢復(fù)算法整個(gè)流程運(yùn)算量的90%以上。擬態(tài)計(jì)算機(jī)在實(shí)現(xiàn)口令恢復(fù)的過程中，通過識別口令恢復(fù)的需求和變化，同時(shí)感知系統(tǒng)中可以利用的處理資源，依據(jù)盡可能高性能和高效能的原則，認(rèn)知并決策出的現(xiàn)場可編程門陣列FPGA(Field-Programmable Gate Arrary)對于實(shí)現(xiàn)SHA512等哈希函數(shù)的運(yùn)算具有速度快、吞吐量高的特點(diǎn)。

FPGA是擬態(tài)計(jì)算機(jī)中的重要部件，它具有體系結(jié)構(gòu)和邏輯單元靈活、設(shè)計(jì)開發(fā)周期短、集成度高以及適用范圍寬等特點(diǎn)[7]。兼容了可編程邏輯器件PLD(Programmable Logic Device)和通用門陣列的優(yōu)點(diǎn)，可實(shí)現(xiàn)較大規(guī)模的電路，編程也很靈活[8,9]。由于SHA512算法本身的復(fù)雜性，使用軟件加密則會存在加密速度慢、占用CPU資源等諸多缺點(diǎn)，因此使用硬件實(shí)現(xiàn)算法就成為未來應(yīng)用的必然選擇。

SHA512在FPGA中已經(jīng)有實(shí)現(xiàn)，也產(chǎn)生了很多不同的實(shí)現(xiàn)方案。Algredo-Badillo等人[2]采用了不同級數(shù)的流水線對SHA512算法進(jìn)行優(yōu)化，并對不同的方案進(jìn)行了分析。Rote等人[3]采用了環(huán)形流水線的方式，對SHA2算法進(jìn)行了實(shí)現(xiàn)，提高了算法的吞吐率。文獻(xiàn)[10]通過對關(guān)鍵運(yùn)算部分進(jìn)行分解，采用中間變量進(jìn)行預(yù)計(jì)算，實(shí)現(xiàn)了SHA512迭代部分的并行計(jì)算處理，提高了運(yùn)算速度。文獻(xiàn)[11]通過循環(huán)打開和路徑優(yōu)化兩大硬件優(yōu)化技術(shù)，在保持較小面積和相似主頻的情況下，提高了加密速率。文獻(xiàn)[12]在關(guān)鍵計(jì)算路徑上進(jìn)行了加法器結(jié)構(gòu)的優(yōu)化，并且實(shí)現(xiàn)了分組數(shù)據(jù)輸入與循環(huán)運(yùn)算的并行進(jìn)行,減少了加密一個(gè)分組所需的時(shí)鐘周期數(shù),提高了加密效率。文獻(xiàn)[13]采用數(shù)據(jù)流可重構(gòu)的設(shè)計(jì)思想和方法設(shè)計(jì)了一種新的硬件結(jié)構(gòu)實(shí)現(xiàn)多種哈希函數(shù)，注重降低資源的消耗。鑒于目前芯片技術(shù)突飛猛進(jìn)的發(fā)展，使用更多的邏輯資源來換取運(yùn)算時(shí)間的降低，以提升運(yùn)算性能已經(jīng)十分普遍。本文將介紹使用全流水線結(jié)構(gòu)在擬態(tài)計(jì)算機(jī)中實(shí)現(xiàn)SHA512算法，同時(shí)也對加法運(yùn)算進(jìn)行優(yōu)化，達(dá)到增加工作頻率和并行化的目的,從而提高SHA512的計(jì)算速度和效能。

2 SHA512算法簡介

SHA512算法可以將任意長的輸入消息串(長度不超過2128bit),通過一系列操作轉(zhuǎn)化為固定長的輸出串，且轉(zhuǎn)化過程不可逆，如圖1所示。

Figure 1 Whole process of SHA512 algorithm圖1 SHA512算法整體流程

算法的具體流程如下：

(1)填充。

SHA512算法的運(yùn)算過程是以1 024 bit(16×64 bit)為單位進(jìn)行的，因此需要對輸入消息串進(jìn)行數(shù)據(jù)填充處理。第一步填充的字符串高位為1，其余位為 0，使其滿足：填充后的字符串長度模1 024后余896 bit；第二步填充(即長度填充)，長128 bit的長度值(以bit為單位)附加在經(jīng)過數(shù)據(jù)填充后的消息后，使得消息的最終長度為1 024位的整數(shù)倍。

(2)迭代加密階段。

SHA512是對長度為1 024 bit的數(shù)據(jù)塊進(jìn)行處理，因此需要將輸入的數(shù)據(jù)每1 024 bit分成一塊。分塊之后就可以對每塊數(shù)據(jù)按下述方法依次進(jìn)行處理(這里以一個(gè)1 024 bit的數(shù)據(jù)塊進(jìn)行說明):

Figure 2 Calculation of Wt value and register shift圖2 Wt值計(jì)算和寄存器移位

步驟1將1 024 bit的消息塊分成16個(gè)64 bit的字M0，M1，…，M15。

步驟2按如下公式計(jì)算Wt：

Wt=Mt(0≤t≤15);

Wt=σ1(Wt-2)+Wt-7+σ0(Wt-15)+Wt-16(16≤t≤79)。

步驟3令A(yù)=H0，B=H1，C=H2，D=H3，E=H4，F(xiàn)=H5，G=H6，H=H7(H0～H7為固定常數(shù))。

步驟4Fort=0 to 79(Kt為固定哈希值)

T2=Σ0(A)+Maj(A,B,C);

H=G;

G=F;

F=E;

E=D+T1;

D=C;

C=B;

B=A;

A=T1+T2。

步驟5令H0=A+H0，H1=B+H1，H2=C+H2，H3=D+H3，H4=E+H4，H5=F+H5，H6=G+H6，H7=H+H7。

所有消息塊處理完后得到的8個(gè)64 bit變量H0～H7構(gòu)成512 bit的數(shù)據(jù)，就是SHA512算法輸出的散列值。

上述計(jì)算過程中使用的一些邏輯函數(shù)和常數(shù)說明如下：

Ch(x,y,z)=(x∩y)⊕(x∩z)；

Maj(x,y,z)=(x∩y)⊕(x∩z)⊕(y∩z)；

σ0=ROTH1⊕ROTH8⊕SHR7；

σ1=ROTH19⊕ROTH61⊕SHR6；

Σ0(x)=ROTH28⊕ROTH34⊕ROTH39；

Σ1(x)=ROTH14⊕ROTH18⊕ROTH41；

ROTRn(x)=(x?n)∪(x?w-n)；

SHRn(x)=x?n。

3 算法優(yōu)化

SHA512算法迭代加密階段，步驟2中計(jì)算Wt，從計(jì)算公式可看出，W0～W15無需計(jì)算，可直接輸出，從W16開始，需要經(jīng)過計(jì)算方可輸出。分析計(jì)算公式可以發(fā)現(xiàn)，輸入計(jì)算模塊中的Wt-2、Wt-7、Wt-15、Wt-16隨著每步的執(zhí)行向后移動一個(gè)字。因此，可以使用 16個(gè)64位寄存器，從第17步開始，每一步寄存器里的數(shù)據(jù)都向右移動一個(gè)字的長度。如圖2所示，這樣每一步以后，上述4個(gè)字Wt-2、Wt-7、Wt-15、Wt-16也將發(fā)生相應(yīng)的變化，然后再將該步計(jì)算所得Wt輸出補(bǔ)充到最后一個(gè)寄存器中。

3.1 加法運(yùn)算優(yōu)化

從上述算法描述可以看出，SHA512最關(guān)鍵的計(jì)算是步驟4的哈希迭代運(yùn)算，SHA512每1 024位數(shù)據(jù)塊需要80個(gè)時(shí)鐘周期才能完成處理。并且在每輪的哈希計(jì)算中，SHA512涉及一個(gè)6個(gè)數(shù)相加和一個(gè)7個(gè)數(shù)相加的加法運(yùn)算。如圖3所示，在每輪的哈希計(jì)算中，B、C、D、F、G、H的值無需計(jì)算，分別由上一輪的A、B、C、E、F、G直接賦值得到，幾乎沒有電路上的延時(shí)。而A涉及7個(gè)數(shù)相加，還有一些異或運(yùn)算，這就大大增大了關(guān)鍵路徑上的延時(shí)，使整個(gè)算法的運(yùn)行頻率降低。因此，要提高哈希函數(shù)的運(yùn)算速度可以從提高算法的工作頻率著手。而提高算法的工作頻率，可以通過減少算法實(shí)現(xiàn)的關(guān)鍵路徑的長度，減少關(guān)鍵路徑的延時(shí)來實(shí)現(xiàn)。加法在FPGA 的實(shí)現(xiàn)中要比位操作的延時(shí)大得多，因此本文基于進(jìn)位選擇加法器CSA(Carry Select Adder)的原理對加法進(jìn)行優(yōu)化。CSA方式是根據(jù)如下特性做出的：如果Result=A+B+C，則有S=AxorBxorC；Ca=((AandB) or (BandC) or (AandC))?1；最后結(jié)果為Result=Ca+S。

Figure 4 80-stage fully pipelined architecture圖4 80級全流水架構(gòu)示意圖

Figure 3 Schematic diagram of single step iterative processing of SHA512 algorithm圖3 SHA512算法單步迭代處理示意圖

從A、E的賦值運(yùn)算可以看出，A的賦值運(yùn)算共由7個(gè)加法計(jì)算構(gòu)成，E的賦值運(yùn)算共由6個(gè)加法計(jì)算構(gòu)成。為了對加法進(jìn)行優(yōu)化，本文根據(jù)CSA原理，定義了如下方法：

CSA(a,b,c)=(axorbxorc)+(((aandb) or (bandc) or (aandc))?1)；

CSA4(a,b,c,d)=CSA((axorbxorc),(((aandb)or(bandc) or (aandc))?1),d)；

CSA5(a,b,c,d,e)=CSA4((axorbxorc),(((aandb)or(bandc) or (aandc))?1),d,e)；

CSA6(a,b,c,d,e,f)=CSA4((axorbxorc),(((aandb) or (bandc) or (aandc))?1),(dxorexorf),(((dande) or (eandf) or (dandf))?1))；

CSA7(a,b,c,d,e,f,g)=CSA5((axorbxorc),(((aandb) or (bandc) or (aandc))?1),(dxorexorf),(((dande) or (eandf) or (dandf))?1),g)。

因此，A的賦值運(yùn)算使用CSA7，E的賦值運(yùn)算使用CSA6。從上述的方法描述可以看出，A的賦值運(yùn)算由原來的7個(gè)加法計(jì)算變?yōu)?個(gè)加法計(jì)算，E的賦值運(yùn)算由原來的6個(gè)加法計(jì)算變?yōu)?個(gè)加法計(jì)算，減少了關(guān)鍵路徑上加法計(jì)算的數(shù)量，也就大大減少了關(guān)鍵路徑上的延時(shí)。

3.2 全流水線結(jié)構(gòu)

Figure 5 80-stage pipeline in SHA512 algorithm 圖5 SHA512算法80級流水線

如果某個(gè)設(shè)計(jì)的處理流程可分為若干步驟，而且整個(gè)數(shù)據(jù)處理是“單流向”的，即沒有反饋或者迭代運(yùn)算，前一個(gè)步驟的輸出是下一個(gè)步驟的輸入，可利用流水線技術(shù)來提高處理的并行度。在SHA512最核心的80輪迭代運(yùn)算中，如圖4所示，單步運(yùn)算有著結(jié)構(gòu)上的相似性，每一輪數(shù)據(jù)都是上一輪運(yùn)算的結(jié)果，并且沒有反饋。因此，本文采用全流水線技術(shù)增加并行程度。為了將吞吐量提升至最高，通過打開循環(huán)并且加入中間寄存器，把80輪循環(huán)迭代運(yùn)算的每一輪作為流水線的一級，構(gòu)建了一個(gè)80級的全流水線。在80級的全流水線中，每一級對應(yīng)傳統(tǒng)的80輪迭代運(yùn)算中的一輪運(yùn)算。為了提高對公共寄存器的使用率，本文構(gòu)建了一個(gè)80級的全流水線。如圖5所示，在第一個(gè)時(shí)鐘周期，第一組64 bit數(shù)據(jù)進(jìn)入第一級流水線進(jìn)行處理；在第二個(gè)時(shí)鐘周期，第一組數(shù)據(jù)處理完后傳遞到第二級，與此同時(shí)第二組64 bit數(shù)據(jù)進(jìn)入第一級；每一個(gè)時(shí)鐘周期都按照這樣的流水線處理方式處理。從每一組數(shù)據(jù)的處理來看，每一組數(shù)據(jù)都需要80個(gè)時(shí)鐘周期進(jìn)行處理，但在整個(gè)80輪流水線處理過程中，每一個(gè)時(shí)鐘周期都能計(jì)算出一組數(shù)據(jù)。因此，平均計(jì)算一組數(shù)據(jù)只需要一個(gè)時(shí)鐘周期，大大提高了數(shù)據(jù)處理速度，保證了整個(gè)系統(tǒng)以較高的頻率工作。

綜上所述，全流水線結(jié)構(gòu)的SHA512算法可以通過如下方法來計(jì)算：

步驟1明文經(jīng)過預(yù)處理之后，按照1 024 bit為單位進(jìn)行分組。

步驟2將需要處理的1 024 bit數(shù)據(jù)塊分成相應(yīng)的16個(gè)64 bit字W0，W1，…，W15。

步驟3令A(yù)0=H0，B0=H1，C0=H2，D0=H3，E0=H4，F(xiàn)0=H5，G0=H6，H0=H7(當(dāng)處理第一分塊時(shí),H0～H7為固定常數(shù)，否則為上一分塊輸出結(jié)果)。

步驟4在一個(gè)時(shí)鐘周期內(nèi)對n從0～79同時(shí)做下列運(yùn)算：

Wt=σ1(Wt-2)+Wt-7+σ0(Wt-15)+Wt-16,t≥16；

Bn+1=An；

Cn+1=Bn；

Dn+1=Cn；

Fn+1=En；

Gn+1=Fn；

Hn+1=Gn。

步驟5令H0=A80+H0，H1=B80+H1，H2=C80+H2，H3=D80+H3，H4=E80+H4，H5=F80+H5，H6=G80+H6，H7=H80+H7。

步驟6所有的1 024 bit數(shù)據(jù)分塊處理完之后，最后的H0～H7就是散列值輸出。

4 算法實(shí)驗(yàn)

本文在ISE Design Suite軟件上使用Verilog硬件描述語言實(shí)現(xiàn)了設(shè)計(jì)的SHA512算法，仿真結(jié)果正確，編譯綜合通過，并且下載到Xilinx公司的Virtex6系列XC6VLX550T器件中進(jìn)行測試，芯片運(yùn)行正常，測試結(jié)果正確。如表1所示，本文所實(shí)現(xiàn)的芯片的最大工作頻率為130 MHz，吞吐量達(dá)133 120 Mbits/s，是文獻(xiàn)[2]的130倍，是文獻(xiàn)[3]的56倍，是文獻(xiàn)[12]的102倍，是文獻(xiàn)[13]的92倍，加密速率得到了很大的提升，優(yōu)于以往的實(shí)現(xiàn)結(jié)果。

Table 1 Performance comparison with others in the literature

本文還在Xilinx公司的Virtex6系列XC6VLX550T開發(fā)板上實(shí)現(xiàn)了另外幾種SHA512算法。如表2所示，NoP_NoCSA代表1級流水線并且沒有加法運(yùn)算優(yōu)化；NoP_CSA代表1級流水線并且經(jīng)過加法運(yùn)算優(yōu)化；P_NoCSA代表80級流水線并且沒有加法運(yùn)算優(yōu)化；P_CSA代表80級流水線并且經(jīng)過加法運(yùn)算優(yōu)化(即本文算法)。另外，本文計(jì)算吞吐量的公式如下所示：

(1024×130×80)/80=133120 Mbi/s

其中吞吐量為T，數(shù)據(jù)塊大小為B，時(shí)鐘頻率為f，流水線級數(shù)為N，計(jì)算延時(shí)為d，則可以得出本文全流水結(jié)構(gòu)的SHA512算法實(shí)際實(shí)現(xiàn)所達(dá)到的吞吐量為：

由NoP_NoCSA和P_NoCSA對比可以看出，雖然P_NoCSA的頻率比NoPNoCSA的低，并且P_NoCSA占用的LUT(Look-Up-Table)和寄存器都是No_NoCSA的20倍，但是P_NoCSA的吞吐量卻是No_NoCSA的60倍。因此，本文采用的全流水線結(jié)構(gòu)增加了同時(shí)處理數(shù)據(jù)的能力，極大地提高了數(shù)據(jù)吞吐率。由NoP_NoCSA與NoP_CSA對比可以看出，兩者的LUT和寄存器占用的數(shù)量很接近，但是NoP_CSA的頻率卻比NoP_NoCSA高50 MHz。因此，本文采用的加法運(yùn)算優(yōu)化，對于提高工作頻率,降低一個(gè)周期內(nèi)的運(yùn)算延時(shí)，是非常有效的。

Table 2 Comparison of different implementations

綜上所述，P_CSA 與NoP_NoCSA對比，P_CSA占用的LUT和寄存器數(shù)量分別是NoP_NoCSA的30倍和20倍，但數(shù)據(jù)吞吐率是NoP_NoCSA的80倍。本文采用全流水線結(jié)構(gòu)和加法運(yùn)算優(yōu)化，雖然占用了一定數(shù)量的資源，但是數(shù)據(jù)吞吐率得到了極大的提高，因此本文對于SHA512算法的優(yōu)化方案是值得采納的。

基于擬態(tài)計(jì)算機(jī)高效能的特點(diǎn)，本文隨機(jī)選取一個(gè)加密SHA512文件，與IBM M3(在M3上安裝了HashCat)進(jìn)行比較，分別測試性能，并通過功耗儀來測量任務(wù)破解過程中的功耗。本文引入能效比來評測不同平臺的效能高低。假定平臺的能效比為E;M代表性能，即口令回復(fù)中的破解速度;P代表各平臺運(yùn)行時(shí)的功耗，則平臺的能效比為：

擬態(tài)計(jì)算機(jī)與IBM M3 平臺能效比如表3所示。

Table 3 Comparison of energy efficiency ratios

從表3的數(shù)據(jù)可以看出，破解同一個(gè)SHA512加密文件時(shí)，雖然擬態(tài)計(jì)算機(jī)的功耗是M3服務(wù)器的三倍多，但是擬態(tài)計(jì)算機(jī)的能效比是M3服務(wù)器的一百多倍。

5 結(jié)束語

本文給出了SHA512算法基于擬態(tài)計(jì)算機(jī)的全流水線實(shí)現(xiàn)方案，通過使用全流水線結(jié)構(gòu)和對加法運(yùn)算的優(yōu)化，提高了工作頻率，吞吐率也得到了極大的提高，在130 MHz時(shí)鐘頻率下數(shù)據(jù)吞吐率達(dá)133 120 Mbits/s。

另外，通過理論分析和實(shí)驗(yàn)驗(yàn)證，雖然本文的實(shí)驗(yàn)方案占用了一定數(shù)量的資源，LUT和寄存器的使用量分別是1級流水線的30倍和20倍，數(shù)據(jù)吞吐率卻是1級流水線的80倍。最后，為了驗(yàn)證擬態(tài)計(jì)算機(jī)高效能的特點(diǎn)，本文通過實(shí)驗(yàn)與IBM M3進(jìn)行了能效比測試。實(shí)驗(yàn)表明，擬態(tài)計(jì)算機(jī)的能效比遠(yuǎn)高于通用服務(wù)器的。