SM3密码杂凑算法的填充与迭代过程

题目描述
SM3密码杂凑算法是中国国家密码管理局发布的密码哈希算法标准，输出长度为256位。本题要求详细讲解SM3算法中消息填充和迭代压缩的过程，包括如何将任意长度的输入消息转换为符合分组要求的填充后消息，以及如何通过迭代模式调用压缩函数生成最终哈希值。

解题过程

1. 消息填充（Padding）

   • 步骤1：在原始消息末尾添加一个"1"比特（实际实现中常添加字节0x80）。
   • 步骤2：添加k个"0"比特，使得填充后的消息长度满足：(原始消息长度 + 1 + k) ≡ 448 mod 512。
     • 示例：若原始消息长500比特，则1+k需满足501+k ≡ 448 mod 512，解得k=459。
   • 步骤3：在末尾添加64比特的原始消息长度值（以大端序表示）。
     • 最终消息总长度变为512的整数倍，划分为多个512比特分组。

2. 迭代过程

   • 初始化8个32位寄存器（A~H）为固定初始值IV。
   • 对每个512比特分组执行：
     • 消息扩展：将分组划分为16个32位字W0~W15，通过线性变换生成132个扩展字W0~W67和W'0~W'63。
       • 计算公式：
         Wj = P1(W_{j-16} ⊕ W_{j-9} ⊕ (W_{j-3} <<< 15)) ⊕ (W_{j-13} <<< 7) ⊕ W_{j-6}（16≤j≤67）
     • 压缩函数：进行64轮迭代，每轮更新寄存器值：
       • SS1 = ((A <<< 12) + E + (Tj <<< j)) <<< 7
       • SS2 = SS1 ⊕ (A <<< 12)
       • TT1 = FFj(A,B,C) + D + SS2 + W'j
       • TT2 = GGj(E,F,G) + H + SS1 + Wj
       • 更新顺序：D=C, C=B<<<9, B=A, A=TT1, H=G, G=F<<<19, F=E, E=TT2⊕(TT2<<<9)
   • 处理完所有分组后，将最终寄存器值拼接为256位哈希值。

关键点说明

• 填充确保消息长度唯一对应，防止长度扩展攻击。
• 压缩函数中的FFj/GGj为布尔函数，Tj为常量，设计体现雪崩效应。
• 迭代结构使每个分组均影响最终结果，增强抗碰撞性。