4.3 SHA-3算法的硬件实现

可配置SHA-3的硬件结构由填充模块（Padding）、迭代运算模块（Transformation Round）、控制模块（Control）和截取模块（Truncating）四个部分组成，如图4-9所示。SHA-3启动后，随机数种子（Seed）首先通过寄存器进入填充模块。填充模块对随机数种子进行填充，填充的规则是“pad10*1”，填充完成后，会在数据末尾补0，使得数据长度为1600位。数据接下来会通过多路选择器（mux）进入迭代运算模块。迭代运算模块执行数据的迭代运算操作，迭代运算包含 θ、ρ、π、χ、τ 五个步骤。五个步骤执行完成后，数据通过寄存器进入数据分配器（dmux）。从数据分配器输出的数据会再次通过多路选择器进入迭代运算模块执行运算操作，此过程需要重复24轮。若SHA-3的模式为SHA3-224、SHA3-256、SHA3-383、SHA3-512中的任意一种，或者SHA-3的模式为SHAKE128、SHAKE256两者之一且同时满足挤压（Squeeze）次数设置为0，则24轮迭代运算完成后，数据通过数据分配器进入截取模块，截取模块截取特定的长度位输出即可。若SHA-3的模式为SHAKE128、SHAKE256两者之一，挤压次数设置为 n （ n ≠0），则迭代运算需执行（ n +1）*24次，每执行24轮，截取模块会产生一次特定长度位（ r 位）输出，一共生成（ n +1）* r 位随机数。

4.3.1 哈希函数

填充模块执行数据的填充操作，填充的规则是“pad10*1”，即先在输入数据的末尾添加单位1，然后在单位1后接若干位0，最后在若干位0的末尾再添加单位1，使得整个数据长度填充为 r 的最小整数倍。在执行“pad10*1”规则之前，需要在输入数据的末尾添加后缀，可扩展输出函数和加密散列函数的后缀不同，四种加密散列函数在填充前需要在末尾添加“01”，两种可扩展输出函数在填充前需要在末尾添加“1111”，即

式中， M 为输入任意字符数组或字节数组的长度； d 为所需的输出字节数。

根据Keccak官方的描述，算法对应的操作以字节为单位，且存储的格式为小端格式，即低字节数据存储在低地址位置。以消息“OK”为例，“O”对应的二进制ASCII码为“01001111”，“K”对应的二进制ASCII码为“01001011”，因此在小端存储格式中，“OK”对应的比特串为“1111001011010010”。若要对“OK”进行加密散列运算，以SHA3-256为例，填充的规则是SHA3-256（“OK”）=KECCAK[512]（“OK”||01，256），分组长度 r =1088，于是填充的序列如图4-10所示。若要对“OK”进行可扩展输出运算，以SHAKE128为例，填充的规则是SHAKE128（“OK”）=KECCAK[256]（“OK”||1111），分组长度 r =1344，于是填充的序列如图4-11所示。

根据SHA-3函数家族的填充规则和数据存储规则，SHA-3函数家族六种函数都分别对应一种填充模式，一共有六种填充模式（Padding1到Padding6），如图4-12所示。

由于消息的一个可显示字符对应8位二进制ASCII码，所以每种填充模式都有三种填充情况。对于加密散列函数，以SHA3-256（ r =1088）为例，Padding2对应的三种填充情况分别如下。

（1）若输入种子有效长度 l 小于或等于1072（即 r -16），则在数据末尾填充06（十六进制），06之后填充0，直至在第[1087：1080]位填充80（十六进制），如图4-13所示。

（2）若输入种子有效长度 l 等于1080（即 r -8），则在第[1087：1080]位填充86（十六进制），如图4-14所示。

（3）若输入种子有效长度 l 大于或等于1088（即 r ），则本次无填充，如图4-15所示。

对于可扩展输出函数，以SHAKE128（ r =1344）为例，Padding5对应的三种填充情况分别为：

（1）若输入种子有效长度 l 小于或等于1328（即 r -16），则在数据末尾填充1F（十六进制），1F之后填充0，直至在第[1343：1336]位填充80（十六进制），如图4-16所示。

（2）若输入种子有效长度 l 等于1336（即 r -8），则在第[1343：1336]位填充9F（十六进制），如图4-17所示。

（3）若输入种子有效长度 l 大于或等于1344（即 r ），则本次无填充，下一次挤压时在数据末尾按（1）或（2）填充，如图4-18所示。

SHA-3函数家族对应的六种填充模式和所有的填充情况归纳为表4-4。

4.3.2 迭代运算模块

作为SHA-3的核心运算单元，迭代运算模块是SHA-3内部数据量最大，同时也是运算最为复杂的一部分。迭代运算一共包括θ变换、ρ变换、π变换、χ变换、ι变换五个步骤。五个步骤依次执行，需要循环执行24轮。除了最后一个运算步骤是对64位数据的操作，其他四个步骤都是对1600位数据的操作。由于五个函数对应的函数涉及的运算都是1位之间的与、非、异或和循环移位操作，所以迭代运算模块最直接的实现方式是全组合逻辑设计。

如图4-19所示，为了方便数据处理，在设计这个模块时，将输入的1600位数据均分为25路： S ₀₀ 、 S ₁₀ 、 S ₂₀ 、…、 S ₄₄ 。每一路对应三维数据模型的“道”（Lane），数据线宽为64位。θ变换涉及移位和异或运算。1位数据进行 θ变换需通过5个异或门。ρ 变换和π 变换全部只涉及移位和旋转变换，不消耗门电路。χ变换涉及非、与、异或运算。1位数据进行χ变换需通过1个非门、1个与门和1个异或门。ι 变换只涉及异或运算。1位数据进行 ι 变换需通过1个异或门。

4.3.3 控制模块

控制模块由状态机和计数器设计。根据SHA-3模块的运算流程，状态机由五个状态组成：空闲（Idle）、读数据（Rd）、填充（Pad）、迭代计算（Calc）和写回（Wr）。图4-20为SHA-3状态转移图。

（1）Idle：空闲状态。当start为0时，模块不工作，为空闲状态。当start为1时，进入读数据状态。

（2）Rd：读数据状态。将以每周期64位的速度读取数据，读取的数据存入数据寄存器，数据读取完成后进入填充状态。

（3）Pad：填充状态。对有效数据进行填充，填充完成后进入迭代运算状态。

（4）Calc：迭代运算状态。对填充好的数据进行迭代运算，迭代运算需重复24次，24次计算完成后进入写回状态。

（5）Wr：写回状态。将迭代运算完成所需特定数据写入FIFO中。写入后，若SHA-3执行的函数为SHAKE128或SHAKE256，同时squeeze的值不为0，需要返回迭代运算状态再次进行数据运算。每次返回，squeeze的值减1，重复此过程，直至squeeze为0，将所有所需数据写入FIFO中，此时done为1，回到空闲状态。

4.3.4 截取模块

截取模块截取特定长度的数据写入FIFO中。截取模块对应的六种截取长度如图4-21所示。截取的特定长度根据SHA-3执行的函数决定：四种加密散列函数SHA3-224、SHA3-256、SHA3-384和SHA3-512截取的长度分别为224位、256位、384位和512位；两种可扩展输出函数SHAKE128和SHAKE256单次运算截取的长度分别为1344位和1088位。