随机性检测及其片面性

摘要

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