4.2 SHA-3算法分析

4.2.1 哈希函数

哈希函数的输入值被称为消息（Message），消息的长度是任意的；输出值被称为摘要（Digest）或哈希值，摘要的长度是固定的。如图4-1所示，哈希函数通过特定的算法将消息转化为摘要。

将任意长度的消息记为 m ，固定长度的摘要记为 d ，散列算法记为 h ，则哈希函数可表示为

为了保证安全性，在加密协议中哈希函数还必须具有以下三种属性 ^[28] ：

（1）抗第一原象性（单向性）：已知一个摘要 d ，求解出满足 d = h （ m ）的消息 m 在计算上是不可行的。

（2）抗第二原象性（弱抗冲突性）：两个不同消息不会映射相同摘要值，即给定消息 m ₁ ，找到另一个消息 m （ ₂ m ₁ ≠ m ₂ ），满足 h （ m ₁ ）= h （ m ₂ ），在计算上是不可行的。

（3）抗冲突性（强抗冲突性）：找到满足 h （ m ₁ ）= h （ m ₂ ）的两个不同的消息 m ₁ ≠ m ₂ 在计算上是不可行的。

哈希函数的三种核心属性如图4-2所示。

4.2.2 参数构造

SHA-3函数家族由四个哈希函数和两个可扩展输出函数（Extendable-Output Function，XOF）组成。四个哈希函数分别为SHA3-224、SHA3-256、SHA3-384、SHA3-512，其中连字符后的后缀数字表示固定的输出摘要长度。例如，SHA3-224的摘要长度为224位。SHA-2函数家族的SHA-224、SHA-256、SHA-384、SHA-512能生成相同对应SHA-3长度的摘要，因此在实施时，SHA-2函数可以方便地过渡移植为SHA-3函数。可扩展输出函数指的是输出长度可任意扩展的函数，两个可扩展输出函数分别为SHAKE128和SHAKE256。其中，后缀数字表示XOF可支持的安全强度，与输出长度无关。SHAKE128和SHAKE256是NIST第三代哈希函数第一次标准化的可扩展输出函数。

SHA-3函数基于Keccak算法。Keccak算法的置换规则可表示为Keccak-p。Keccak-p在定义时由两个重要的参数组成：置换后字符串的固定长度，即置换的宽度；函数内部置换的迭代次数（也称迭代轮数），即“轮”（Round）。通常置换的宽度用 b 表示，迭代轮数用 n _r 表示，具有 n _r 次迭代，置换宽度为 b 的Keccak-p置换可表示为Keccak-p[ b ， n _r ]。在Keccak最初定义时， b 的取值范围为{25，50，100，200，400，800，1600}。Keccak函数还有另两个重要的参数，速率（比特率） r 和容量 c 。速率 r 表示在海绵结构中，每次调用函数时处理的输入消息分组长度。容量 c 在数值上等于宽度 b 减去速率 r ，即 r + c = b 。 c 越大，函数的安全性越高；相反， b 越大，函数的运行速度越快。SHA-3函数家族速率 r 、容量 c 和输出长度 d 见表4-1。

4.2.3 海绵结构

Keccak算法构造时基于海绵结构。海绵结构是一种能生成任意长度的二进制数据输出的特定函数框架。海绵结构可表示为Sponge[ f ，pad， r ]（ N ， d ），其中 N 为消息串， d 为摘要长度。结构主体由三组参数定义：迭代函数 f 、消息填充规则pad和消息分组长度 r 。迭代函数在4.2.4节中详细介绍。不同SHA-3函数的消息分组长度 r 不同，在数值上等于速率。消息填充pad遵循多重位速率填充（Multi-rate Padding）的规则，规则描述见算法4-1。

其中，len为比特串 P 的长度，mod表示模运算。在SHA-3中，输入正整数 x 为速率 r ，非负整数 m 为消息串 N 的比特长度。简单来说，就是首先在消息值末尾添加1位1，之后中间填充若干位0，最后添加1位1，填充0的位数要使得填充后的消息长度是消息分组长度 r 的最小整数倍。

