基于擬態計算機的SHA512算法高吞吐量實現

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

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

1 引言

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

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

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

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

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

2 SHA512算法簡介

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

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

算法的具體流程如下：

(1)填充。

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

(2)迭代加密階段。

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

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

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

步驟2按如下公式計算Wt：

Wt=Mt(0≤t≤15);

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

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

步驟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個64 bit變量H0～H7構成512 bit的數據，就是SHA512算法輸出的散列值。

上述計算過程中使用的一些邏輯函數和常數說明如下：

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 算法優化

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

3.1 加法運算優化

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

Figure 4 80-stage fully pipelined architecture圖4 80級全流水架構示意圖

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

從A、E的賦值運算可以看出，A的賦值運算共由7個加法計算構成，E的賦值運算共由6個加法計算構成。為了對加法進行優化，本文根據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的賦值運算使用CSA7，E的賦值運算使用CSA6。從上述的方法描述可以看出，A的賦值運算由原來的7個加法計算變為2個加法計算，E的賦值運算由原來的6個加法計算變為2個加法計算，減少了關鍵路徑上加法計算的數量，也就大大減少了關鍵路徑上的延時。

3.2 全流水線結構

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

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

綜上所述，全流水線結構的SHA512算法可以通過如下方法來計算：

步驟1明文經過預處理之后，按照1 024 bit為單位進行分組。

步驟2將需要處理的1 024 bit數據塊分成相應的16個64 bit字W0，W1，…，W15。

步驟3令A0=H0，B0=H1，C0=H2，D0=H3，E0=H4，F0=H5，G0=H6，H0=H7(當處理第一分塊時,H0～H7為固定常數，否則為上一分塊輸出結果)。

步驟4在一個時鐘周期內對n從0～79同時做下列運算：

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數據分塊處理完之后，最后的H0～H7就是散列值輸出。

4 算法實驗

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

Table 1 Performance comparison with others in the literature

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

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

其中吞吐量為T，數據塊大小為B，時鐘頻率為f，流水線級數為N，計算延時為d，則可以得出本文全流水結構的SHA512算法實際實現所達到的吞吐量為：

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

Table 2 Comparison of different implementations

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

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

擬態計算機與IBM M3 平臺能效比如表3所示。

Table 3 Comparison of energy efficiency ratios

從表3的數據可以看出，破解同一個SHA512加密文件時，雖然擬態計算機的功耗是M3服務器的三倍多，但是擬態計算機的能效比是M3服務器的一百多倍。

5 結束語

本文給出了SHA512算法基于擬態計算機的全流水線實現方案，通過使用全流水線結構和對加法運算的優化，提高了工作頻率，吞吐率也得到了極大的提高，在130 MHz時鐘頻率下數據吞吐率達133 120 Mbits/s。

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