可重構(gòu)的SHA-3 算法流水線結(jié)構(gòu)優(yōu)化及實(shí)現(xiàn)

周雍浩，董婉瑩，李斌，陳曉杰，馮峰

（1.鄭州大學(xué)電氣工程學(xué)院，鄭州450001；2.鄭州大學(xué)信息工程學(xué)院，鄭州450001；3.中國(guó)人民解放軍信息工程大學(xué)數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室，鄭州450001）

0 引言

安全散列算法（Secure Hash Algorithm，SHA）是由美國(guó)NIST 發(fā)布的一種密碼散列函數(shù)，其作用是對(duì)不定長(zhǎng)的消息計(jì)算出一個(gè)固定長(zhǎng)度的消息摘要[1]。SHA 具有單向性和抗碰撞性，是密碼學(xué)中的一個(gè)重要工具，被廣泛應(yīng)用于數(shù)據(jù)完整性校驗(yàn)、數(shù)字簽名、消息鑒別和密碼協(xié)議等信息安全領(lǐng)域[2]。但是，隨著計(jì)算機(jī)技術(shù)的快速發(fā)展和破解技術(shù)的增強(qiáng)，MD5 和SHA-1 相繼被成功破解，變得并不安全。因此，NIST 制定了新的SHA3 標(biāo)準(zhǔn)，并將Keccak 算法選定為SHA3 標(biāo)準(zhǔn)的單向散列算法[3]。由于SHA3 算法本身的復(fù)雜性且在應(yīng)用中經(jīng)常被多次迭代使用，所以如何實(shí)現(xiàn)更快速的SHA3 算法，成為了亟待解決的問(wèn)題。FPGA 作為可重構(gòu)硬件，憑借著高性能、低功耗的特性成為了實(shí)現(xiàn)密碼算法的首選平臺(tái)。國(guó)內(nèi)外眾多學(xué)者也在FPGA 上對(duì)SHA3 算法進(jìn)行了優(yōu)化、實(shí)現(xiàn)，但是很少涉及全流水線結(jié)構(gòu)和并行的設(shè)計(jì)方案。

綜上，本文通過(guò)分析SHA3 算法的關(guān)鍵路徑，使用可重構(gòu)硬件FPGA 和流水線技術(shù)，并以展開(kāi)結(jié)構(gòu)的方法進(jìn)一步優(yōu)化算法，達(dá)到了增加工作頻率和并行化的目的，以實(shí)現(xiàn)高效能的SHA3 算法。

1 背景知識(shí)

1.1 SHA3簡(jiǎn)介

Keccak 算法是SHA3 標(biāo)準(zhǔn)選定的算法，采用不同于MD（如MD5）類(lèi)結(jié)構(gòu)的海綿結(jié)構(gòu)。海綿結(jié)構(gòu)如圖1所示。

圖1 海綿結(jié)構(gòu)

其中，壓縮函數(shù)Keccak-f 是海綿結(jié)構(gòu)的計(jì)算引擎，它封裝了海綿結(jié)構(gòu)的主要計(jì)算邏輯。內(nèi)部狀態(tài)是海綿結(jié)構(gòu)計(jì)算操作數(shù)的載體，內(nèi)部狀態(tài)在海綿結(jié)構(gòu)中作為壓縮函數(shù)Keccak-f 的輸入輸出。b 代表內(nèi)部狀態(tài)的比特長(zhǎng)度，b 的具體數(shù)值必須滿足公式（1）：

因此，b∈{25，50，100，200，400，800，1600}。海綿結(jié)構(gòu)由b 還定義了兩個(gè)分量，比特率（bitrate，用r 表示）和容量（capacity，用c 表示），且b、r 和c 滿足關(guān)系b=r+c，三者的具體值均由使用者決定。圖1 中{M1，...，Mn}是對(duì)填充后消息的分組，分組長(zhǎng)度等于r；{H1，...，Hm}是分步提取的散列值，每個(gè)散列值的長(zhǎng)度等于r，提取步數(shù)m 由使用者決定，所有散列值按提取順序排列合并成最終的輸出散列值。

