SHA-256哈希算法中消息分组的W_t推导与计算过程
我将为你讲解SHA-256算法中，如何从输入消息的一个512位分组，推导出64个32位字W₀到W₆₃的过程。这是SHA-256压缩函数的核心预处理步骤。
题目描述：
在SHA-256哈希算法中，输入消息被填充和分块为多个512位的消息分组。每个分组在进入压缩函数处理前，需要先被扩展为64个32位字（W₀到W₆₃）。其中前16个字（W₀到W₁₅）直接取自消息分组，而后48个字（W₁₆到W₆₃）需要通过特定的递归公式计算得出。请详细解释W₀到W₆₃的推导过程，包括每个步骤的位操作和设计原理。
解题过程详解：
第一步：理解基本概念和输入格式
SHA-256处理的消息分组长度为512位。这512位在逻辑上可以看作是16个连续的32位字，我们记为M₀, M₁, ..., M₁₅。其中M₀是该分组的最高有效32位，M₁₅是最低有效32位。
我们的目标是将这16个初始字，扩展为64个字W₀, W₁, ..., W₆₃，供后续64轮压缩运算使用。
第二步：前16个字（W₀到W₁₅）的初始化
这16个字直接从消息分组中拷贝得到：
W_t = M_t， 对于 t = 0, 1, 2, ..., 15
也就是说，W₀ = M₀, W₁ = M₁, ..., W₁₅ = M₁₅。这里没有进行任何计算变换，只是简单的赋值。这确保了消息数据的原始性。
第三步：后48个字（W₁₆到W₆₃）的递归计算
对于t = 16, 17, ..., 63，Wₜ通过其前面的某些W值计算得出。计算公式如下：
W_t = σ₁(W_{t-2}) + W_{t-7} + σ₀(W_{t-15}) + W_{t-16}
让我们拆解这个公式的四个组成部分：
-
σ₀(x) 函数： 这是对“较老”的消息字（距离当前t点15个位置）进行的非线性变换。
- 计算公式： σ₀(x) = ROTR⁷(x) ⊕ ROTR¹⁸(x) ⊕ SHR³(x)
- 位操作解释：
ROTRⁿ(x)： 将32位字x循环右移n位。循环右移是指移出的位从左侧补回。SHRⁿ(x)： 将32位字x逻辑右移n位。逻辑右移是指左侧用0填充。
- 在Wₜ的计算中，
σ₀(W_{t-15})意味着对W_{t-15}这个值，分别进行循环右移7位、循环右移18位和逻辑右移3位，然后将这三个结果进行按位异或（XOR，⊕） 操作。
-
σ₁(x) 函数： 这是对“较新”的消息字（距离当前t点2个位置）进行的非线性变换。
- 计算公式： σ₁(x) = ROTR¹⁷(x) ⊕ ROTR¹⁹(x) ⊕ SHR¹⁰(x)
- 操作方式同σ₀，只是移位的常数（17, 19, 10）不同。在Wₜ的计算中，
σ₁(W_{t-2})就是对W_{t-2}进行这个变换。
-
加法（+）运算： 公式中的“+”是模2³²加法。即将两个32位字当作普通的整数相加，如果结果超过2³²（即0xFFFFFFFF + 1），则丢弃最高位的进位，只保留结果的低32位。这不同于按位异或。
-
组合项：
W_{t-16}是16轮之前最“老”的原始消息字。W_{t-7}是7轮之前的字。σ₀(W_{t-15})是15轮之前的字经过非线性扩散。σ₁(W_{t-2})是2轮之前的字经过另一种非线性扩散。
第四步：通过一个具体例子理解计算过程
假设我们要计算 W₁₆。
根据公式：W₁₆ = σ₁(W₁₄) + W₉ + σ₀(W₁) + W₀
计算步骤：
- 查找已知值：此时W₀到W₁₅已经由M₀到M₁₅初始化得到，所以W₀, W₁, W₉, W₁₄是已知的32位数值。
- 计算 σ₁(W₁₄)：
- a = ROTR¹⁷(W₁₄)
- b = ROTR¹⁹(W₁₄)
- c = SHR¹⁰(W₁₄)
- σ₁(W₁₄) = a ⊕ b ⊕ c
- 计算 σ₀(W₁)：
- d = ROTR⁷(W₁)
- e = ROTR¹⁸(W₁)
- f = SHR³(W₁)
- σ₀(W₁) = d ⊕ e ⊕ f
- 执行模2³²加法：将上述四个分量（σ₁(W₁₄), W₉, σ₀(W₁), W₀）依次相加，每次加法都是模2³²。最终得到的32位结果就是W₁₆。
同理，要计算W₁₇：
W₁₇ = σ₁(W₁₅) + W₁₀ + σ₀(W₂) + W₁
如此递归，直到算出W₆₃。
第五步：设计原理与安全性分析
这个推导过程的设计目标是为压缩函数的每一轮提供“与整个消息分组相关”且“具有充分扩散和混淆”的输入字。
- 非线性扩散：σ₀和σ₁函数通过不同距离的循环移位和逻辑移位的组合，打破了数据的线性结构。即使输入消息只有一位不同，经过多次σ函数和模加运算后，其影响会迅速扩散到后续所有的Wₜ中。
- 消除规律性：如果仅仅重复使用最初的16个字，算法会存在明显的周期性弱点，容易被攻击。递归计算引入了数据的依赖性，Wₜ的值依赖于前面多个不同位置的字，使得64轮中使用的字各不相同且相互关联。
- 防止固定点：公式中同时使用了距离为2、7、15、16的“旧”值。这些精心选择的距离（是互质的）确保了在递归过程中，数据的每一位都有机会通过不同的路径和组合影响新生成的Wₜ，增强了算法的雪崩效应。
- 运算效率：整个扩展过程只涉及简单的位操作（移位、异或）和模加运算，在现代CPU上可以高效实现，满足了哈希函数对速度的要求。
总结：
SHA-256的消息扩展（Wₜ推导）是一个巧妙的设计。它将一个512位的输入分组，通过前16个字的直接装载和后48个字的递归计算，扩展为64个32位的消息调度字。这个过程通过σ₀和σ₁函数以及模2³²加法，为后续的64轮压缩函数提供了充分非线性化、扩散性良好的输入，是SHA-256算法具备强抗碰撞能力的重要基础之一。