基于SP 800-22标准的随机性测试方法研究与快速实现*

2018-09-03段俊红韩炼冰房利国

通信技术 2018年8期

段俊红，韩炼冰，房利国

（中国电子科技集团公司第三十研究所，四川成都 610041）

0 引言

随机数在众多科学研究和工程技术领域都有着广泛应用。特别是在信息安全领域，随机数作为密码应用的一个重要组成部分，在众多密码算法及密码协议中起着至关重要的作用[1]。安全、高速地产生强随机性的随机数，一直是信息安全领域的重点关注问题。

物理随机数发生器利用自然界的随机物理过程，可获得不重复、不具备周期性的随机序列，被广泛应用于金融、政府和军事等行业的信息安全保密通信设备。但是，在实际使用过程中，由于环境的复杂性和元器件的耗损等，都可能造成物理随机数发生器自身性能的下降[2]。一个有缺陷的随机数序列可能会导致整个安全保密系统被攻击者攻破，从而导致严重的安全漏洞。因此，当随机数应用于安全保密系统时，必须对其进行随机性测试。

1 SP 800-22标准简介

随机性测试通常通过概率统计的方法考察被检测序列是否满足随机序列的某些特征（如周期性、相关性和分布特性等），从而判定其是否随机[3]。目前，国际上的随机性测试方法200多种，其中美国国家标准技术学会（NIST)制定的SP 800-22标准是最具代表性的方法之一。该标准专门用于对密码应用中的随机数和伪随机数发生器产生的二进制随机数序列进行统计测试。

1.1 SP 800-22标准定义的测试项

SP 800-22标准在最开始制定时共定义了16个测试项来检验二进制序列的随机性。2010年，NIST又发布了一个新的版本（SP 800-22 revision 1a），里面共定义了15个测试项[4]。和原来的标准相比，减少了“Lempel-Ziv压缩测试”这一测试项。每个测试项通过选取一个特定的统计量，计算观察值是否符合理论分布，以此确定待测序列在某方面是否存在规律[5]。如果能检测到这种规律，则认为序列是不随机的；反之，则认为序列是随机的。例如，单比特频数测试通过查看序列中0和1的个数是否近似相同来判断序列是否随机。

由于每个测试项只能检测到序列在某一方面的特性，如果只通过某一项测试，并不能说明序列一定是随机的。例如，二进制序列“000000111111”能通过单比特频数测试，但它显然不是一个随机序列。因此，在实际使用过程中，应根据需要选择适当的测试项进行测试。

1.2 SP 800-22标准定义的测试项

NIST在制定SP800-22标准的同时，还发布了一个随机性测试包“sts-2.1.2”。该测试包提供了标准定义的所有测试项和一些测试样例的C语言源代码。利用测试包可以直接在Linux平台生成一个可执行程序“assess”。该程序可以对外部输入或程序自己生成的随机数进行随机性测试，并将测试结果输出到特定目录的指定文件中。

2 部分测试项的快速实现

对随机数进行随机性测试，通常需要对待测数据进行逐比特的数值判断和数学运算才得到统计量值，有时还要通过若干轮的逐比特运算。同时，统计测试公式也会涉及很多复杂的数学运算，如开方、对数、积分等，因此对大量数据进行随机性测试是一个非常耗时的过程。

如果是在嵌入式平台中进行随机性测试，由于其运算能力有限，耗时将会更久。在需要对大量数据进行随机性在线测试的应用场合中，对SP800-22标准定义的测试项进行研究和快速实现是非常必要的。受于篇幅限制，下面仅对部分测试项的快速实现方法进行介绍。

2.1 频数测试快速实现

在SP 800-22标准中，对n比特二进制序列进行频数测试的步骤如下：

（1）将序列中的0和1转换为-1和+1，并相加得到Sn；

（2）根据式（1）计算P值，如果P＜0.01，则判定序列是非随机的。

该测试项最耗时的是步骤（1）的Sn值计算。本文采用与文献[6]相似的方法对频数测试进行快速实现。方法主要包括以下几方面内容：

（1）每个内存单元中不只存1比特数据，而是8比特数据，便于一次处理多比特数据；

（2）利用查表法直接得到转换后序列的8比特和；

（3）优化统计测试公式，降低计算复杂度。

