0 引言

    2012年10月,，Keccak^[1]算法被美國NIST選為SHA3^[2](Secure Hash Algorithm 3)的標(biāo)準(zhǔn)算法。Keccak算法具有加密速度快,、散列值位分布均勻,、抗碰撞性強(qiáng)等特點(diǎn)，并且較其他雜湊算法具有更好的硬件實(shí)現(xiàn)性能,，因此Keccak算法得到了廣泛關(guān)注,。

    目前關(guān)于Keccak算法硬件實(shí)現(xiàn)的研究中，對填充過程的設(shè)計(jì)和完整算法電路的分析較少,，如文獻(xiàn)[3]對算法結(jié)構(gòu)的分析只基于了置換過程而沒有考慮填充過程,；并且這類研究聚焦于算法的實(shí)現(xiàn)性能而沒有考慮面積資源，如文獻(xiàn)[4]采用流水線實(shí)現(xiàn)置換過程,，文獻(xiàn)[5],、[6]將寄存器插入置換過程間減少關(guān)鍵路徑，文獻(xiàn)[7]串聯(lián)多級置換運(yùn)算單元,，這些提高性能方式都是以面積資源的增加為代價(jià),。

    本文通過分析Keccak完整算法流程，以32 bit作為輸入數(shù)據(jù)位寬,，對算法數(shù)據(jù)填充和狀態(tài)置換過程設(shè)計(jì)獨(dú)立的模塊,，簡化了控制結(jié)構(gòu)的復(fù)雜度，實(shí)現(xiàn)了加密過程中的數(shù)據(jù)填充與置換過程的并行執(zhí)行,；通過分析和實(shí)驗(yàn)結(jié)果可知,，本文設(shè)計(jì)的結(jié)構(gòu)平衡了性能和資源消耗，并具有較高的能效,。

1 Keccak算法過程描述

    Keccak算法是基于海綿結(jié)構(gòu)設(shè)計(jì)的雜湊算法,，海綿結(jié)構(gòu)具有可變長度輸入和任意長度輸出。

1.1 海綿結(jié)構(gòu)

    海綿結(jié)構(gòu)使用置換f建立具有可變輸入長度和任意輸出長度的函數(shù)[f,，pad,，r]，置換f對固定數(shù)量的比特進(jìn)行操作，其位寬為b,。

    如圖1所示,，海綿結(jié)構(gòu)的置換過程分為吸收階段和擠壓階段。

    吸收階段：輸入信息M根據(jù)規(guī)則pad進(jìn)行填充后得到信息P,，然后將P按照r bit長度劃分成消息分組M₀,，M₁，…,，M_n-1。M₀與置換的初始狀態(tài)(初始狀態(tài)為全0)的前r bit進(jìn)行異或,，后c bit保持不變,，將得到的b(b=r+c)比特狀態(tài)信息輸入到置換函數(shù)f；在吸收階段后續(xù)的每個(gè)置換函數(shù)f的輸入都是當(dāng)前消息分組M_i與上個(gè)置換函數(shù)f的輸出前r bit異或得到的結(jié)果,。當(dāng)最后一個(gè)消息分組M_n-1進(jìn)入置換函數(shù)產(chǎn)生結(jié)果后,，吸收階段結(jié)束。

    擠壓階段：根據(jù)使用者所需要的輸出信息Z,，從b bit狀態(tài)信息的前r bit進(jìn)行截?。划?dāng)所需輸出長度|Z|>r,，首先將當(dāng)前狀態(tài)信息的前r bit截取,，然后將當(dāng)前狀態(tài)數(shù)據(jù)輸入到置換函數(shù)f，從函數(shù)結(jié)果截取r bit,，直到達(dá)到使用者所需的輸出長度后,，擠壓階段結(jié)束。

1.2 填充規(guī)則

    Keccak算法的填充規(guī)則記為pad,，具體過程如下：

    在輸入消息M后添加單個(gè)比特1,，然后添加n比特0，最后添加單個(gè)比特1,，使得填充后的長度|P|為r的整數(shù)倍,。其中，n為滿足|M|+2+n≡0 mod r的最小整數(shù),；填充比特長度最短為2,，最長為r+1。

    基于海綿結(jié)構(gòu)的Keccak算法理論上可以生成任意長度的散列值,，但NIST為了配合SHA2散列值,，在SHA3標(biāo)準(zhǔn)中規(guī)定了4種模式。不同的模式下只有消息分組r與輸出長度Z的位寬不同,，具體數(shù)據(jù)如表1所示,。