海綿結(jié)構(gòu)在工作過(guò)程上分為吸收和擠出兩個(gè)階段，吸收階段是將輸入消息根據(jù)分組依次“攪拌”進(jìn)它的內(nèi)部狀態(tài)的過(guò)程，擠出階段是分步提取輸出散列值的過(guò)程。在吸收階段，初始時(shí)將內(nèi)部狀態(tài)的所有比特位置0，接下來(lái)反復(fù)進(jìn)行以下過(guò)程，直到消息分組耗盡。該過(guò)程是，先將消息分組Mi（1 ≤i ≤n）與內(nèi)部狀態(tài)的前r 個(gè)比特異或，然后將內(nèi)部狀態(tài)輸入壓縮函數(shù)Keccak-f，最后壓縮函數(shù)Keccak-f 處理后輸出內(nèi)部狀態(tài)。在擠出階段，根據(jù)使用者選擇的步數(shù)，分步重復(fù)以下過(guò)程。該過(guò)程是，先獲取內(nèi)部狀態(tài)的前r 個(gè)比特，然后將內(nèi)部狀態(tài)輸入壓縮函數(shù)Keccak-f，最后壓縮函數(shù)Keccak-f 處理后輸出內(nèi)部狀態(tài)。

對(duì)于壓縮函數(shù)Keccak-f。內(nèi)部狀態(tài)在輸入壓縮函數(shù)Keccak-f 后和壓縮函數(shù)Keccak-f 輸出前都需要經(jīng)過(guò)格式轉(zhuǎn)換，即壓縮函數(shù)Keccak-f 處理過(guò)程中內(nèi)部狀態(tài)為函數(shù)可操作的格式。壓縮函數(shù)Keccak-f 中輪計(jì)算的輪數(shù)由公式（2）計(jì)算得到，其中變量l 來(lái)自于公式（1），因此間接取決于使用者的選擇。

在SHA3 標(biāo)準(zhǔn)下Keccak 算法具有以下特點(diǎn)：

（1）在輸入上，采用Keccak 算法的SHA3 沒(méi)有長(zhǎng)度限制。

（2）在輸出上，Keccak 算法本身可以生成任意長(zhǎng)度的散列值，但為了配合SHA2 的散列值長(zhǎng)度，SHA3 標(biāo)準(zhǔn)中規(guī)定了SHA3-224、SHA3-256、SHA3-384、SHA3-512 這4 種版本。本文實(shí)現(xiàn)的是SHA3-256，即最終輸出的散列值長(zhǎng)度為256 比特。

（3）在參數(shù)選取上，SHA3 標(biāo)準(zhǔn)選定了b 的取值為1600，從而壓縮函數(shù)Keccak-f 的輪計(jì)算輪數(shù)為24。

1.2 FPGA簡(jiǎn)介

現(xiàn)場(chǎng)可編程門(mén)陣列（Field Programmable Gate Array，F(xiàn)PGA），是一種擁有高密度邏輯、大量計(jì)算和存儲(chǔ)資源的高性能計(jì)算平臺(tái)。FPGA 的本質(zhì)是無(wú)指令、無(wú)需共享內(nèi)存的體系結(jié)構(gòu)，通過(guò)編程可定義其中的單元配置和鏈接架構(gòu)進(jìn)行計(jì)算。FPGA 以查找表和寄存器實(shí)現(xiàn)復(fù)雜的組合邏輯操作，且片上內(nèi)存BRAM 屬于各自的邏輯區(qū)域，無(wú)需不必要的仲裁和緩存。因此FPGA的運(yùn)算速度足夠快，具有很強(qiáng)的計(jì)算能力和靈活性，使得FPGA 可重構(gòu)計(jì)算系統(tǒng)成為加速科學(xué)計(jì)算的一種重要選擇[4]。如圖2 所示，給出了一般的FPGA 芯片的邏輯結(jié)構(gòu)。

圖2 FPGA內(nèi)部邏輯結(jié)構(gòu)

