随机性检测及其片面性

On the randomness test and its incompleteness

现有随机性检测规范由于没有系统地讨论统计检验和随机本质的联系,难以指导实际的安全性评估工作。通过随机性的不可区分性定义,论证了随机性检测在理想情况下需要考察所有概率多项式时间算法的区分情况,因此对随机性进行完备的检测理论上只能是无效的。由伪随机生成器的定义及其可证明性,论证了当随机种子较短时可通过构造概率分布并验证不可区分性证明的方法来检测伪随机性;并论证了对随机种子较长的伪随机生成器和非确定性随机生成器进行统计检验的必要性,运用概率工具证明了样本量与置信区间在进行统计检验时的定量关系。最后例证了NIST SP800-22中的统计检验方法无法探出某些明显的非随机特征。研究结果表明:实际可行的检测方法能检测出某些非随机特征,但无法给出随机性的断言。

Randomness test specifications do not demonstrate the relationship between statistical tests and the nature of randomness,thus providing little guidance for practical security evaluations.The indistinguishability definition of randomness states that randomness tests ideally have to investigate all probabilistic polynomial algorithms,hence testing randomness with completeness is theoretically impossible.Pseudorandomness can be tested by verifying the probabilistic distribution of the seed and the correctness of the claimed indistinguishability proofs for short random seeds.Further,pseudorandom generators with long seeds and non-deterministic random generators require statistical tests,while the quantitative relationship between sample size and significant level in statistical tests is also proved by applying Chebyshev＇s multivariate inequality and statistical techniques.An example is given to demonstrate that the statistical tests in specification NIST SP800-22 may not detect the obvious non-randomness of some contrived sequences.These results show that practical testing approaches can only detect non-randomness to some degree,but cannot be used to certify randomness.