1.3 置換過程

    Keccak算法的置換過程記為Keccak-f[b]，是針對狀態(tài)數(shù)組A的迭代過程，迭代輪數(shù)n_r=24,。狀態(tài)數(shù)組A是一個(gè)三維數(shù)組,，數(shù)組中的元素屬于GF[2]域，狀態(tài)數(shù)組也可以看出一個(gè)位寬為1 600 bit的比特串S,，狀態(tài)數(shù)組的置換函數(shù)f包括θ,、ρ、π,、χ,、ι 5個(gè)步驟。其詳細(xì)描述如下：

1.3.1 映射規(guī)則

    比特串S到狀態(tài)數(shù)組A的映射規(guī)則為A[x][y][z]=S[64×(5×y+x)+z],，其中(0≤x≤5,，0≤y<5，0≤Z<64),。示例如下：

1.3.2 步驟描述

    (1)步驟θ：

2 Keccak算法ASIC設(shè)計(jì)

    分析海綿體結(jié)構(gòu)和Keccak算法流程可知,，Keccak寄存填充過程與置換過程是能夠并行執(zhí)行的，其具體過程如圖2所示,。

    從圖2中看出,，前一組消息分組進(jìn)行置換時(shí)可以同時(shí)進(jìn)行第二個(gè)消息分組的寄存或填充，因此在Keccak硬件電路中設(shè)計(jì)填充模塊和置換模塊來并行執(zhí)行填充寄存過程和置換過程,。

    Keccak硬件完整電路結(jié)構(gòu)如圖3所示,，填充模塊用于外部數(shù)據(jù)的接收，消息分組的寄存和算法的填充過程,；置換模塊負(fù)責(zé)狀態(tài)數(shù)組的吸收擠壓過程和數(shù)據(jù)輸出過程,。

2.1 填充模塊

    在外部信號作用下，填充模塊每個(gè)時(shí)鐘周期接收串行輸入的32 bit消息數(shù)據(jù),，當(dāng)寄存的消息數(shù)據(jù)構(gòu)成一個(gè)r bit的消息分組后,，將寄存的消息分組送入空閑狀態(tài)的置換模塊；若外部信號顯示當(dāng)前為最后一個(gè)消息分組,，則需要先對該消息分組進(jìn)行填充,，此過程由填充狀態(tài)機(jī)進(jìn)行控制。

    填充模塊的內(nèi)部包括存儲當(dāng)前SHA3標(biāo)準(zhǔn)的模式寄存器,，存儲最后消息分組有效長度位信息的長度寄存器,， 存儲消息分組的填充寄存器，以及控制數(shù)據(jù)輸入或填充過程的狀態(tài)機(jī),。

    填充模塊的輸入信號包括寫信號Wen,、地址信號Addr、最后一個(gè)消息分組的標(biāo)志信號Last,、位寬為32 bit輸入數(shù)據(jù)Datain及來自填充模塊的運(yùn)算啟動(dòng)標(biāo)識信號start_Incore,。

    填充寄存器電路結(jié)構(gòu)如圖4所示,，填充寄存器由36個(gè)32 bit移位寄存器構(gòu)成，用于存儲外部輸入的消息分組和內(nèi)部產(chǎn)生的填充數(shù)據(jù),。當(dāng)外部32 bit數(shù)據(jù)Datain進(jìn)入寄存器后,，填充模塊內(nèi)部的計(jì)數(shù)器進(jìn)行計(jì)數(shù)操作，當(dāng)計(jì)數(shù)值達(dá)到當(dāng)前的SHA3模式所對應(yīng)的消息分組時(shí),，代表一個(gè)消息分組存儲完成,。若該過程中Last信號出現(xiàn)，由填充狀態(tài)機(jī)控制進(jìn)行填充操作,。通過對填充過程進(jìn)行分析,，得到可能出現(xiàn)的4種填充數(shù)據(jù)Fill_data，其數(shù)值如表4所示,。

    填充狀態(tài)機(jī)的跳轉(zhuǎn)是由模塊內(nèi)的計(jì)數(shù)器,、模式寄存器存儲數(shù)據(jù)、長度寄存器存儲數(shù)據(jù)控制,，狀態(tài)機(jī)的轉(zhuǎn)換圖如圖5所示。

    圖5中的各個(gè)狀態(tài)所代表的含義及功能如表5所示：Fill_S0代表狀態(tài)機(jī)空閑,，該狀態(tài)下填充模塊由外部控制接收消息分組數(shù)據(jù),、長度數(shù)據(jù)、模式數(shù)據(jù),；Fill_S1,、Fill_S2、Fill_S3,、Fill_S4是進(jìn)行數(shù)據(jù)填充的狀態(tài),；Fill_S5是數(shù)據(jù)準(zhǔn)備狀態(tài)，在該狀態(tài)下代表當(dāng)前的消息分組全部進(jìn)入填充寄存器,，等待送入置換模塊,。