根据erfc函数的计算方法可知，erfc(1.821 39)=0.01 erfc(1.821 40)=0.009 99，当n=1 000 000时，有：

因此，当n=1 000 000时，如果Sn绝对值大于2 575，则判定序列是非随机的。

2.2 游程测试快速实现

在SP 800-22标准中，对n比特二进制序列进行游程测试的步骤如下：

（1）计算待测序列中‘1’的比例π，并检查下面的判定公式是否成立。如果不成立，则判定序列为不随机，无需进行后面的测试；

（2）如果式（4）成立，则计算测试统计量V：

根据式（6）计算P值，如果P＜0.01，则判定序列是非随机的。

游程测试最耗时的是步骤（1）的π值计算和步骤（2）的V值计算。其中，计算V值时需要依次对序列中的连续2比特数据进行比较，如果不相同，则将V值加1。

游程测试的快速实现方法为：

（1）共享频数测试中对序列中‘1’的统计值，或采用与其相同的方法计算‘1’的统计值；

（2）利用查表法直接得出8比特数据的V值。

查找表大小为256 Byte，建立方法为：表中第i个数据的值Ti与i值相同的8位二进制序列的游程个数。例如，当i=5时，Ti=4。同时，如果当前8比特的最高位和前一个8比特的最低位相同，则将V值减1。

2.3 序列测试快速实现

在SP 800-22标准中，对n比特二进制序列进行游程测试的步骤如下：

（1）构建扩张序列，将待测序列的第一个m-1比特加到整个序列的末尾；

（2）确定所有可能的重叠m比特、m-1比特、m-2比特模式的子序列出现的个数，分别用Vi1…Vim，Vi1…Vim-1和 Vi1…Vim-2表示；

（3）令 x=m、x=m-1和 x=m-2，计算 φ2m、和的值：

（5）计算P1和P2的值；

（6）如果P1＜0.01，或者P2＜0.01，则判定序列是非随机的。

通过观察上面的测试步骤可以发现，测试中最耗时的是步骤（2）。NIST的统计测试包通过一个通用的方法来计算扩张序列所有可能的重叠x比特，该方法的具体实现步骤为：

（1）定义局部变量k、i，初始值分别设为1和0；

（2）定义一个具有2x+1-1个元素的数组变量P[·]，每个元素的初始值都设为0；

（3）将序列划分为n/x个非重叠子序列；

（4）对于每一个子序列，依次判断每个比特的值，如果值为1，则令k=k+1；如果值为0，则令k=2k+1；

（5）每个子序列判断结束后，令P[k-1]=P[k-1]+1，同时令k=1。

m值的不确定性是运算耗时的一个重要因素。而在实际应用过程中，m值通常固定为3。因此，当m=3时，游程测试的快速实现方法如下：

（1）采用查表法计算序列中所有可能的重叠3比特模式的子序列出现的次数。

首先，建立两个查找表，每个查找表由256个32位数据组成。查找表内每个数据再按8比特宽度分为四个部分。第一个查找表中第i个数据的四部分，分别记为T1i1、T1i2、T1i3和T1i4；第二个查找表中第i个数据的四部分，分别记为T2i1、T2i2、T2i3和T2i4。其中，T1i1～T1i4分别为将i转化为8位二进制序列后重叠的000、001、010和011子序列出现的次数；T2i1～T2i4分别为将i转化为8位二进制序列后重叠的100、101、110和111子序列出现的次数。

接下来，查表统计序列中所有可能的重叠3比特模式的子序列出现的次数。因为是重叠3比特进行统计，所以如果上一次是使用序列中第j～j+7位进行查表的，那本次将使用序列中第j+6～j+13位进行查表。

（2）采用查表法计算序列中所有可能的重叠2比特模式的子序列出现的次数。

首先建立查找表，但与3比特模式不同，这里只需要建一个表即可。查找表由256个数据组成，每个数据的宽度为32位。查找表内每个数据再按8比特宽度分为四个部分，分别记为Ti1、Ti2、Ti3和Ti4。Ti1～Ti4分别为将i转化为8位二进制序列后重叠的00、01、10和11子序列出现的次数。

接下来，查表统计序列中所有可能的重叠2比特模式的子序列出现的次数。对于2比特模式，如果上一次是使用序列中第i～i+7位进行查表的，那本次将使用序列中第i+7～i+14位进行查表。

