馬占剛 李婷婷 曹喜信,?

1.集成電路和智能系統(tǒng)系, 北京大學(xué)軟件與微電子學(xué)院, 北京 100871; 2.鄭州職業(yè)技術(shù)學(xué)院, 鄭州 450000;? 通信作者, E-mail: cxx@ss.pku.edu.cn

SHA2[1]是美國國家標(biāo)準(zhǔn)與技術(shù)研究院(NIST)2001年發(fā)布的哈希算法, 作為 SHA1[2]的替代哈希算法, 包括 SHA224, SHA256, SHA384, SHA512,SHA512/224 和 SHA512/256 等 6種不同的算法標(biāo)準(zhǔn),廣泛應(yīng)用于數(shù)字簽名與驗證、消息認(rèn)證碼生成和驗證以及偽隨機數(shù)生成等領(lǐng)域。

很多應(yīng)用(如公共密鑰設(shè)施(PKI)[3], IPSec[4],SSL/TLS[5]和 802.16 標(biāo)準(zhǔn)[6])都包含數(shù)字認(rèn)證、數(shù)字簽名和偽隨機數(shù)生成等服務(wù)。這些服務(wù)在進(jìn)行過程中, 對數(shù)據(jù)進(jìn)行哈希計算是特別關(guān)鍵的步驟。當(dāng)具有安全保護(hù)功能應(yīng)用處理的用戶數(shù)據(jù)比較多時, 特別是擁有大量客戶端的服務(wù)器, 對處理數(shù)據(jù)的吞吐率有很高的要求, 而應(yīng)用的吞吐率往往由哈希函數(shù)的吞吐率決定。

基于處理速度和安全保護(hù)方面的考慮, 產(chǎn)業(yè)界很多公司采用硬件電路實現(xiàn)哈希函數(shù), 例如NASA只授權(quán)使用特定的硬件電路對關(guān)鍵數(shù)據(jù)進(jìn)行加密。

隨著區(qū)塊鏈技術(shù)[7]的興起, 大量的數(shù)據(jù)完整性驗證、數(shù)字簽名和偽隨機數(shù)生成等功能應(yīng)用到區(qū)塊鏈的底層計算中。具有完整性驗證和數(shù)據(jù)壓縮功能的哈希計算在交易和區(qū)塊的同步過程中是必不可少的環(huán)節(jié)。隨著通信技術(shù)的發(fā)展和區(qū)塊鏈共識算法的進(jìn)化, 網(wǎng)絡(luò)傳輸過程的延遲和共識機制對數(shù)據(jù)同步的影響越來越小, 而節(jié)點對交易和區(qū)塊的驗證計算對數(shù)據(jù)同步的影響越來越大。所以, 哈希計算硬件加速器性能的提升對區(qū)塊鏈交易和區(qū)塊驗證速度的提升有較大的幫助, 從而對促進(jìn)區(qū)塊鏈技術(shù)的商業(yè)應(yīng)用落地有一定的幫助。

1 SHA2硬件電路及相關(guān)研究

為了提升 SHA2 哈希計算的性能, 產(chǎn)業(yè)界和學(xué)術(shù)界對哈希函數(shù)硬件電路的優(yōu)化集中在結(jié)構(gòu)優(yōu)化和路徑延遲優(yōu)化兩個方面。從基本迭代結(jié)構(gòu), 到部分展開結(jié)構(gòu), SHA2 硬件電路的優(yōu)化方案不斷演進(jìn)。為減少關(guān)鍵路徑上的路徑延遲, 各種技術(shù)(如延遲均衡和加法器進(jìn)位鏈優(yōu)化(CSA 等))不斷被采用。

1.1 基本迭代架構(gòu)

Roar 等[8]提出基本迭代結(jié)構(gòu)的 SHA2 硬件電路,相對于軟件加密方案, 明顯地提高了處理速度, 但具有 7個加法器的關(guān)鍵路徑太長, 路徑延遲也比較大, 限制電路性能的提高。

1.2 全展開結(jié)構(gòu)

Deepakumara 等[9]利用全展開結(jié)構(gòu), 使 MD5 硬件電路的計算吞吐率得到明顯提升, 但因關(guān)鍵路徑太長而限制了電路工作頻率的提高。然而, 它為進(jìn)一步提高 SHA2 硬件電路的性能提供了一種與以往不同的思路——展開結(jié)構(gòu)。