Keccak海绵函数结构如图4-3所示。海绵结构处理数据的过程类似于海绵：任意长度的消息被分段“吸收”入结构中，之后摘要被分段从结构中“挤出”。计算的过程见算法4-2。

计算的过程可表述如下。

（1）吸收阶段：消息 N 首先被填充。填充完成后，消息将被顺序分割成若干组 N ₁ ， N ₂ ，…， N _n ，每组长度均为 r 。之后，第一组消息段 N ₁ 将与长度同样为 r 的二进制串0进行异或计算，计算结果拼接 c 个0后将作为迭代函数 f 的输入，经迭代函数处理后，输出的低 r 位将与第二组消息段 N ₂ 进行异或计算，计算结果拼接 c 个0后同样作为迭代函数 f 的输入。重复以上过程，直至所有的消息段都被吸收入海绵结构中。

（2）挤压阶段：特定长度的摘要 H ₁ 将直接从最后一次迭代函数输出的最低位截取获得。如果需要的输出长度大于 r ，则将多次调用迭代函数，每调用一次产生 r 位输出，将这些输出段拼接起来，直至达到所需长度的输出。

4.2.4 迭代函数

迭代函数 f 是整个SHA-3算法的核心部分。记每一轮的迭代运算为R，迭代轮数 n _r =12+2 l ，则 f 可表示为

迭代轮数 n _r 由数据的位宽 b 决定

由于在最终确定的SHA-3标准中，位宽 b =1600，因此迭代轮数 n _r 为24。每一轮迭代运算R共需5个步骤，分别是 θ 、 ρ 、 π 、 χ 和 ι ，故R可表示为

在迭代函数运算的过程中，中间状态固定为1600位，如图4-4所示，为了方便定义运算规则，将这1600位数据转换为一个5×5×64的三维状态数组，数据按照坐标轴 x 、 y 、 z 依次填充，状态数组中的任一位数据可表示为 S [ x ][ y ][ z ]。迭代运算基于该三维数组进行变换，每一轮变换包括 θ、ρ、π、χ、ι 五个步骤，一共需要24轮变换。Keccak-f[1600]五个步骤中的前四个步骤都是在三维数组中进行不同方向的行（Row）、列（Column）、道（Lane）变换，从而将所有元素混淆和扩散。最后一个步骤是将一组24个各不相同的轮常数添加到数组元素中以打破其他四个步骤变换的对称性。

以下讲述这五个变换步骤。

（1）步骤θ：对于0≤ x ＜5且0≤ y ＜5，有

步骤θ的作用是将矩阵数组中的每一位数据更新为附近两列与其本身的异或值。具体来说，对于任一位 A [ x ₀ ， y ₀ ， z ₀ ]，其值将更新为（（ x ₀ -1）mod 5， z ₀ ）所在列与（（ x ₀ +1）mod 5，（ z ₀ -1）mod 64）所在列与其本身共11位数值的异或值。θ变换的数学模型可以用图4-5表示。

（2）步骤ρ：对于0≤ x ＜5且0≤ y ＜5，有

步骤ρ对应的操作是 z 轴方向上的循环移位，三维数组中各个位置的移位长度见表4-2。

ρ变换的数学模型可以用图4-6表示。

（3）步骤 π ：对于0≤ x ＜5且0≤ y ＜5，有

π 变换对应的是 xOy 平面上任一位的位置变换，数学模型如图4-7所示。

（4）步骤 χ ：对于0≤ x ＜5且0≤ y ＜5，有

χ 变换对应的是每一行的任一位与该行的另外两位非线性函数进行异或运算。 χ 变换的数学模型可以用图4-8表示。

（5）步骤 ι ：对于0≤ i ≤23，有

ι 运算对应的操作是将 A [0，0， z ]这一道共64位与轮常数（Round Constant，RC）异或。轮常数RC共64位，一共24个轮常数。每一轮迭代变换依次与其中一个进行异或运算。轮常数的值根据以下函数定义。

其中，RC[ i _r ][ x ][ y ][ z ]的其他值均为0；rc[ t ] ∈ GF（2），由算法4-3定义。

根据算法4-3计算的轮常数值见表4-3。