SHA-3 (Keccak) 海绵结构中的轮函数 Keccak-f[b] 的状态数组结构与索引映射

我将为你讲解 SHA-3 (Keccak) 算法中核心组件——Keccak-f[b] 轮函数内部使用的状态数组结构及其独特的索引映射方式。这是理解 Keccak-f 如何操作 5×5×w 三维状态的关键。

题目描述
Keccak-f[b] 是 SHA-3 哈希算法（Keccak 家族）中使用的置换函数，其中 b 是状态的总比特长度，可取 {25, 50, 100, 200, 400, 800, 1600}。最常用的是 Keccak-f[1600]，其状态可视为一个三维数组 a[5][5][w]，其中 w = b/25（对于 b=1600，w=64）。我们需要理解这个三维状态是如何在内存中表示和索引的，以及 Keccak-f 的五个步骤（θ, ρ, π, χ, ι）如何基于特定的映射规则来操作状态比特。

解题过程

我们将分步构建状态数组的索引映射模型，并解释其设计原理和运算方式。

第一步：理解状态的三维结构
Keccak-f[b] 的状态本质上是一个三维比特数组，但为了方便理解和实现，它被概念化为一个 5×5 的“车道”（lane）矩阵，每个车道是一个 w 比特的字（word）。

• 设状态为 S，其三维坐标为 (x, y, z)，其中：
  • x：列索引，范围 0 到 4。
  • y：行索引，范围 0 到 4。
  • z：深度/比特索引，范围 0 到 w-1。
• 一个比特 S[x][y][z] 表示位于第 x 列、第 y 行、深度为 z 的比特。
• 在二维视角下，S[x][y] 是一个 w 比特的车道（lane），是整个 w 比特的字。

例如，对于 Keccak-f[1600]（w=64）：

• 状态总比特数 = 5 × 5 × 64 = 1600 比特。
• 每个车道是一个 64 比特字（在 64 位 CPU 上，正好对应一个寄存器）。

第二步：状态的内存布局与索引计算
虽然状态是三维的，但在内存中通常存储为一个一维比特数组或一个 5×5 的 w 比特字数组。Keccak 规范定义了一种特殊的索引映射，使得五个步骤可以高效实现。

索引映射规则如下：
给定三维坐标 (x, y, z)，其在一维比特数组中的索引 i（0 ≤ i < b）为：
i = (5*y + x) * w + z
但注意，这是“自然”的按行主序排列（先 y 后 x）。然而，在 Keccak 的官方描述和许多实现中，更常用的是将状态视为一个 5×5 的 w 比特字数组 A[x][y]，其中 A[x][y] 存储整个车道（即所有 z 比特）。此时，对车道内比特 z 的访问，就是对字 A[x][y] 的第 z 比特的操作。

所以，我们有两种等价的视角：

1. 三维比特数组 S[x][y][z]，其中 x, y, z 如上述范围。
2. 二维车道数组 A[x][y]（每个元素是 w 比特字），比特 z 对应 (A[x][y] >> z) & 1 或类似的位操作。

第三步：轮函数步骤中的坐标变换
Keccak-f 的五个步骤（θ, ρ, π, χ, ι）大量使用固定的坐标映射（尤其是 ρ 和 π），这些映射是基于模 5（对于 x, y）和模 w（对于 z）的循环操作。

1. θ (Theta) 步骤：

   • 计算每列的奇偶性（模 2 和）。对于每个 (x, z)，计算：
     C[x][z] = S[x][0][z] ⊕ S[x][1][z] ⊕ S[x][2][z] ⊕ S[x][3][z] ⊕ S[x][4][z]
   • 然后，对每个比特 S[x][y][z] 进行更新：
     S[x][y][z] = S[x][y][z] ⊕ C[x-1][z] ⊕ C[x+1][z-1]
     其中索引 x-1, x+1 是模 5 的，z-1 是模 w 的。
   • 这里操作的是整个列（固定 x, z，遍历 y）和相邻列（x-1, x+1）的奇偶性。