1.3 部分展開結(jié)構(gòu)

為了提升單個消息哈希計算的性能和緩解全展開結(jié)構(gòu)中關(guān)鍵路徑太長的問題, Michail 等[10–11]和Dadda 等[12]采用部分展開結(jié)構(gòu)來提升 SHA2 電路的處理性能。這種結(jié)構(gòu)每個時鐘周期處理k輪哈希變換, 計算一次消息摘要迭代的時鐘周期縮小為原來的 1/k。

這種方法為相鄰兩輪哈希變換的一系列運算的整合優(yōu)化提供了可能性, 以每個周期展開兩輪哈希變換為例, 其關(guān)鍵路徑上串聯(lián) 6個加法器, 路徑延遲在很大程度上把電路工作頻率限制在較低的水平, 特別是在 SHA2-512 處理時, 6個串聯(lián)的 64 位加法器的路徑延遲更大。

基于展開系數(shù)為 2 的 SHA2 部分展開結(jié)構(gòu), 雖然 Michail 等[10–11]和 Dadda 等[12]的電路不同, 但縮短關(guān)鍵路徑的思路大體上相同。1) 為了縮短兩輪哈希變換的關(guān)鍵路徑, 把每個周期的兩輪哈希變換處理分為前處理和后處理, 兩個模塊都采用準(zhǔn)流水線結(jié)構(gòu)。2) 由于所有Wt在迭代變換前可以預(yù)先計算都得到, 并且常數(shù)Kt是基于迭代次數(shù)的先驗值,所以Wt與Kt的求和可以在At和Et的計算路徑之外提前運算, 并將求和結(jié)果存在中間寄存器中, 以備At和Et的計算之用。3) 采用多操作數(shù)加法器代替兩操作數(shù)加法器, 從而減少多個串聯(lián)的加法器進(jìn)位鏈的個數(shù), 減少串聯(lián)求和運算中進(jìn)位鏈對關(guān)鍵路徑的影響。

Michail 等[10–11]和 Dadda 等[12]提 出 的 SHA256硬件優(yōu)化方案都可以顯著地提高 SHA256 硬件加速引擎的吞吐率, 但提出的“連接預(yù)計算和后計算兩級準(zhǔn)流水結(jié)構(gòu)”并不是真正的流水線結(jié)構(gòu), 實際上還是平均每個時鐘周期處理一輪 SHA2 運算, 不能充分發(fā)揮“部分展開結(jié)構(gòu)”成倍提升性能的效果。

2 提出的優(yōu)化方案

目前, SHA2 系列哈希函數(shù)在區(qū)塊鏈技術(shù)中得到廣泛的應(yīng)用。為了滿足區(qū)塊鏈對 SHA2 系列不同哈希函數(shù)的高性能計算需求, 本文分別從系統(tǒng)結(jié)構(gòu)和微觀計算方面做了相應(yīng)的改進(jìn)。

2.1 優(yōu)化的系統(tǒng)架構(gòu)

如圖1 所示, 優(yōu)化的 SHA2 硬件加速器的系統(tǒng)架構(gòu)包括消息填充模塊、消息乒乓緩存器和消息迭代壓縮模塊。通過采用乒乓緩存器、消息填充模塊和消息迭代壓縮模塊, 可以實現(xiàn)兩級流水處理, 流水線的處理級別是一個包含 16個消息字的消息塊。對待壓縮的源數(shù)據(jù), 首先由填充單元對源數(shù)據(jù)進(jìn)行數(shù)據(jù)填充和分塊(每個消息塊包含 16個消息字), 寫入填充數(shù)據(jù)的 2 Kb 乒乓緩存中(2 Kb 是 SHA384/SHA-512 處理的兩個完整消息塊的容量)。只要填充數(shù)據(jù)的乒乓緩存中含有一個完成的消息塊, 迭代壓縮模塊就可以開始進(jìn)行迭代處理。迭代壓縮模塊每個時鐘周期處理兩個哈希變換, 對應(yīng)地, 每個時鐘周期從填充乒乓緩存讀出兩個消息字。迭代壓縮模塊中, 8個 64 位寄存器 a~h 用來存儲哈希迭代處理中的中間狀態(tài), 8個 64 位寄存器 h0~h7 用來存儲消息塊的哈希摘要值, 16個 64 位寄存器 w0~w15 用來存儲消息字或者擴展消息字, 控制模塊負(fù)責(zé)迭代輪次的控制、K值的讀取以及寄存器 a~h、h0~h7和 w0~w15 的讀寫等。

