SHA-256哈希算法的压缩函数设计
题目描述
SHA-256的压缩函数是其核心组件，负责将512位的消息块与256位的中间哈希值（状态）混合，生成新的256位哈希值。要求详细解释压缩函数的结构、运算步骤（如消息扩展、轮函数等），并说明其设计如何保证抗碰撞性。
1. 压缩函数的输入与输出
- 输入：
- 当前哈希状态（256位）：由8个32位寄存器
a, b, c, d, e, f, g, h表示。 - 一个512位的消息块
M，划分为16个32位字（M[0]到M[15]）。
- 当前哈希状态（256位）：由8个32位寄存器
- 输出：
- 更新后的256位哈希状态。
2. 消息扩展（Message Schedule）
512位消息块需扩展为64个32位字（W[0] 到 W[63]），用于后续64轮计算：
- 前16个字：直接取自消息块：
\[ W[i] = M[i] \quad (0 \leq i \leq 15) \]
- 后续48个字（
i = 16 到 63）通过以下运算生成：
\[ W[i] = \sigma_1(W[i-2]) + W[i-7] + \sigma_0(W[i-15]) + W[i-16] \]
其中：
- \(\sigma_0(x) = (x \ggg 7) \oplus (x \ggg 18) \oplus (x \gg 3)\)
- \(\sigma_1(x) = (x \ggg 17) \oplus (x \ggg 19) \oplus (x \gg 10)\)
- \(\ggg\) 表示循环右移，\(\gg\) 表示逻辑右移。
设计目的：通过非线性运算和位移，消除消息中的规律性，增强雪崩效应。
3. 轮函数（Round Function）
每一轮（共64轮）更新寄存器 a 到 h 的值。第 i 轮（0 ≤ i ≤ 63）的步骤如下：
- 计算中间变量：
\[ T_1 = h + \Sigma_1(e) + \text{Ch}(e, f, g) + K[i] + W[i] \]
\[ T_2 = \Sigma_0(a) + \text{Maj}(a, b, c) \]
其中：
- 选择函数：\(\text{Ch}(e, f, g) = (e \land f) \oplus (\neg e \land g)\)
- 多数函数：\(\text{Maj}(a, b, c) = (a \land b) \oplus (a \land c) \oplus (b \land c)\)
- 循环移位和：
\[ \Sigma_0(a) = (a \ggg 2) \oplus (a \ggg 13) \oplus (a \ggg 22) \]
\[ \Sigma_1(e) = (e \ggg 6) \oplus (e \ggg 11) \oplus (e \ggg 25) \]
- \(K[i]\)：64个32位轮常数（取自自然数前64个质数的立方根小数部分前32位）。
- 更新寄存器：
\[ h = g,\quad g = f,\quad f = e,\quad e = d + T_1 \]
\[ d = c,\quad c = b,\quad b = a,\quad a = T_1 + T_2 \]
设计意图：通过非线性逻辑函数（Ch、Maj）和线性扩散（Σ₀、Σ₁）混合消息与状态，确保微小输入变化导致输出巨大差异。
4. 最终更新
64轮后，将新一轮的哈希状态与初始状态相加（模 \(2^{32}\)）：
\[H_{\text{new}} = (a + a_0, b + b_0, \dots, h + h_0) \]
其中 \((a_0, \dots, h_0)\) 是压缩函数开始前的初始状态。
5. 安全性设计要点
- 非线性操作：Ch和Maj函数引入布尔运算的非线性，防止线性攻击。
- 消息扩展的扩散：σ₀和σ₁确保每个消息位影响多轮计算。
- 轮常数避免对称性：K[i] 打破轮函数的对称性，防止固定点攻击。
- 雪崩效应：单比特变化平均在3轮内扩散到所有寄存器。
总结：SHA-256压缩函数通过迭代的混淆与扩散，将消息块充分混合到状态中，其结构兼顾效率与安全性，是目前抗碰撞攻击的可靠设计。