據(jù)此，文獻(xiàn)[5]提出了一種流水線硬件架構(gòu)，該架構(gòu)支持4 種SHA3 操作模式，以及可同時(shí)支持多塊和多消息處理的FPGA 器件的高性能實(shí)現(xiàn)，在不同F(xiàn)PGA器件上的實(shí)驗(yàn)結(jié)果證明提出的設(shè)計(jì)實(shí)現(xiàn)了吞吐量的顯著提高。文獻(xiàn)[6]通過(guò)流水線、子流水線和展開(kāi)的方法，優(yōu)化實(shí)現(xiàn)了SHA3 的五種方案，其中方案五在吞吐量和面積效率上取得了平衡。文獻(xiàn)[7]根據(jù)SHA3 的結(jié)構(gòu)特點(diǎn)和FPGA 內(nèi)部邏輯，主要采用折疊的方式對(duì)其進(jìn)行了優(yōu)化，減少了所需的面積資源并獲得了更短的數(shù)據(jù)路徑，算法效率至少提高了50%。文獻(xiàn)[8]采用SoC設(shè)計(jì)，在FPGA 端實(shí)現(xiàn)了SHA3 算法，并通過(guò)AHB 接口與ARM 端互連，提高了算法應(yīng)用范圍。文獻(xiàn)[9]采用基于鎖存器的時(shí)鐘門(mén)控技術(shù)優(yōu)化了SHA3 算法，并有效降低了功耗。但是這些方案本質(zhì)上仍是串行計(jì)算，只是局部使用了流水線技術(shù)，仍有提升空間。

綜上，本文通過(guò)深入分析SHA3 算法，以全流水線結(jié)構(gòu)，優(yōu)化設(shè)計(jì)適合FPGA 的數(shù)據(jù)通路，以提高算法速度。

2 SHA3在FPGA上的優(yōu)化及流水線實(shí)現(xiàn)

2.1 關(guān)鍵計(jì)算分析

從SHA3 的算法流程中可以看出，Keccak-f 計(jì)算是關(guān)鍵。想要提高算法的性能，必須對(duì)Keccak-f 深入分析。當(dāng)b=1600 時(shí)，將輸入數(shù)據(jù)轉(zhuǎn)換為5×5×64 的三維結(jié)構(gòu)，并用元素為64 位的二維數(shù)組A 表示，則有A[x、y]，其中x、y∈[0，4]。Keccak-f 每輪總共有5 個(gè)計(jì)算步驟[10]，分別用θ，ρ，π，χ，ι表示，每個(gè)計(jì)算步驟的具體運(yùn)算如下所示：

上述運(yùn)算步驟中，⊕代表按位異或運(yùn)算，?代表按位取反運(yùn)算，∧代表按位與運(yùn)算。rot 函數(shù)表示循環(huán)移位。r[x][y]和RC 分別是移位位數(shù)和輪常數(shù)。

θ的處理過(guò)程較復(fù)雜，可預(yù)先循環(huán)展開(kāi)，對(duì)操作的數(shù)據(jù)進(jìn)行計(jì)算，并確定需要操作數(shù)據(jù)的位置，從而方便后續(xù)的實(shí)現(xiàn)。ρ是對(duì)θ的輸出進(jìn)行移位，π的功能是對(duì)ρ的輸出進(jìn)行位置交換，因此可通過(guò)預(yù)先計(jì)算出交換的位置以及需要的移位，從而將ρ、π進(jìn)行合并。χ是對(duì)π的輸出進(jìn)行運(yùn)算，ι對(duì)χ的輸出進(jìn)行一次常量的異或運(yùn)算，因此可將χ與ι進(jìn)行合并。通過(guò)對(duì)這五個(gè)步驟進(jìn)行預(yù)計(jì)算、合并等預(yù)處理，從而簡(jiǎn)化了Keccak-f 的計(jì)算且降低了實(shí)現(xiàn)復(fù)雜度。

2.2 全流水線實(shí)現(xiàn)

SHA3 算法中Keccak-f 包含24 輪重復(fù)的運(yùn)算，且每一輪的輸入、輸出僅與相鄰的輪具有依賴關(guān)系，因此可將SHA3 算法通過(guò)流水線技術(shù)實(shí)現(xiàn)為并行算法，從而降低時(shí)間復(fù)雜度。

流水線是一種通過(guò)增加空間的利用來(lái)減少時(shí)間消耗的時(shí)空映射技術(shù)。通過(guò)前述的預(yù)處理，每輪的五個(gè)步驟變?yōu)榱甩取ⅵ薛小ⅵ枝扇剑梢圆捎?4 級(jí)流水線結(jié)構(gòu)實(shí)現(xiàn)。具體的，每一級(jí)流水線都包含三步運(yùn)算，并壓縮在一個(gè)子模塊中，共24 個(gè)子模塊，對(duì)應(yīng)24 輪運(yùn)算。同時(shí)，為了在一個(gè)時(shí)鐘計(jì)算出一輪運(yùn)算結(jié)果，將θ、ρπ實(shí)現(xiàn)為線網(wǎng)型的組合邏輯，而χι實(shí)現(xiàn)為依賴于時(shí)鐘信號(hào)的時(shí)序邏輯，算法在FPGA 中實(shí)現(xiàn)的時(shí)序結(jié)構(gòu)如圖3所示。

