0 引言

    2012年10月，Keccak^[1]算法被美国NIST选为SHA3^[2](Secure Hash Algorithm 3)的标准算法。Keccak算法具有加密速度快、散列值位分布均匀、抗碰撞性强等特点，并且较其他杂凑算法具有更好的硬件实现性能，因此Keccak算法得到了广泛关注。

    目前关于Keccak算法硬件实现的研究中，对填充过程的设计和完整算法电路的分析较少，如文献[3]对算法结构的分析只基于了置换过程而没有考虑填充过程；并且这类研究聚焦于算法的实现性能而没有考虑面积资源，如文献[4]采用流水线实现置换过程，文献[5]、[6]将寄存器插入置换过程间减少关键路径，文献[7]串联多级置换运算单元，这些提高性能方式都是以面积资源的增加为代价。

    本文通过分析Keccak完整算法流程，以32 bit作为输入数据位宽，对算法数据填充和状态置换过程设计独立的模块，简化了控制结构的复杂度，实现了加密过程中的数据填充与置换过程的并行执行；通过分析和实验结果可知，本文设计的结构平衡了性能和资源消耗，并具有较高的能效。

1 Keccak算法过程描述

    Keccak算法是基于海绵结构设计的杂凑算法，海绵结构具有可变长度输入和任意长度输出。

1.1 海绵结构

    海绵结构使用置换f建立具有可变输入长度和任意输出长度的函数[f，pad，r]，置换f对固定数量的比特进行操作，其位宽为b。

    如图1所示，海绵结构的置换过程分为吸收阶段和挤压阶段。

    吸收阶段：输入信息M根据规则pad进行填充后得到信息P，然后将P按照r bit长度划分成消息分组M₀，M₁，…，M_n-1。M₀与置换的初始状态(初始状态为全0)的前r bit进行异或，后c bit保持不变，将得到的b(b=r+c)比特状态信息输入到置换函数f；在吸收阶段后续的每个置换函数f的输入都是当前消息分组M_i与上个置换函数f的输出前r bit异或得到的结果。当最后一个消息分组M_n-1进入置换函数产生结果后，吸收阶段结束。

    挤压阶段：根据使用者所需要的输出信息Z，从b bit状态信息的前r bit进行截取；当所需输出长度|Z|>r，首先将当前状态信息的前r bit截取，然后将当前状态数据输入到置换函数f，从函数结果截取r bit，直到达到使用者所需的输出长度后，挤压阶段结束。

1.2 填充规则

    Keccak算法的填充规则记为pad，具体过程如下：

    在输入消息M后添加单个比特1，然后添加n比特0，最后添加单个比特1，使得填充后的长度|P|为r的整数倍。其中，n为满足|M|+2+n≡0 mod r的最小整数；填充比特长度最短为2，最长为r+1。

    基于海绵结构的Keccak算法理论上可以生成任意长度的散列值，但NIST为了配合SHA2散列值，在SHA3标准中规定了4种模式。不同的模式下只有消息分组r与输出长度Z的位宽不同，具体数据如表1所示。

1.3 置换过程

    Keccak算法的置换过程记为Keccak-f[b]，是针对状态数组A的迭代过程，迭代轮数n_r=24。状态数组A是一个三维数组，数组中的元素属于GF[2]域，状态数组也可以看出一个位宽为1 600 bit的比特串S，状态数组的置换函数f包括θ、ρ、π、χ、ι 5个步骤。其详细描述如下：

1.3.1 映射规则

    比特串S到状态数组A的映射规则为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设计

    分析海绵体结构和Keccak算法流程可知，Keccak寄存填充过程与置换过程是能够并行执行的，其具体过程如图2所示。

    从图2中看出，前一组消息分组进行置换时可以同时进行第二个消息分组的寄存或填充，因此在Keccak硬件电路中设计填充模块和置换模块来并行执行填充寄存过程和置换过程。

    Keccak硬件完整电路结构如图3所示，填充模块用于外部数据的接收，消息分组的寄存和算法的填充过程；置换模块负责状态数组的吸收挤压过程和数据输出过程。

