0 引言

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

    本文通過分析Keccak完整算法流程，以32 bit作為輸入數(shù)據(jù)位寬，對(duì)算法數(shù)據(jù)填充和狀態(tài)置換過程設(shè)計(jì)獨(dú)立的模塊，簡(jiǎn)化了控制結(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)具有可變長(zhǎng)度輸入和任意長(zhǎng)度輸出。

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

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

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

    吸收階段：輸入信息M根據(jù)規(guī)則pad進(jìn)行填充后得到信息P，然后將P按照r bit長(zhǎng)度劃分成消息分組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)所需輸出長(zhǎng)度|Z|>r，首先將當(dāng)前狀態(tài)信息的前r bit截取，然后將當(dāng)前狀態(tài)數(shù)據(jù)輸入到置換函數(shù)f，從函數(shù)結(jié)果截取r bit，直到達(dá)到使用者所需的輸出長(zhǎng)度后，擠壓階段結(jié)束。

1.2 填充規(guī)則

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

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

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

1.3 置換過程

    Keccak算法的置換過程記為Keccak-f[b]，是針對(duì)狀態(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 填充模塊

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

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

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

    填充寄存器電路結(jié)構(gòu)如圖4所示，填充寄存器由36個(gè)32 bit移位寄存器構(gòu)成，用于存儲(chǔ)外部輸入的消息分組和內(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模式所對(duì)應(yīng)的消息分組時(shí)，代表一個(gè)消息分組存儲(chǔ)完成。若該過程中Last信號(hào)出現(xiàn)，由填充狀態(tài)機(jī)控制進(jìn)行填充操作。通過對(duì)填充過程進(jìn)行分析，得到可能出現(xiàn)的4種填充數(shù)據(jù)Fill_data，其數(shù)值如表4所示。

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

    圖5中的各個(gè)狀態(tài)所代表的含義及功能如表5所示：Fill_S0代表狀態(tài)機(jī)空閑，該狀態(tài)下填充模塊由外部控制接收消息分組數(shù)據(jù)、長(zhǎng)度數(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ù)組的存儲(chǔ)、置換以及數(shù)據(jù)輸出三個(gè)操作。

    在置換模塊中，設(shè)計(jì)了一組狀態(tài)寄存器，用于存儲(chǔ)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ù)與填充模塊存儲(chǔ)完畢的消息分組異或來完成狀態(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ù)兩級(jí)級(jí)聯(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)，比較了兩級(jí)的展開結(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級(jí)流水線結(jié)構(gòu)中需要n個(gè)填充寄存結(jié)構(gòu)，才能滿足數(shù)據(jù)填充過程進(jìn)行流水，因此流水線結(jié)構(gòu)面積開銷大。

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

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

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

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

    文獻(xiàn)[5]采用了兩級(jí)流水線結(jié)構(gòu)，以面積資源換取了吞吐率的提高，但是當(dāng)外界數(shù)據(jù)以單任務(wù)方式出現(xiàn)時(shí)，該結(jié)構(gòu)吞吐率會(huì)降低一倍。從表中數(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é)果及對(duì)比分析中可以看出，置換過程采用基本結(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)