2. ρ (Rho) 步骤：

   • 对每个车道（即每个 (x, y)）进行循环左移，移位量 r[x][y] 是预定义的常量。
   • 移位量 r[x][y] 定义如下（对于 w 是 2 的幂的情况，这里给出 w=64 时的值）：

     r[0][0]=0,  r[1][0]=1,  r[2][0]=62, r[3][0]=28, r[4][0]=27,
     r[0][1]=36, r[1][1]=44, r[2][1]=6,  r[3][1]=55, r[4][1]=20,
     r[0][2]=3,  r[1][2]=10, r[2][2]=43, r[3][2]=25, r[4][2]=39,
     r[0][3]=41, r[1][3]=45, r[2][3]=15, r[3][3]=21, r[4][3]=8,
     r[0][4]=18, r[1][4]=2,  r[2][4]=61, r[3][4]=56, r[4][4]=14
     

   • 操作：A[x][y] = ROT(A[x][y], r[x][y])，其中 ROT 是循环左移。
   • 关键点：ρ 只改变比特在车道内的位置（z 坐标变化），不改变车道所属的 (x, y)。移位量设计成使每个车道的移位都不同，且覆盖 0 到 w-1，确保比特充分扩散。

3. π (Pi) 步骤：

   • 重新排列车道的位置。它是一个固定的置换，将车道从位置 (x, y) 移动到新的位置 (x', y')。
   • 变换公式：(x, y) → (x', y') = ( (x + 3y) mod 5, x )
   • 即：新的列索引 x' = (x + 3y) mod 5，新的行索引 y' = x。
   • 注意：π 置换的是整个车道（w 比特一起移动），不改变车道内的比特顺序（z 坐标不变）。
   • 该置换是可逆的，其逆变换为：(x', y') → (x, y) = (y', (2x' + 3y') mod 5)。
   • π 步骤的目的是破坏车道之间的对齐，增加扩散。

4. χ (Chi) 步骤：

   • 这是唯一的非线性步骤，对每一行（固定 y 和 z，遍历 x）独立操作。
   • 公式：S[x][y][z] = S[x][y][z] ⊕ ( (¬ S[x+1][y][z]) ∧ S[x+2][y][z] )
     其中索引 x+1, x+2 是模 5 的。
   • 注意：χ 在每一行内（5 个比特，对应 x=0..4）进行一个 5 比特的 S 盒替换。这个 S 盒是最大距离可分的（MDS），提供非线性性。
   • 因为是对每个 z 独立操作，所以可以并行处理所有 w 个比特（即整个行车道组）。

5. ι (Iota) 步骤：

   • 只修改一个车道：A[0][0]（即 (x=0, y=0) 车道）。
   • 操作：A[0][0] = A[0][0] ⊕ RC[i_r]，其中 i_r 是轮索引（0 到 23），RC[i_r] 是一个 w 比特的轮常量。
   • 轮常量 RC 的生成基于一个最大长度的线性反馈移位寄存器（LFSR），确保每轮不同。
   • ι 的目的是破坏对称性，防止在特定输入下轮函数出现不动点或短周期。

第四步：总结索引映射的意义

• 三维结构 (x, y, z) 允许算法在两个维度（x, y）进行 5×5 的矩阵操作（如 θ, π, χ），同时在第三个维度 z 进行比特级操作（如 θ 的列奇偶性、χ 的行内非线性）。
• ρ 步骤的循环左移利用了 z 维度的循环特性，配合预定义的移位表 r[x][y]，确保比特在三维空间中充分混合。
• π 步骤的置换 (x, y) = (x+3y, x) 是精心选择的，使得经过多轮后，任何两个原始相邻的比特在三维空间中都能快速扩散开来。
• 整个设计使 Keccak-f 具有高扩散性、非线性，并能抵抗已知的密码分析攻击（如差分、线性分析）。

第五步：实际实现中的优化
在软件实现中，状态通常表示为 A[5][5] 的 64 位整数数组（对于 b=1600）。五个步骤可以高效实现：

• θ：先计算每列的奇偶（5 个 64 位字 C[0]..C[4]），然后更新所有车道。
• ρ：直接对每个 A[x][y] 进行循环左移 r[x][y] 位。
• π：将 A 复制到一个新数组 B，并按照映射 B[x'][y'] = A[x][y] 赋值。
• χ：对每一行（5 个 64 位字）进行并行比特操作，可以利用位运算技巧。
• ι：简单地将 A[0][0] 与轮常量异或。

这种三维状态结构和索引映射使得 Keccak-f 在硬件和软件上都能高效实现，同时提供了强大的密码学安全性。

通过以上步骤，你应该能理解 Keccak-f[b] 轮函数中三维状态的组织方式和各步骤如何利用索引映射进行操作。这种设计是 SHA-3 算法安全性和效率的基石。