圖3 SHA3算法FPGA實(shí)現(xiàn)流水線結(jié)構(gòu)

圖3 中一個(gè)時(shí)鐘周期的每級(jí)流水線內(nèi)三個(gè)計(jì)算步驟串行執(zhí)行，而24 個(gè)子計(jì)算模塊并行運(yùn)行，圖中的箭頭指向表示數(shù)據(jù)的傳遞方向。當(dāng)有一組數(shù)據(jù)需要進(jìn)行Keccak-f 處理時(shí)，需經(jīng)過(guò)24 個(gè)時(shí)鐘周期處理完畢，而當(dāng)有n 組數(shù)據(jù)需要進(jìn)行Keccak-f 處理時(shí)，只需要n+23 個(gè)時(shí)鐘周期，時(shí)間復(fù)雜度為Ο（n）。因此，在滿負(fù)荷的情況下，一組數(shù)據(jù)僅需要一個(gè)時(shí)鐘周期即可產(chǎn)生結(jié)果，從而通過(guò)算法的并行化，減少了計(jì)算的時(shí)間，提升了運(yùn)行效率。

2.3 展開(kāi)再優(yōu)化

通過(guò)對(duì)Keccak-f 的分析可知，其每輪運(yùn)算包含76次異或運(yùn)算，25 次位非運(yùn)算，50 次位與運(yùn)算以及49 次移位運(yùn)算。雖然FPGA 對(duì)于位運(yùn)算具有較好的性能表現(xiàn)，但是在一個(gè)時(shí)鐘周期內(nèi)將200 次運(yùn)算串行執(zhí)行結(jié)束，會(huì)存在較大的延時(shí)。在全流水線結(jié)構(gòu)中，算法的執(zhí)行效率由頻率決定，因此，提高算法的頻率，減少算法的延時(shí)是一種有效的優(yōu)化方法。

Keccak-f 每輪運(yùn)算的計(jì)算步驟間數(shù)據(jù)是依次傳遞的，因此可將每個(gè)時(shí)鐘周期內(nèi)串行執(zhí)行的三步進(jìn)行時(shí)鐘展開(kāi)。由于ρπ僅包含移位運(yùn)算，結(jié)構(gòu)特殊，因此可將ρπ獨(dú)立進(jìn)行一個(gè)時(shí)鐘周期的運(yùn)算，而將θ和χι在另一個(gè)時(shí)鐘周期內(nèi)串行運(yùn)行，即由原來(lái)的一個(gè)時(shí)鐘展開(kāi)為兩個(gè)時(shí)鐘，加上最后輸出消耗的一個(gè)時(shí)鐘，最終采用的是49 級(jí)全流水線結(jié)構(gòu)進(jìn)行實(shí)現(xiàn)，該優(yōu)化結(jié)構(gòu)如圖4 所示。

圖4 SHA3算法流水線優(yōu)化結(jié)構(gòu)圖

圖4 中算法的實(shí)現(xiàn)結(jié)構(gòu)與圖3 相比，雖然時(shí)鐘周期數(shù)增加了一倍，但是時(shí)間復(fù)雜度仍為Ο（n），即在相同頻率下，兩種結(jié)構(gòu)性能相同。但是，由于每一級(jí)流水線上的計(jì)算延時(shí)降低，使得該實(shí)現(xiàn)在FPGA 的綜合編譯結(jié)果中可以獲得更高的頻率表現(xiàn)，從而使SHA3 算法的性能得到進(jìn)一步提升。

3 實(shí)驗(yàn)結(jié)果與分析

