Q_Value检测: 一种新的随机数统计检测方法

Abstract

随机数在密码与安全技术方面使用广泛, 随机数的产生和使用过程中, 需要对随机数的随机性进行检测, 统计检测是一种普遍采用的随机数检测方法, 其中NIST发布的SP 800-22统计检测包是国际上常采用的统计检测方法, 它包含15个检测项目, 每个检测项又分为一级检测和二级检测. 对于SP 800-22的正态分布型检测项目, 我们发现这些检测项目的二级检测是不完备的, 即通过这种检测的随机序列仍有可能在所检测的统计特性上存在缺陷. 这是因为, 正态分布型的检测计算出的P_value适用于一级检测, 不适用于二级检测, 因为在二级检测中, 即使该P_value分布均匀, 被测序列通过检测, 这个序列也不一定满足所检测性质, 为此, 不同于原标准二级检测中的P_value均匀性检测, 本文提出了Q_value的均匀性检测作为正态分布型检测项目的二级检测, 并且给出了Q_value参数的非渐进分布, 我们发现相比于P_value, Q_value的分布更接近于均匀分布, 用于新的检测能降低误检率提高可靠性. 最后, 本文通过实验证实Q_value检测能够发现一些更为隐蔽的统计缺陷.

Alternate abstract:

Random numbers are widely used in cryptography and information security techniques. When generating and using random sequences, we need to test their randomness. Statistical test is a traditional testing method for random numbers. The NIST SP 800-22 Statistical Test Suit is one of the most common-used test suits, which contains 15 test items. Each test item is composed of first-level test and second-level test. In SP 800-22, for normal distribution based test items, we found that their second-level tests are not complete, as the statistical flaws may still exist in the sequence even if the sequence passes the test item. The P_value which is computed during the normal-distribution-test can apply to the first level test, but it does not fit the second level test. Because in the second level test, the random sequence does not always satisfy the tested features, even if this P_value is equally distributed and the random sequence passed the test. For this reason, in contrast to the original standard level two test which assesses the uniformity of P_value, we introduce Q_value and propose to assess its uniformity in the second-level test. We also give a non-asymptotic distribution of Q_value. We found that the distribution of Q_value is much closer to the uniform distribution than the P_value, and it can reduce false test rate. Thus, it is more reliable to take it as the test item of the second level test. Finally, through the experiments, we demonstrate that the Q_value is able to find some more subtle statistical flaws of the tested sequence.