序列密码算法结构性测试
密钥、初始向量与密钥流的统计评估。
序列密码算法的安全性在很大程度上依赖于密钥流是否呈现伪随机性。本章介绍的四种结构性测试，从不同角度检验种子密钥、初始向量（IV）与密钥流之间的统计关系。
一、测试总览
序列密码被视为黑盒，测试流程与分组密码类似：
- 构造统计量 $ V $，在安全假设下应服从某种已知分布；
- 使用假设检验（卡方拟合优度检验）判断实际观测值是否与理论分布一致；
- 根据 $ p $-value 是否大于显著性水平 $ \alpha = 0.01 $ 判定是否通过。
- 种子密钥 / 密钥流相关性检测
- 初始向量 / 密钥流相关性检测
- 帧相关性测试
- 扩散性测试
二、种子密钥 / 密钥流相关性检测
测试目的
评估种子密钥 $ key $ 与前 $ k $ 比特密钥流（$ k $ 为密钥长度）之间是否存在线性相关性。高相关性可能导致攻击者通过密钥流恢复密钥或降低穷举搜索空间。
测试原理
- 固定一个初始向量 IV；
- 随机生成 $ m = 2^{20} $ 个不同的种子密钥 $ key_i $；
- 对每个 $ key_i $，生成前 $ k $ 比特密钥流 $ C_i = S(key_i, IV, k) $；
- 计算 $ C_i \oplus key_i $ 的汉明重量 $ \omega_i $；
- 若算法安全，$ \omega_i $ 应服从二项分布 $ B(k, 1/2) $。
测试方法
- 固定 IV；
- 生成 $ m $ 个随机密钥；
- 计算 $ C_i $ 并与密钥异或，统计汉明重量；
- 根据密钥长度 $ k $（64,80,128,192,256）将重量分为5组；
- 计算卡方统计量及 $ p $-value。
结论
- 通过（$ p \geq 0.01 $）：密钥与密钥流无明显相关性；
- 不通过（$ p < 0.01 $）：
- 汉明重量过低 → 密钥与密钥流相似（正相关）；
- 汉明重量过高 → 密钥与密钥流呈负相关。
本测试仅考察相同比特位置（第 $ i $ 比特密钥 vs 第 $ i $ 比特密钥流）的相关性，不考虑跨比特关系。
三、初始向量 / 密钥流相关性检测
测试目的
评估初始向量 IV 与前 $ v $ 比特密钥流（$ v $ 为 IV 长度）之间的相关性。若相关性过高，攻击者可能从密钥流反推 IV。
测试原理
- 固定一个种子密钥 $ key $；
- 随机生成 $ m = 2^{20} $ 个不同的 IV；
- 对每个 IV，生成前 $ v $ 比特密钥流 $ C_i = S(key, IV_i, v) $；
- 计算 $ C_i \oplus IV_i $ 的汉明重量，理论上应服从 $ B(v, 1/2) $。
测试方法
与密钥相关性检测完全对称，只需将“固定 IV、变化密钥”改为“固定密钥、变化 IV”。
结论
- 通过：IV 与密钥流相互独立；
- 不通过：IV 重载阶段需要修改，避免线性依赖。
四、帧相关性测试
测试目的
在序列密码中，一个固定长度的密钥流称为帧（Frame）。该测试检测当 IV 以固定步长（通常加1）递增时，对应帧之间是否存在统计相关性。若存在，则表明 IV 初始化方式有缺陷。
测试原理
- 固定一个密钥 $ key $；
- 取初始 IV₁（如 0x00000001），生成长度为 $ l = 256 $ 的密钥流；
- 将 IV 逐次加1，生成 $ m = 2^{20} $ 个长度为 $ l $ 的密钥流；
- 构造一个 $ m \times l $ 矩阵，第 $ i $ 行是第 $ i $ 个密钥流；
- 计算每一列的汉明重量（即该比特位在 $ m $ 个密钥流中1的个数）；
- 若算法安全，每一列的汉明重量应近似服从正态分布 $ N(m/2, m/4) $。
测试方法
- 固定密钥，IV 从 0x00000001 开始递增；
- 生成 $ m $ 个密钥流，组成矩阵；
- 计算每列的汉明重量 $ \omega_j (j=1..l) $；
- 根据 $ m $ 的大小（如 $ 2^{20} $），将重量分为5组；
- 进行卡方拟合优度检验。
参考分布（$ m = 2^{20} $）
| 区间 | 理论概率 |
|---|---|
| 0 – 523857 | 0.2 |
| 523858 – 524158 | 0.2 |
| 524159 – 524418 | 0.2 |
| 524419 – 524719 | 0.2 |
| 524720 – 1048576 | 0.2 |
结论
- 通过：各帧对应比特位独立同分布，无帧相关性；
- 不通过：IV 递增方式导致密钥流出现模式，需修改 IV 重载阶段。
五、扩散性测试
测试目的
检测密钥或 IV 的每一比特变化是否对密钥流产生雪崩效应——即改变一比特输入，密钥流中大约一半的比特应发生变化。
测试原理
- 随机生成一个密钥 $ key $ 和一个 IV；
- 生成参考密钥流 $ C $（长度 $ l = 256 $）；
- 逐一改变密钥的每一比特（共 $ k $ 次），生成新密钥流 $ C_i $；
- 逐一改变 IV 的每一比特（共 $ v $ 次），生成新密钥流 $ C_{k+j} $；
- 计算每个新密钥流与 $ C $ 的异或结果 $ D $，得到一个 $ (k+v) \times l $ 的异或矩阵；
- 重复上述过程 $ m $ 次（例如 $ m = 1024 $ 或 $ 2^{20} $），得到 $ m $ 个这样的矩阵；
- 对每个矩阵位置（共 $ (k+v) \times l $ 个位置），统计 $ m $ 次实验中该位置为1的次数；
- 这些次数应服从正态分布 $ N(m/2, m/4) $。
测试方法
- 初始化零矩阵 $ M $（尺寸 $ (k+v) \times l $）；
- 重复 $ m $ 次：
- 随机生成 $ key, IV $，计算参考密钥流 $ C $；
- 依次翻转 $ key $ 和 $ IV $ 的每个比特，生成新密钥流并异或得到 $ D $；
- 将 $ D $ 按位加到 $ M $ 上（整数加法）；
- 得到最终的 $ M $ 矩阵，每个元素取值范围 $ 0..m $；
- 将 $ M $ 的所有元素按值分组（参考 $ m $ 值对应的分组边界）；
- 计算卡方统计量，判断是否与理论分布一致。
参考分布（$ m = 2^{20} $）
与帧相关性测试相同的五等分区间（0–523857, 523858–524158, …）。
结论
- 通过：每个输入比特的扩散均匀，满足雪崩准则；
- 不通过：某些输入比特对密钥流影响过小或过大，扩散性差，需修改初始化阶段。
总结
| 测试名称 | 固定变量 | 变化变量 | 统计对象 | 理论分布 |
|---|---|---|---|---|
| 种子密钥/密钥流相关性 | IV | 密钥 | $ key \oplus $ 前\(k\)比特密钥流的汉明重量 | $ B(k, 1/2) $ |
| 初始向量/密钥流相关性 | 密钥 | IV | $ IV \oplus $ 前\(v\)比特密钥流的汉明重量 | $ B(v, 1/2) $ |
| 帧相关性测试 | 密钥、IV递增步长 | IV 递增值 | 密钥流矩阵每列的汉明重量 | $ N(m/2, m/4) $ |
| 扩散性测试 | 无（随机生成） | 密钥与 IV 逐比特翻转 | 多次实验下同位置异或值的累加和 | $ N(m/2, m/4) $ |
- 这四项测试重点评估算法初始化阶段（密钥和 IV 载入）的统计特性，能有效发现简单的线性依赖或扩散不足。
- 测试通过并不代表算法绝对安全（例如无法抵抗代数攻击或时序攻击），但它们是序列密码评估的基本体检项。
- 若某项测试失败，通常提示需要修改算法初始化过程中的密钥/IV 重载机制或轮函数设计。