SHA-1哈希算法的轮函数设计
题目描述
SHA-1（Secure Hash Algorithm 1）是一种曾广泛使用的密码学哈希函数，可将任意长度消息压缩为160位（20字节）的摘要。其核心是80轮的压缩函数，每轮对5个32位状态变量（A、B、C、D、E）进行非线性迭代。本题要求详细分析SHA-1轮函数的结构，包括轮函数的分组、每轮使用的逻辑函数、常量及消息扩展规则，并逐步演示一轮计算过程。
解题过程
1. SHA-1压缩函数整体框架
- 输入：
- 160位中间哈希值（5个32位变量 \(A_0, B_0, C_0, D_0, E_0\)，初始为IV或前一轮结果）。
- 512位消息分组（通过填充和分块得到）。
- 过程：将消息分组扩展为80个32位字 \(W_0 \sim W_{79}\)，经80轮迭代更新状态变量。
- 输出：新一轮哈希值 \(A_{80}, B_{80}, C_{80}, D_{80}, E_{80}\)。
2. 轮函数的分组与参数
80轮分为4个阶段，每20轮使用不同的逻辑函数 \(f_t\) 和常量 \(K_t\)：
| 轮次范围 \(t\) | 逻辑函数 \(f_t(B,C,D)\) | 常量 \(K_t\)（十六进制） |
|---|---|---|
| 0–19 | \(f_1 = (B \land C) \lor (\lnot B \land D)\) | 0x5A827999 |
| 20–39 | \(f_2 = B \oplus C \oplus D\) | 0x6ED9EBA1 |
| 40–59 | \(f_3 = (B \land C) \lor (B \land D) \lor (C \land D)\) | 0x8F1BBCDC |
| 60–79 | \(f_4 = B \oplus C \oplus D\)（同 \(f_2\)） | 0xCA62C1D6 |
注意：
- \(f_1\) 与条件运算（IF）等价：若 \(B=1\) 取 \(C\)，否则取 \(D\)。
- \(f_3\) 是多参数多数表决（MAJ），输出占多数的位值。
3. 单轮迭代步骤
以第 \(t\) 轮为例（\(0 \leq t \leq 79\)），输入当前状态 \((A_{t}, B_{t}, C_{t}, D_{t}, E_{t})\) 和扩展消息字 \(W_t\)，输出更新后的状态：
- 计算轮函数输出：
\[ \text{temp} = f_t(B_t, C_t, D_t) \]
- 加法与循环左移：
\[ \text{temp} = (A_t \lll 5) + \text{temp} + E_t + K_t + W_t \]
其中 \(\lll 5\) 表示循环左移5位，所有加法为模 \(2^{32}\) 加法。
3. 更新状态变量：
\[ \begin{aligned} A_{t+1} &= \text{temp} \\ B_{t+1} &= A_t \\ C_{t+1} &= B_t \lll 30 \quad (\text{注意：B左移30位而非5位！}) \\ D_{t+1} &= C_t \\ E_{t+1} &= D_t \end{aligned} \]
关键细节：
- \(C_{t+1}\) 由 \(B_t\) 循环左移30位得到，这是SHA-1与MD4族算法的区别。
- 状态更新是线性移位（B→C→D→E）与非线性的混合。
4. 消息扩展：生成 \(W_0 \sim W_{79}\)
- 初始16个字：直接取自512位消息分组，按大端序分为16个32位字 \(W_0 \sim W_{15}\)。
- 后续64个字（\(16 \leq t \leq 79\)）：
\[ W_t = (W_{t-3} \oplus W_{t-8} \oplus W_{t-14} \oplus W_{t-16}) \lll 1 \]
通过异或和循环左移1位引入扩散，确保每轮输入与原始消息相关。
5. 实例演示：第1轮（t=0）计算
假设初始状态为SHA-1标准IV（十六进制）：
\[A_0 = 0x67452301,\quad B_0 = 0xEFCDAB89,\quad C_0 = 0x98BADCFE,\quad D_0 = 0x10325476,\quad E_0 = 0xC3D2E1F0 \]
消息分组前16字全为0（简化示例），则 \(W_0 = 0x00000000\)。
逐步计算：
- 计算 \(f_0\)（属于0–19轮，用 \(f_1\)）：
\[ f_1(B_0, C_0, D_0) = (0xEFCDAB89 \land 0x98BADCFE) \lor (\lnot 0xEFCDAB89 \land 0x10325476) \]
按位计算：
- \(\lnot B_0 = 0x10325476\)（按位取反）
- 第一部分：\(B_0 \land C_0 = 0x88A88888\)
- 第二部分：\(\lnot B_0 \land D_0 = 0x10325476\)（因 \(D_0 = \lnot B_0\)）
- 合并：\(0x88A88888 \lor 0x10325476 = 0x98BADCFE\)（实际即 \(C_0\) 的值）。
- 计算 temp：
\[ \begin{aligned} \text{temp} &= (A_0 \lll 5) + f_1 + E_0 + K_0 + W_0 \\ &= (0x67452301 \lll 5) + 0x98BADCFE + 0xC3D2E1F0 + 0x5A827999 + 0x00000000 \end{aligned} \]
- \(A_0 \lll 5\)：0x67452301 循环左移5位 = 0xE8A46023（二进制左移5位后拼接低位）。
- 模 \(2^{32}\) 加法：
\[ 0xE8A46023 + 0x98BADCFE = 0x815F3D21 \quad (\text{忽略进位}) \]
逐步加：
\[ \begin{aligned} 0x815F3D21 + 0xC3D2E1F0 &= 0x45321F11 \\ 0x45321F11 + 0x5A827999 &= 0x9FB498AA \\ 0x9FB498AA + 0x00000000 &= 0x9FB498AA \end{aligned} \]
故 $\text{temp} = 0x9FB498AA$。
- 更新状态：
\[ \begin{aligned} A_1 &= 0x9FB498AA \\ B_1 &= A_0 = 0x67452301 \\ C_1 &= B_0 \lll 30 = 0xEFCDAB89 \lll 30 = 0xBF36AF3B \\ D_1 &= C_0 = 0x98BADCFE \\ E_1 &= D_0 = 0x10325476 \end{aligned} \]
完成第1轮迭代。
6. 安全性注记
SHA-1因碰撞攻击（2017年实际攻击成本＜10万美元）被弃用，但其轮函数设计体现了经典哈希算法的思路：
- 非线性函数 \(f_t\) 轮换增强混淆。
- 消息扩展通过移位和异或实现扩散。
- 循环移位和模加抵抗差分攻击。
通过以上步骤，可逐轮推演完整SHA-1计算，理解其压缩函数的核心机制。