圖1 優(yōu)化的SHA2硬件加速器的系統(tǒng)架構(gòu)Fig.1 System architecture of proposed SHA2 hardware accelerator

SHA2 哈希計算引擎不僅可以支持對消息進(jìn)行SHA2 系列哈希函數(shù)的運算, 還可以支持對消息進(jìn)行 SHA2 系列哈希函數(shù)的雙重運算。哈希函數(shù)的雙重運算或者雙重哈希, 是將由哈希函數(shù)計算得到消息的哈希摘要作為消息, 并對之進(jìn)行哈希函數(shù)處理。在迭代壓縮單元的控制器的控制下, 把哈希摘要 h0, h1, …, h7 作為消息, 并對其進(jìn)行迭代哈希變換。

2.2 優(yōu)化的哈希迭代

本文采用如下更加優(yōu)化的技術(shù)來實現(xiàn) SHA2 計算引擎的性能的提升。

2.2.1 兩輪展開的哈希兩級流水架構(gòu)

采用預(yù)計算時序均衡技術(shù), 把兩輪展開的哈希迭代運算均勻地分為預(yù)計算和后計算兩部分, 并將這兩部分計算分別作為流水線處理的兩級電路。預(yù)計算和后計算兩級流水電路的均勻劃分使流水線電路的時序更加均衡, 圖2 示意兩輪 SHA2 系列哈希函數(shù)計算部分的劃分。預(yù)計算部分可由式(1)~(4)表示:

圖2 預(yù)計算和后計算的流水線結(jié)構(gòu)Fig.2Pipeline diagram of pre-computationand pos-computation

后計算部分由式(5)~(8)表示:

式(1)~(8)都是多操作數(shù)的求和計算。通過采用新型的進(jìn)位鏈更短的多加數(shù)求和計算技術(shù), 這些求和計算的關(guān)鍵路徑得以縮短, 從而實現(xiàn)在較高的時鐘頻率下, 展開的兩輪哈希迭代運算可以滿足時序要求的目標(biāo)。

2.2.2 使用多操作數(shù)加法壓縮器

預(yù)計算部分的最長路徑為計算 V0 和 V1 的路徑, 是 6個加數(shù)求和的運算。對 6個加數(shù)求和的硬件電路由多操作數(shù)加法壓縮器和快速加法器組成。如圖3 所示, 6個操作數(shù)求和的電路可以由 3:2 壓縮器、4:2 壓縮器和 5:2 壓縮器來實現(xiàn)。表1 描述門數(shù)以及在關(guān)鍵路徑延遲的門數(shù)。

圖3 實現(xiàn)預(yù)計算壓縮器和加法器的不同組合Fig.3 Combinations of compressors and adder used to perform pre-computation

表1 不同壓縮器的門數(shù)Table 1 Gate count of various compressors

從表2 可以看出, 采用 4:2 壓縮器、3:2 壓縮器和快速加法器的方案是實現(xiàn)預(yù)計算部分的 V0 和 V1計算的最優(yōu)方案, 臨界路徑短、成本低。

表2 預(yù)計算單元不同方案的路徑延遲和門數(shù)Table 2 Path delay and gate count of different schemes for pre-computation unit

后計算部分是兩塊相同的哈希計算電路的級聯(lián)運算, 它們分別負(fù)責(zé) post0_A, post0_E, post0_Hx0和 post0_Hx1 的計算與 post1_A, post1_E, post1_Hx0和 post1_Hx1 的計算。如圖4 所示, 通過對推導(dǎo)postX_Hx0 和 postX_A 的路徑的分析, 可以確定采用 4:2 壓縮器、3:2 壓縮器和快速加法器計算 postX_Hx0 和 postX_A 的方案最優(yōu)。采用 3:2 壓縮器和快速加法器計算 postX_Hx0 和 postX_E 的方案是最優(yōu)方案, 關(guān)鍵路徑延遲也最小。