本實(shí)驗(yàn)中的一塊FPGA 加速卡包含四顆FPGA 芯片，該芯片型號(hào)為Xilinx 公司的xcku060，其查找表LUTs 資源是331680，F(xiàn)lipFlops 寄存器資源是663360，軟件為Vivado 2018.2。實(shí)驗(yàn)對(duì)優(yōu)化后的SHA3 算法流水線進(jìn)行了仿真分析；并對(duì)比了SHA3 串行和兩種流水線資源使用情況；然后與GPU 在性能和功耗方面進(jìn)行了對(duì)比；最后與其他方案進(jìn)行了對(duì)比，說(shuō)明本文方案的有效性。

3.1 仿真分析

優(yōu)化后的SHA3 算法流水線仿真如圖5 所示。其中in_valid 為輸入有效信號(hào)；in_data 為輸入數(shù)據(jù)；out_valid 為輸出有效信號(hào)；out_data 為輸出數(shù)據(jù)；其他為中間結(jié)果信號(hào)。

圖5 SHA3算法仿真圖

從圖5 中可以看出，對(duì)于優(yōu)化后的SHA3 算法，當(dāng)連續(xù)輸入50 個(gè)數(shù)據(jù)后，在4866.191ns 連續(xù)產(chǎn)生50 組輸出，充分發(fā)揮了流水線并行的優(yōu)勢(shì)。

3.2 資源占用

這里分別采用串行和兩種流水線實(shí)現(xiàn)了SHA3，其資源占用對(duì)比如表1 所示。

表1 SHA3 串行和兩種流水線資源占用

從表1 中可以看出，串行SHA3 每24 個(gè)時(shí)鐘處理1 組數(shù)據(jù)，而流水線SHA3 可連續(xù)處理n 組數(shù)據(jù)，兩種流水線結(jié)構(gòu)分別從第25 個(gè)時(shí)鐘和第50 個(gè)時(shí)鐘開(kāi)始依次輸出它們的結(jié)果。由于優(yōu)化后的全流水線SHA3 算法通過(guò)增加流水線的級(jí)數(shù)來(lái)降低單個(gè)時(shí)鐘周期的延時(shí)，因此從實(shí)驗(yàn)結(jié)果也可以看出優(yōu)化后的實(shí)現(xiàn)與未優(yōu)化的相比具有更高的頻率。對(duì)應(yīng)的，SHA3 串行的處理速度為13 M 次/秒，而展開(kāi)流水線為415 M 次/秒，在處理速度上SHA3 流水線是串行的31.92 倍，具有明顯優(yōu)勢(shì)。

3.3 與GPU對(duì)比

描述SHA3 計(jì)算部件性能的指標(biāo)有速度、功率、能效比。其中能效比表示計(jì)算部件性能與功率之比，簡(jiǎn)記為EER（Energy Efficiency Ratio），計(jì)算公式3 如下：

表2 給出了本實(shí)驗(yàn)中的FPGA 加速卡與GPU 在各方面指標(biāo)上的對(duì)比。其中，單顆FPGA 芯片內(nèi)放置了4 個(gè)優(yōu)化后的SHA3 流水線模塊，工作頻率為200 MHz；GPU 型號(hào)為NVIDIA GeForce GTX 1080。

表2 FPGA 與GPU 指標(biāo)對(duì)比

從表2 中可以看出，F(xiàn)PGA 不僅性能較高，且功耗較低，具有很高的能效比，是GPU 的5.65 倍，更具有應(yīng)用價(jià)值。

3.4 與其他方案對(duì)比

與其他方案的對(duì)比如表3 所示。

通過(guò)對(duì)比可以發(fā)現(xiàn)，除文獻(xiàn)[3]外，本文實(shí)現(xiàn)的頻率優(yōu)于大多數(shù)方案。同時(shí)由于采用了全流水線結(jié)構(gòu)，本文實(shí)現(xiàn)的吞吐量高于其他方案，充分發(fā)揮了FPGA 的計(jì)算優(yōu)勢(shì)。

4 結(jié)語(yǔ)

本文提出了可重構(gòu)的SHA3 算法流水線結(jié)構(gòu)及其優(yōu)化、實(shí)現(xiàn)。通過(guò)對(duì)SHA3 算法的深入分析，使用高效能的FPGA 硬件計(jì)算平臺(tái)，縮短了SHA3 關(guān)鍵路徑，并以全流水線結(jié)構(gòu)和展開(kāi)的實(shí)現(xiàn)方式，有效地提高了工作頻率和計(jì)算速度，具有很高的實(shí)際應(yīng)用價(jià)值。

表3 與其他方案對(duì)比