Whirlpool 哈希算法的轮函数设计

1. 题目描述
Whirlpool 是一种基于 AES 设计理念的密码学哈希算法，输出长度为 512 位。其核心是一个类似 AES 的 512 位分组密码（W 算法）运行在 Miyaguchi-Preneel 模式下构成压缩函数。本题要求详细讲解 Whirlpool 轮函数的设计，包括轮函数的整体结构、各子步骤的数学定义、具体操作以及设计原理。

2. 轮函数整体结构
Whirlpool 的轮函数是 W 算法的一部分，其结构与 AES 高度相似，但针对 512 位状态进行了适配。整体流程如下：

• 输入：一个 8×8 字节的状态矩阵（共 512 位），以及当前轮次的轮密钥。
• 轮函数包含 4 个依次应用的变换：
  1. 非线性字节替换（SubBytes, SB）
  2. 循环行移位（ShiftColumns, SC）
  3. 扩散行混合（MixRows, MR）
  4. 轮密钥加（AddRoundKey, AK）
• 注意：在 Whirlpool 中，轮函数的顺序是 SB → SC → MR → AK，与 AES 的顺序（SubBytes → ShiftRows → MixColumns → AddRoundKey）略有不同，但逻辑相似。
• 总轮数：Whirlpool 的 W 算法固定为 10 轮（与密钥扩展的轮数相同）。

3. 子步骤详解

3.1 SubBytes（非线性字节替换）

• 目的：引入非线性，抵抗线性密码分析。
• 操作：对状态矩阵中的每个字节（共 64 字节），应用一个固定的 8×8 位 S 盒。
• S 盒来源：基于有限域 GF(2⁸) 上的运算构造，与 AES 的 S 盒不同但结构相似。其构造包括：
  • 将输入字节视为 GF(2⁸) 中的元素（不可约多项式为 \(x^8 + x^4 + x^3 + x^2 + 1\)）。
  • 若输入为 0，映射为 0；否则计算在 GF(2⁸) 上的乘法逆元。
  • 对结果应用一个仿射变换（比特层面线性变换 + 异或常数 0x63）。
  • 最终输出字节。
• 注意：此 S 盒是预先计算好的表，轮函数中直接查表即可。

3.2 ShiftColumns（循环行移位）

• 目的：在列方向引入扩散，与 AES 的 ShiftRows 类似但方向不同。
• 操作：将状态矩阵视为 8×8 字节，每一列独立进行循环上移，移动的偏移量等于列号（从 0 开始计数）。
• 数学表示：设状态为 \(S[i][j]\)（i 为行，j 为列，0 ≤ i,j ≤ 7），变换后得到 \(S'[i][j] = S[(i + j) \bmod 8][j]\)。
• 举例：第 0 列不变，第 1 列上移 1 行，第 2 列上移 2 行，…，第 7 列上移 7 行。

3.3 MixRows（扩散行混合）

• 目的：在行方向引入强扩散，与 AES 的 MixColumns 类似但方向不同。
• 操作：将状态矩阵的每一行视为一个向量，在 GF(2⁸) 上左乘一个固定的 8×8 循环矩阵 M。
• 矩阵 M 的定义（十六进制表示元素，视为 GF(2⁸) 中的多项式系数）：

\[ M = \begin{pmatrix} 01 & 01 & 04 & 01 & 08 & 05 & 02 & 09 \\ 09 & 01 & 01 & 04 & 01 & 08 & 05 & 02 \\ 02 & 09 & 01 & 01 & 04 & 01 & 08 & 05 \\ 05 & 02 & 09 & 01 & 01 & 04 & 01 & 08 \\ 08 & 05 & 02 & 09 & 01 & 01 & 04 & 01 \\ 01 & 08 & 05 & 02 & 09 & 01 & 01 & 04 \\ 04 & 01 & 08 & 05 & 02 & 09 & 01 & 01 \\ 01 & 04 & 01 & 08 & 05 & 02 & 09 & 01 \end{pmatrix} \]

• 计算：对于第 r 行（0 ≤ r ≤ 7），新字节为：
  \(S'[r][c] = \bigoplus_{k=0}^{7} M[c][k] \otimes S[r][k]\)
  其中 \(\otimes\) 是 GF(2⁸) 上的乘法（模同一个不可约多项式），\(\oplus\) 是异或。
• 注：M 是循环矩阵，其每行是前一行的循环右移，这简化了硬件实现。

3.4 AddRoundKey（轮密钥加）

• 目的：将轮密钥与状态进行混合。
• 操作：轮密钥也是一个 8×8 字节矩阵，与状态矩阵进行逐字节异或（XOR）。
• 轮密钥来源：由 Whirlpool 的密钥扩展算法生成（基于类似轮函数的结构，但本题不展开）。

4. 轮函数流程示例
假设当前状态为 \(S\)，轮密钥为 \(K_r\)（r 为轮次，0 ≤ r ≤ 9），则一轮的具体伪代码为：

State = SubBytes(State)     # 字节替换
State = ShiftColumns(State) # 列循环移位
State = MixRows(State)      # 行混合
State = AddRoundKey(State, K_r) # 轮密钥加

注意：在 W 算法的第一轮之前，会先进行一次 AddRoundKey（使用 \(K_0\)），这通常被视为“第 0 轮密钥加”，之后再进行 10 轮上述操作。

5. 轮函数设计原理

• 对称结构：四个子步骤均以字节或行为单位并行处理，适合软硬件优化。
• 非线性与扩散平衡：SubBytes 提供强非线性，ShiftColumns 和 MixRows 确保在 2 轮内所有输出比特依赖于所有输入比特。
• 有限域运算：基于 GF(2⁸) 的运算提供了良好的代数结构，同时 S 盒和 M 矩阵的设计可抵抗已知攻击（如差分和线性分析）。
• 与 AES 的异同：借鉴 AES 的宽轨迹策略，但调整了移位和混合的方向（列移位 vs 行移位，行混合 vs 列混合），以适应 512 位状态。

6. 总结
Whirlpool 的轮函数通过精心设计的四个步骤，在有限域上构建了一个强扩散和非线性层，结合轮密钥加实现了混乱和扩散，确保了哈希函数的安全性。其结构与 AES 相似，但参数和方向有所不同，是理解分组密码在哈希函数中应用的经典案例。