📚 课程目录第3章随机性度量与统计检测基础

3. 随机性度量与统计检测基础

在量子随机数后处理与模块集成工程中，“随机性”并不是一个可以直接测量的物理量，而是通过统计模型和假设检验间接推断的性质。工程上必须区分两类问题：一类是信息论意义上的不确定性度量，如香农熵、最小熵；另一类是统计假设检验，如 NIST SP 800-22、Dieharder、TestU01。前者回答“一个输出序列最多能提供多少不可预测性”，后者回答“给定序列是否与理想随机模型显著不符”。两者不能互相替代。

一、熵的三种常用度量

设随机变量 X 取值于集合 𝒳，概率分布为 p(x)。香农熵定义为 H(X) = −Σ p(x) log₂ p(x)，单位是比特，描述平均不确定性。若 X 均匀分布于 2ⁿ 个取值，则 H(X)=n。香农熵适合描述“平均每个符号携带多少信息”，但它对低概率事件不敏感，不能直接用于密钥安全性评估。

最小熵定义为 H_∞(X) = −log₂ max_x p(x)，它描述最可能取值的可预测性上界。若某分布最大概率为 2^−k，则最小熵为 k 比特。在量子随机数提取中，最小熵是安全参数的核心：提取器只能从最小熵为 k 的原始源中提取出接近 k 比特的均匀随机位。例如，若原始源每个采样点有 8 位量化输出，但最大概率为 0.1，则最小熵约为 −log₂0.1 ≈ 3.32 比特，远低于 8 比特。

碰撞熵 H₂(X) = −log₂ Σ p(x)² 介于香农熵与最小熵之间，常用于估计提取器可达到的速率。工程中通常先用最小熵做保守安全下界，再用香农熵或碰撞熵评估后处理效率。

工程提示：最小熵必须基于对原始物理源的建模或保守假设得到，不能由统计检测套件“通过”反推。检测通过只说明未发现显著偏差，不给出熵下界。

二、统计检测套件的定位与差异

NIST SP 800-22 是最常用的随机性检测套件，包含频率、块内频率、游程、最长 1 游程、二元矩阵秩、离散傅里叶变换、非重叠模板匹配、重叠模板匹配、Maurer 通用统计、线性复杂度、序列、近似熵、累加和、随机游走、随机游走变量等 15 项检验。每项检验输出一个 p 值，通常以 p ≥ 0.01 作为单次通过判据。工程中更关注p 值均匀性和通过率：对多个序列分别检验，p 值应近似均匀分布于 [0,1]，通过率应接近 1−α。

Dieharder 在 Diehard 基础上扩展，提供约 30 余项检验，支持多种伪随机数发生器和文件输入，适合快速筛查。TestU01 则提供 SmallCrush、Crush、BigCrush 三个层级，BigCrush 包含约 160 项检验，统计功效强，常用于 PRNG 的严格评估。三者定位不同：NIST SP 800-22 偏重密码学应用与标准化流程，Dieharder 偏重快速批量筛查，TestU01 偏重对生成器弱点的深度挖掘。

三、工程适用边界与常见误用

统计检测套件最容易被误用的地方，是把“通过 NIST SP 800-22”当作“随机数安全”的证明。实际上，任何检测套件都只能发现它设计时针对的特定偏差模式。一个序列完全可能通过全部 15 项 NIST 检验，但仍然具有可预测结构，例如由某个未知线性反馈移位寄存器生成、周期极长且统计性质良好的序列。检测套件不提供计算安全性证明，也不提供最小熵下界。

另一个边界是样本量与检验功效。NIST SP 800-22 建议每条序列至少 10⁶ 比特，且对多项检验需要更长序列才能获得足够功效。若用 10⁴ 比特去跑全部检验，很多检验的 p 值分布会严重偏离均匀，产生大量假阳性或假阴性。工程中应固定样本长度、检验项集合和显著性水平 α，并记录每次运行的 p 值分布，而不是只记录“通过/失败”。

此外，检测套件对后处理输出的检验与对原始源的检验目的不同。原始源通常存在明显偏置和相关性，直接跑 NIST 套件大概率失败，这并不说明源不可用，而是说明需要提取器。正确的流程是：先对原始源做物理建模与最小熵估计，再设计提取器（如 Toeplitz 哈希、AES-CBC-MAC、SHA-3 派生），最后对提取器输出跑统计检测，确认后处理没有引入新的结构性缺陷。

四、一个可复用的检测配置示例

以下给出一个工程中可直接参考的检测配置片段，用于对后处理输出做例行筛查。参数为示例值，实际项目应根据源速率、安全等级和算力调整。

# 示例：NIST SP 800-22 检测配置（假设已安装 sts）
# 输入：postprocessed.bin，长度 100,000,000 bit = 12.5 MB
# 显著性水平 alpha = 0.01
# 检验项：frequency, block_frequency, runs, longest_run_1s,
#         dft, approximate_entropy, cumulative_sums, random_excursions

./assess 100000000
# 选择输入文件 postprocessed.bin
# 选择检验项 1,2,3,4,6,10,13,14
# 每条流序列数：100
# 输出：p 值列表与通过率统计

# 判读规则（示例）：
# 1) 单项通过率应落在 [0.99 - 3*sqrt(0.99*0.01/100), 0.99 + 3*sqrt(...)]
#    即约 [0.960, 1.000]
# 2) p 值均匀性检验（如 chi-square）不应拒绝均匀分布
# 3) 若某项通过率低于下界，先增加样本量复测，再排查提取器实现

判读时要注意：通过率下界随序列条数变化，不能机械套用 0.96。若只跑 10 条序列，置信区间会宽得多。更稳健的做法是记录多轮运行的 p 值，用 Kolmogorov-Smirnov 或 chi-square 检验其均匀性，而不是只看单轮通过率。

常见错误：把 Dieharder 或 TestU01 的“通过”当作熵源认证。检测套件是筛查工具，不是安全证明。量子随机数模块的熵评估必须回到物理源模型、最小熵估计和提取器安全性分析三条主线。

总结来说，熵度量回答“有多少不可预测性”，统计检测回答“是否发现显著偏差”。前者决定提取器的安全参数，后者用于验证后处理输出和实现正确性。工程中应把两者作为互补环节：先用最小熵确定可提取的安全比特数，再用 NIST SP 800-22 或 TestU01 对提取器输出做例行筛查，并始终保留 p 值分布和样本量等原始记录，以便复现和审计。