随机序列的检验

四、随机序列的检验

在信息安全领域的基本标准有美国商务部国家标准技术协会NIST发布的ITSEC、CC及FIPS系列标准。对于真随机数发生器而言，常用的评价标准有德国BSI在2001年9月25日发布的AIS31标准。高质量的随机数序列必须通过一系列的统计检验。结合上述标准可设计出合适的检验方法，主要用于检测随机序列的分布均匀性、相关性等。常用的检验方法如下：

1．比特分布检测。这是随机数发生器最基本的检测标准，用以判断随机序列是否满足分布的均匀性。主要测试长为n比特的序列中0和1的个数，理想情况0和1等概率分布。

2．跟随特性检测（又称转移检测）。序列的跟随特性指序列中相邻元素的出现情况。主要用来测试长为n比特的序列中00，01，10，11的概率是否相等。采样低频采样的措施有利于保证输出数的跟随特性。

3．游程检测。游程是由连续0或者1组成的序列，并且其前后元素与游程的元素不同。游程数目为序列长度的一半时，产生的随机序列较好。

4．碰撞检测。这种检测法是以抽象概率试验小球碰撞为比喻的。假定我们将n个小球随机的扔进m个空的缸里，这里m>>n，当小球掉进非空的缸里时我们认为碰撞发生。理论上，一个缸里有k个球的概率为：

因此碰撞次数的期望值为：

5．扑克检测。扑克检测先将待测序列划分成若干个长为m（m为任意正整数）的二进制子序列，长为m的二进制子序列有2m种类型，然后检测这2m种子序列类型的个数是否相等。

此外，随机序列的检测方法还有相关性检测、线性复杂度检测、长游程检测等。