圖4 后計算中使用的多操作數(shù)加法Fig.4 Mult-operand addition used in post-computation

2.2.3 4:2/3:2 壓 縮 器 用 XOR-XNOR 和 MUX 代 替XOR 門

由于 XOR-XNOR 組合門和 MUX 門的延遲時間小于 XOR 門[13], 因此本文使用 XOR-XNOR 組合門和 MUX 門替代 4:2 壓縮器和 3:2 壓縮器的 XOR門, 以減小 4:2 壓縮器和 3:2 壓縮器的延遲。

2.2.4 快速加法器

連波進(jìn)位加法器(RCA)的進(jìn)位鏈延遲與加法器的位數(shù)成正比, 所用的硬件資源也與位數(shù)成正比。超前進(jìn)位加法器(CLA)的進(jìn)位鏈關(guān)鍵路徑與位數(shù)無關(guān), 計算進(jìn)位輸出的延遲固定為 3 級門延遲, 如果擴大加法器位寬, 則電路就變得非常復(fù)雜。32 位或 64 位加法運算通常是由小的超前進(jìn)位加法器(4 位或 8 位超前進(jìn)位加法器)串聯(lián)而成的傳播進(jìn)位加法器。選擇進(jìn)位加法器首先把進(jìn)位分別為 0 和 1 的兩個求和結(jié)果同時計算出來, 然后再利用進(jìn)位輸入值, 選擇相應(yīng)的結(jié)果作為最終結(jié)果。關(guān)鍵路徑主要由低位的加法器和高位選擇進(jìn)位加法器引入的多路器組成, 其延遲遠(yuǎn)低于超前進(jìn)位加法器的關(guān)鍵路徑延遲, 但在同樣位數(shù)的加法器中, 選擇進(jìn)位加法器所用的門數(shù)比超前進(jìn)位加法器多。綜合考慮時序和面積兩個因素, 我們采用超前進(jìn)位加法器、傳播進(jìn)位加法器和選擇進(jìn)位加法器的組合方式設(shè)計, 可以適應(yīng)不同需求的 64 位快速加法器。

表3 列出不同快速加法器的性能和資源。通過分析, 我們采用 3 對 16 位傳播進(jìn)位加法器, 分別基于進(jìn)位輸入為 0 和 1 兩種情況, 對高 48 位操作數(shù)實現(xiàn)進(jìn)位選擇加法器(其中 16 位傳播進(jìn)位加法器由兩個 8 位超前進(jìn)位加法器組成)來實現(xiàn)加法器的快速運算。加法器的速度提升以增加 3個 8 位超前進(jìn)位加法器為代價來換取, 因此只用于后運算部分的關(guān)鍵路徑 post0_A, post0_E, post1_A, post1_E, post0_hx0 以 及 post0_hx1, post1_hx0 和 post1_hx1 的 計算。在預(yù)計算部分的兩輸入加法運算, 可以使用 64 位 FastAdder (8 位 CLA 和 32 位 CPA)或 64 位超前進(jìn)位加法器。

表3 不同快速加法器的性能和資源Table 3 Performance and resources of various fast adders

為了均衡預(yù)計算和后計算的延遲, 選擇64Fast-Adder (8 位 CLA 和 64 位 C PA)作為預(yù)計算的加法器,選擇 64FastAdder (8 位 CLA 和 16 位 CPA)作為 后計算部分中計算 post0_A, post0_E, post1_A 和 post1_E的加法器, 計算 post0_hx0 和 post0_hx1 的加法器選擇 64FastAdder (8 位 CLA 和 64 位 CPA), 計算 post1_hx0 和 post1_hx1 的 加 法 器 選 擇 64FastAdder (8 位CLA 和 16 位 CPA), 使預(yù)計算和后計算的延遲值在32個門延遲左右。在滿足時序要求的前提下, 幾條計算路徑中不使用統(tǒng)一的快速加法器, 可以在時序要求不太高的路徑采用超前進(jìn)位加法器, 從而可以節(jié)省硬件資源。