2.1 填充模块

    在外部信号作用下，填充模块每个时钟周期接收串行输入的32 bit消息数据，当寄存的消息数据构成一个r bit的消息分组后，将寄存的消息分组送入空闲状态的置换模块；若外部信号显示当前为最后一个消息分组，则需要先对该消息分组进行填充，此过程由填充状态机进行控制。

    填充模块的内部包括存储当前SHA3标准的模式寄存器，存储最后消息分组有效长度位信息的长度寄存器， 存储消息分组的填充寄存器，以及控制数据输入或填充过程的状态机。

    填充模块的输入信号包括写信号Wen、地址信号Addr、最后一个消息分组的标志信号Last、位宽为32 bit输入数据Datain及来自填充模块的运算启动标识信号start_Incore。

    填充寄存器电路结构如图4所示，填充寄存器由36个32 bit移位寄存器构成，用于存储外部输入的消息分组和内部产生的填充数据。当外部32 bit数据Datain进入寄存器后，填充模块内部的计数器进行计数操作，当计数值达到当前的SHA3模式所对应的消息分组时，代表一个消息分组存储完成。若该过程中Last信号出现，由填充状态机控制进行填充操作。通过对填充过程进行分析，得到可能出现的4种填充数据Fill_data，其数值如表4所示。

    填充状态机的跳转是由模块内的计数器、模式寄存器存储数据、长度寄存器存储数据控制，状态机的转换图如图5所示。

    图5中的各个状态所代表的含义及功能如表5所示：Fill_S0代表状态机空闲，该状态下填充模块由外部控制接收消息分组数据、长度数据、模式数据；Fill_S1、Fill_S2、Fill_S3、Fill_S4是进行数据填充的状态；Fill_S5是数据准备状态，在该状态下代表当前的消息分组全部进入填充寄存器，等待送入置换模块。

2.2 置换模块

    Keccak的置换模块主要执行状态数组的存储、置换以及数据输出三个操作。

    在置换模块中，设计了一组状态寄存器，用于存储25×32 bit状态数组，将置换函数映射成为θ、ρ、π、χ、ι 5个运算单元。置换模块内部的状态机具有4个状态，其状态转换图分别如图6所示。

    图6中的各个状态所代表的含义及功能如表6所示：Incore_S0为空闲态，该状态下模块内部不执行任何操作；Inocre_S1状态下状态寄存器组中的数据与填充模块存储完毕的消息分组异或来完成状态的更新；Incore_S2状态下，状态数组进行24轮迭代置换操作；当所有消息分组完成置换过程后，进入Incore_S3状态等待数据输出。

3 Keccak硬件结构能效分析

    Keccak算法电路的填充置换两个过程结构的面积开销占比如表7所示。

    表7中的数据占比没有包含电路中的控制部分；填充过程的非组合逻辑面积开销主要为填充寄存器，置换过程的非组合逻辑面积开销主要为状态寄存器。

    目前Keccak算法实现区别主要在于置换结构，图7为三种主要实现方式。

    图7中基础结构是本文所使用的结构，特点是资源占用率少；展开结构是将置换函数两级级联，通过时钟周期的减少来提高吞吐率；流水线结构是通过提高整个算法结构频率，并采用流水线来执行不同信息来提高吞吐率。以基础置换结构的Keccak完整电路面积、频率、吞吐率、能效为单位，其他两结构各数值如表8所示。

    表8中将本文Keccak算法电路的面积、频率、吞吐率、能效作为标准，比较了两级的展开结构和流水线结构；由于输入位宽为32 bit，导致填充寄存过程时钟周期多于置换过程，因此展开结构中置换过程时钟周期的减少实际并没有影响单个消息分组处理时钟周期，所以该结构吞吐率反而降低。流水线结构中增加的状态寄存器必须放置在各步骤之间，因此频率并不能随插入寄存器的数量提升；当消息分组寄存填充所占时钟周期大于置换过程迭代轮数，n级流水线结构中需要n个填充寄存结构，才能满足数据填充过程进行流水，因此流水线结构面积开销大。

    综合上述分析，对于实现完整Keccak算法实现，置换过程的展开结构和流水线结构较基础结构能效反而降低。

4 KeccaK算法ASIC实现及性能评估

    本文提出的结构和其他文献结构实现结果对比如表9和表10所示。

    文献[6]所设计的Keccak算法硬件电路采用64 bit输入位宽，置换过程采用三轮级联展开。分析表8的数据中可知，将置换过程级联展开会消耗大量的面积资源，虽然提高了吞吐率，但导致了整个硬件电路能效的降低。从上表中数据分析得知，本文结构较文献[6]结构在能效上提高了约50%。

    文献[5]采用了两级流水线结构，以面积资源换取了吞吐率的提高，但是当外界数据以单任务方式出现时，该结构吞吐率会降低一倍。从表中数据分析得到，当外界数据按多任务出现时，本文结构与文献[5]的流水线结构能效相同；当外界数据按单任务出现时，本文结构较文献[5]的流水线结构提高了约95%。

    从实验结果及对比分析中可以看出，置换过程采用基本结构实现的完整Keccak算法硬件电路具有较高能效。本文采用模块化思想所设计的Keccak算法硬件电路具有资源面积开销小、能效高的特点。

参考文献

[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.

作者信息:

庹  钊，陈  韬，李  伟，南龙梅

(解放军战略支援部队信息工程大学 密码工程学院，河南 郑州450001)