2.2 置換模塊

    Keccak的置換模塊主要執(zhí)行狀態(tài)數(shù)組的存儲、置換以及數(shù)據(jù)輸出三個(gè)操作,。

    在置換模塊中,，設(shè)計(jì)了一組狀態(tài)寄存器，用于存儲25×32 bit狀態(tài)數(shù)組,，將置換函數(shù)映射成為θ,、ρ、π,、χ,、ι 5個(gè)運(yùn)算單元。置換模塊內(nèi)部的狀態(tài)機(jī)具有4個(gè)狀態(tài),，其狀態(tài)轉(zhuǎn)換圖分別如圖6所示,。

    圖6中的各個(gè)狀態(tài)所代表的含義及功能如表6所示：Incore_S0為空閑態(tài)，該狀態(tài)下模塊內(nèi)部不執(zhí)行任何操作；Inocre_S1狀態(tài)下狀態(tài)寄存器組中的數(shù)據(jù)與填充模塊存儲完畢的消息分組異或來完成狀態(tài)的更新,；Incore_S2狀態(tài)下,，狀態(tài)數(shù)組進(jìn)行24輪迭代置換操作；當(dāng)所有消息分組完成置換過程后,，進(jìn)入Incore_S3狀態(tài)等待數(shù)據(jù)輸出,。

3 Keccak硬件結(jié)構(gòu)能效分析

    Keccak算法電路的填充置換兩個(gè)過程結(jié)構(gòu)的面積開銷占比如表7所示。

    表7中的數(shù)據(jù)占比沒有包含電路中的控制部分,；填充過程的非組合邏輯面積開銷主要為填充寄存器,，置換過程的非組合邏輯面積開銷主要為狀態(tài)寄存器。

    目前Keccak算法實(shí)現(xiàn)區(qū)別主要在于置換結(jié)構(gòu),，圖7為三種主要實(shí)現(xiàn)方式,。

    圖7中基礎(chǔ)結(jié)構(gòu)是本文所使用的結(jié)構(gòu)，特點(diǎn)是資源占用率少,；展開結(jié)構(gòu)是將置換函數(shù)兩級級聯(lián),，通過時(shí)鐘周期的減少來提高吞吐率；流水線結(jié)構(gòu)是通過提高整個(gè)算法結(jié)構(gòu)頻率,，并采用流水線來執(zhí)行不同信息來提高吞吐率,。以基礎(chǔ)置換結(jié)構(gòu)的Keccak完整電路面積、頻率,、吞吐率,、能效為單位，其他兩結(jié)構(gòu)各數(shù)值如表8所示,。

    表8中將本文Keccak算法電路的面積,、頻率、吞吐率,、能效作為標(biāo)準(zhǔn),，比較了兩級的展開結(jié)構(gòu)和流水線結(jié)構(gòu)；由于輸入位寬為32 bit,，導(dǎo)致填充寄存過程時(shí)鐘周期多于置換過程,，因此展開結(jié)構(gòu)中置換過程時(shí)鐘周期的減少實(shí)際并沒有影響單個(gè)消息分組處理時(shí)鐘周期，所以該結(jié)構(gòu)吞吐率反而降低,。流水線結(jié)構(gòu)中增加的狀態(tài)寄存器必須放置在各步驟之間,，因此頻率并不能隨插入寄存器的數(shù)量提升；當(dāng)消息分組寄存填充所占時(shí)鐘周期大于置換過程迭代輪數(shù),，n級流水線結(jié)構(gòu)中需要n個(gè)填充寄存結(jié)構(gòu),，才能滿足數(shù)據(jù)填充過程進(jìn)行流水，因此流水線結(jié)構(gòu)面積開銷大,。

    綜合上述分析,，對于實(shí)現(xiàn)完整Keccak算法實(shí)現(xiàn),，置換過程的展開結(jié)構(gòu)和流水線結(jié)構(gòu)較基礎(chǔ)結(jié)構(gòu)能效反而降低。