基于以上分析, SHA2 的迭代壓縮模塊采用兩輪哈希變換展開技術(shù), 可以使每一時鐘周期處理兩輪哈希變換, 性能比傳統(tǒng)的每個時鐘周期處理一輪哈希變換方案提升一倍。SHA2 的迭代壓縮模塊采用預(yù)計算和后計算的兩級流水線結(jié)構(gòu)、與進(jìn)位無關(guān)的多操作數(shù)加法壓縮器技術(shù)和快速加法器技術(shù)等,使得哈希變換部分的關(guān)鍵路徑變短, 可以使迭代壓縮模塊工作在更高時鐘頻率。通過這兩個方面的優(yōu)化, 哈希計算引擎的吞吐率得到大幅提升。

3 實驗和討論

在本文提出的方案中, 填充部分和迭代部分都以流水線的形式來實現(xiàn), 所以 SHA2 迭代部分所需的消息字已經(jīng)在填充乒乓緩沖區(qū)中準(zhǔn)備好, 無需等待填充處理。因此, 對 SHA2 單哈希的性能分析主要基于 SHA2 迭代的處理速度。

SHA2 硬件加速器的吞吐率可以用式(9)表示:

其中, BlockSize 表示消息塊的大小,f表示工作頻率,ClockCycles 表示用于獲取最終摘要的時鐘周期。

根據(jù) SHA2 的算法, 我們可以知道 SHA224 和SHA384 的 吞 吐 率 分 別 與 SHA256 和 SHA512 的 吞吐率一致。因此, 我們選用 SHA256 和 SHA512 兩種哈希算法來完成 SHA2 硬件加速器的性能測試。該硬件 SHA2 加速器使用 Xilinx FPGA (Virtex 6 xc6vlx760) 進(jìn)行測試, 工作頻率為 92.1 MHz, 成本為 8216 LUTs。通過測試, 可以得到 SHA256 和SHA512 的吞吐率, 見表4。

表4 基于 Virtex 6 的 SHA2 單哈希和雙哈希吞吐率Table 4 Throughput of SHA2 single Hash and double hash based on Virtex 6

SHA256 與文獻(xiàn)[14]的性能比較如表5 所示。雖然文獻(xiàn)[14]的工作頻率比本文方案高, 但其處理 SHA256 的吞吐率比本文方案低。

表5 SHA256 的吞吐率比較Table 5 Throughput comparison of SHA256

SHA512 與文獻(xiàn)[15]的計算性能比較如表6 所示。可以看出, 本文在處理 SHA512 時的工作頻率和吞吐率都明顯超過文獻(xiàn)[15]。

表6 SHA512的吞吐率比較Table 6 Throughput comparison of SHA512

根據(jù)上述分析, 在硬件共享情況下, 該 SHA2硬件加速器顯著地提升了 SHA2 系列哈希計算的性能。

4 總結(jié)

針對以往 SHA2 硬件吞吐率難以提升的問題,本文提出一種新的改進(jìn)方法, 還提供了一種能夠滿足區(qū)塊鏈 SHA2 雙哈希計算需求的快速實現(xiàn)方法。

1) 使用乒乓緩存存儲前期生成的 SHA2 填充數(shù)據(jù), 使 SHA2 填充處理和迭代運算的兩個硬件電路以兩級流的形式并行處理。

2) 提取兩輪哈希迭代中的獨立元素作為預(yù)處理部分, 與迭代運算的后處理部分形成真正的流水線處理, 成功地避免以往研究中提出的偽流水線設(shè)計。

3) 在前處理部分和后處理部分, 采用 3:2/4:2 壓縮器和無進(jìn)位鏈的快速加法器來縮短關(guān)鍵路徑, 減少關(guān)鍵路徑延遲。

為了適應(yīng)區(qū)塊鏈技術(shù)的 SHA2 雙哈希要求, 本文還支持對計算出的源操作數(shù)的摘要進(jìn)行二次哈希, 以便得到雙哈希計算的最終結(jié)果, 減少外部存儲器和相關(guān)數(shù)據(jù)處理的訪問時間, 提高了 SHA2 雙哈希計算的處理速度。這些方法對于提高哈希函數(shù)獨立硬件(如 SHA256, SH384, SHA512甚至SM3)的性能有參考意義。