（3）采用查表法计算序列中所有可能的重叠1比特模式的子序列出现的次数。此时，问题转化为统计序列中‘0’和‘1’出现的次数。快速实现方式同“频数测试”。

2.4 二元矩阵秩测试快速实现

在SP 800-22标准中，对n比特二进制序列进行二元矩阵秩测试的测试步骤如下：

（1）将序列分成N个M*Q比特的子块，并舍弃多余位；

（2）将产生的各个子块组成M*Q的矩阵，计算每个矩阵的秩Ri，其中i=1,2,…,N；

（3）令FM为满秩矩阵的个数，FM-1为秩为满秩减1矩阵的个数，T=N-FM-FM-1，并计算统计量V；

（4）计算P值（P=e-V/2），如果P＜0.01，则判定序列是非随机的。

该项测试最耗时的是步骤（3）（求矩阵的秩），NIST的统计测试包通过行变换将矩阵化简为三角矩阵，再通过统计主对角线上1的个数得到矩阵的秩。具体方法为：

（1）申请一个M*N的二维数组空间，将测试序列中的比特值依次放入数组空间中；

（2）检查第i行i列的值是否为1。如果为1，则转到步骤（3）；如果为0，则在第i列中从第i+1行开始依次递增一行找值为1的元素，找到后将该行所有元素的值与第i行进行互换；

（3）在第i列中，从第i+1行开始依次递增一行找值为1的元素，找到后将该行从第i列开始的元素与第i行从第i列开始的元素依次异或至行尾，并将结果存回该行对应位置；

（4）i值加1并检查i值，如果i≠M-2，则返回步骤（2），否则设定i=M-1；

（5）检查第i行i列的值是否为1。如果为1，则转到步骤（6）；如果为0，则在第i列中从第i-1行开始依次递减一行找值为1的元素，找到后将该行所有元素的值与第i行进行互换，并转到下一步；

（6）在第i列中，从第i-1行开始依次递减一行找值为1的元素，找到后将该行所有元素与第i行所有元素依次异或，并将结果存回该行对应位置；

（7）i值减1并检查i值，如果i≠1，则返回步骤（5），否则结束变换。

由于SP 800-22标准中并没有对M和Q值做具体规定，只是要求n≥38MQ。因此，本文选择标准的推荐值（M=Q=32）。此时，二元矩阵秩的快速实现方法为：

（1）申请32个32位数组空间，将测试序列中按字节存放的值放入数组空间中，并设定i=0；检查数组中第i个元素的第31-i比特是否为1。如果为1，则转到步骤（3）；如果为0，则从数组第i+1个元素开始依次递增一个找第31-i比特为1的元素，找到后将该元素的值与第i个元素进行互换；

（2）从数组第i+1个元素开始依次递增一个找第31-i比特为1的元素，找到后将该元素从第31-i比特开始与数组第i个元素从第31-i比特开始依次异或至比特31，并将结果存回该元素对应比特位；

（3）i值加1并检查i值，如果i≠M-2，则返回步骤（2），否则设定i=M-1；

（4）检查数组中第i个元素的第31-i比特是否为1。如果为1，则转到步骤（6）；如果为0，则在第i列中从第i-1个元素开始依次递减一个找第31-i比特为1的元素，找到后将该行所有元素的值与第i行进行互换，并转到下一步；

（5）从数组第i-1个元素开始依次递减一个找第31-i比特为1的元素，找到后将该元素与第i个元素异或，并将结果存回该元素；

（6）i值减1并检查i值，如果i≠1，则返回步骤（5）；

（7）优化统计测试公式，降低计算复杂度。

因为e-9.210 44/2=0.010 0，e-9.210 441/2=0.009 9，同时根据e-V/2函数的性质可知，对P值判定可以改为对V值判定：如果V大于9.210 44，则判定序列是非随机的。

3 测试及结果分析

使用的测试平台为Intel Core i5 @3.30 GHz处理器4 GB DDR3 1 600 MHz内存、Windows XP SP3操作系统、Visual Studio 2010开发环境。测试样本为利用NIST随机性统计测试包“sts-2.1.2”产生的1 000 000比特伪随机数。分别使用NIST测试包和快速实现后的随机性测试程序对样本数据进行测试，并记录每项测试需要的时间，时间单位为μs，结果如表1所示。