4 KeccaK算法ASIC實(shí)現(xiàn)及性能評估

    本文提出的結(jié)構(gòu)和其他文獻(xiàn)結(jié)構(gòu)實(shí)現(xiàn)結(jié)果對比如表9和表10所示,。

    文獻(xiàn)[6]所設(shè)計(jì)的Keccak算法硬件電路采用64 bit輸入位寬,，置換過程采用三輪級聯(lián)展開。分析表8的數(shù)據(jù)中可知,，將置換過程級聯(lián)展開會消耗大量的面積資源,，雖然提高了吞吐率，但導(dǎo)致了整個(gè)硬件電路能效的降低,。從上表中數(shù)據(jù)分析得知,，本文結(jié)構(gòu)較文獻(xiàn)[6]結(jié)構(gòu)在能效上提高了約50%。

    文獻(xiàn)[5]采用了兩級流水線結(jié)構(gòu),，以面積資源換取了吞吐率的提高,，但是當(dāng)外界數(shù)據(jù)以單任務(wù)方式出現(xiàn)時(shí)，該結(jié)構(gòu)吞吐率會降低一倍,。從表中數(shù)據(jù)分析得到,，當(dāng)外界數(shù)據(jù)按多任務(wù)出現(xiàn)時(shí)，本文結(jié)構(gòu)與文獻(xiàn)[5]的流水線結(jié)構(gòu)能效相同,；當(dāng)外界數(shù)據(jù)按單任務(wù)出現(xiàn)時(shí),，本文結(jié)構(gòu)較文獻(xiàn)[5]的流水線結(jié)構(gòu)提高了約95%。

    從實(shí)驗(yàn)結(jié)果及對比分析中可以看出,，置換過程采用基本結(jié)構(gòu)實(shí)現(xiàn)的完整Keccak算法硬件電路具有較高能效。本文采用模塊化思想所設(shè)計(jì)的Keccak算法硬件電路具有資源面積開銷小,、能效高的特點(diǎn),。

參考文獻(xiàn)

[1] BERTONI G，DAEMEN J,，PEETERS M,，et al.Keccak[C].EUROCRYPT，2013：313-314.

[2] DWORKIN M J.SHA-3 standard：permutation-based hash and extendable-output functions[S].Federal Information Processing Standard(NIST-FIPS)-202,，2015.

[3] IOANNOU L,，MICHAIL H E，VOYIATZIS A G.High performance pipelined FPGA implementation of the SHA-3 hash algorithm[C].2015 4th Mediterranean Conference on Embedded Computing(MECO).IEEE,，2015.

[4] SHARMA J,，KOPPAD D.Low power and pipelined secure hashing algorithm-3(SHA-3)[C].India Conference.IEEE，2017.

[5] MESTIRI H,，KAHRI F,，BEDOUI M,et al.High throughput pipelined hardware implementation of the KECCAK hash function[C].International Symposium on Signal.IEEE，2017.

[6] Wu Xufan,，Li Shuoguo.High throughput design and implementation of SHA-3 hash algorithm[C].2017 International Conference on Electron Devices and Solid-State Circuits(EDSSC).IEEE,，2017.

[7] WONG M M,，HAJ-YAHYA J.A new high throughput and area efficient SHA-3 implementation[C].2018 IEEE International Symposium on Circuits and System，2018.

作者信息:

庹  釗,，陳  韜,，李  偉，南龍梅

(解放軍戰(zhàn)略支援部隊(duì)信息工程大學(xué) 密碼工程學(xué)院,，河南 鄭州450001)