分组密码算法结构性测试
明密文独立性、扩散性与密钥有效性
一、测试总览
分组密码被视作一个黑盒，测试的思路如下：
- 构造一个统计量 $ V $，假设算法是安全的，则该统计量应服从某种已知分布；
- 使用假设检验的方法，判断实际观测值是否与该分布一致；
- 根据 $ p $-value 是否大于显著性水平 $ \alpha $（通常取 0.01）来判断是否通过测试。
二、明密文独立性测试
测试目的
检测密文是否不依赖于明文的统计特性。即使明文具有明显规律，密文也应呈现随机性。
测试原理
- 固定一个密钥，随机生成大量明文并加密；
- 计算每对明文与密文的汉明距离（异或后计算1的个数）；
- 若算法安全，这些距离应服从二项分布 $ B(n, 1/2) $，其中 $ n $ 为分组长度。
测试方法简述
- 随机生成 $ m = 2^{20} $ 个明文；
- 计算 $ D_i = P_i \oplus C_i $，统计其汉明重量；
- 按分组长度将重量分为5组，计算卡方统计量：
\( \chi^2 = \sum \frac{(v_i - m\pi_i)^2}{m\pi_i} \) - 计算 $ p $-value，若 $ p \geq 0.01 $ 则通过。
结论
- 通过：密文与明文统计特性独立；
- 不通过：密文可能依赖于明文结构。
三、明文扩散性检测（雪崩测试）
测试目的
检测明文微小变化是否引起密文剧烈变化，满足严格雪崩准则。
测试原理
- 固定密钥，随机生成一个明文并加密；
- 逐一改变明文的每一比特，重新加密；
- 计算两次密文的汉明距离，理想情况下应接近 $ n/2 $；
- 这些距离应服从二项分布 $ B(n, 1/2) $。
测试方法简述
- 随机生成明文 $ P $ 和固定密钥；
- 对每个比特翻转后的明文加密，得到密文 $ C_i $；
- 重复 $ m $ 次，统计所有 $ m \times n $ 个汉明重量；
- 同样使用卡方检验判断是否服从二项分布。
结论
- 通过：算法对明文变化敏感，扩散性良好；
- 不通过：可能存在局部线性或弱扩散问题。
四、密钥有效性检测
测试目的
检测密钥微小变化是否引起密文剧烈变化，确保密钥的雪崩效应。
测试原理
- 固定明文，随机生成一个密钥并加密；
- 逐一改变密钥的每一比特，重新加密；
- 计算密文之间的汉明距离，理想情况下应接近 $ n/2 $。
测试方法简述
- 随机生成明文 $ P $ 和密钥 $ key $；
- 对每个比特翻转后的密钥重新加密；
- 重复 $ m $ 次，统计所有 $ m \times k $ 个汉明重量（$ k $ 为密钥长度）；
- 使用卡方检验判断是否服从二项分布。
结论
- 通过：密钥微小变化能有效打乱密文；
- 不通过：密钥扩展或轮函数设计可能存在问题。
总结
| 测试类型 | 固定变量 | 变化变量 | 统计对象 | 判断标准 |
|---|---|---|---|---|
| 明密文独立性 | 密钥 | 明文 | $ P \oplus C $ 的汉明重量 | 服从 $ B(n, 1/2) $ |
| 明文扩散性 | 密钥 | 明文逐比特 | $ C \oplus C_i $ 的汉明重量 | 服从 $ B(n, 1/2) $ |
| 密钥有效性 | 明文 | 密钥逐比特 | $ C \oplus C_i $ 的汉明重量 | 服从 $ B(n, 1/2) $ |