密码学：如何区分真随机与有偏随机数生成器？需多少样本及偏差阈值？

在密码学场景下区分真随机数生成器（TRNG）和有偏随机数生成器（BRNG），核心依赖统计假设检验、概率界与信息论相关的定理，下面是最实用的几个方向：

1. 二项分布假设检验（针对比特流偏差） #

如果是检测二进制随机数的0/1比例偏差（最常见的场景），可以用单样本比例假设检验：

• 假设TRNG的比特服从无偏二项分布（真实概率p=0.5），BRNG的p≠0.5，偏差大小为ε = |p - 0.5|
• 设定显著性水平α（密码学中通常取0.0001，控制误判TRNG为有偏的概率）和功效β（通常取0.99，控制漏检BRNG的概率）
• 所需最小样本量n可通过正态近似计算：

  n ≈ (z_{1-α/2} + z_{1-β})² * 0.25 / ε²
  

  其中z_{x}是标准正态分布的x分位数。比如ε=0.01、α=0.0001、β=0.99时，n约为130万比特。

2. Chernoff界（快速估算偏差检测下限） #

Chernoff界给出了独立同分布样本均值偏离真实均值的概率上界，适合快速估算所需样本量：

• 对于任意ε>0，样本均值与真实均值偏差≥ε的概率满足：

  Pr[|(1/n)ΣX_i - μ| ≥ ε] ≤ 2e^{-2nε²}
  

• 如果你想以1-δ的概率检测出≥ε的偏差（δ为漏检概率，密码学中通常取1e-12级），解不等式可得：

  n ≥ ln(2/δ)/(2ε²)
  

  比如ε=0.005、δ=1e-12时，n约为56.6万比特。

3. KL散度（量化分布区分度） #

从信息论角度，TRNG与BRNG的概率分布差异可以用KL散度D_KL(P||Q)衡量，其中P是TRNG的分布，Q是BRNG的分布。区分两个分布所需的样本量满足：

n ≥ D_KL(P||Q)^{-1} * ln(1/δ)

对于二进制无偏vs有偏场景，KL散度近似为2ε²/ln2（当ε很小时），代入后结果和Chernoff界一致。

4. 工程化参考：NIST SP 800-22测试套件 #

密码学中常用的NIST随机性测试套件，把上述定理转化为可直接执行的测试标准：

• 每个测试（如频率测试、游程测试）都有最低样本量要求（比如频率测试最少100比特，实际应用中通常用1e6比特以上）
• 判定阈值为p值≥0.0001：如果测试得到的p值低于这个阈值，就认为样本存在显著偏差，大概率来自BRNG。

实用注意点 #

• 偏差阈值的选择要结合场景：密码学密钥生成对偏差容忍度极低（比如ε=1e-6都可能被利用），非敏感场景可适当放宽；
• TRNG也会有统计涨落：有限样本中TRNG可能出现暂时的比例偏差，必须通过统计显著性检验，不能仅凭单次小样本结果判定。

内容的提问来源于stack exchange，提问作者Cys