NIST随机数测试标准

NIST随机数测试（李璞编译）本文是根据NIST官方网站的说明书编译而成，仅为学术交流之用，请勿用作它途。如转载请注明出处！另因水平有限，欢迎批评指正。联系方式：Email：[e-mail]：太原理工大学光电工程研究所引言：这套NIST（国家标准与技术研究所）测试程序是一个统计包，包括16种测试手段。这些测试手段可测试由用作保密随机或者伪随机数发生器的硬件和软件产生的任意长的2进制序列的随机性。这些测试手段主要致力于判定可能存在于序列中的多种多样的非随机性。其中一些测试又可以分解成多种子测验。这16种测试手段是：1.频率检验，2.块内频数检验，3.游程检验，4.块内昀长游程检验，5.二元矩阵秩检验，6.离散傅里叶变换检验，7.非重叠模块匹配检验，8.重叠模块匹配检验，9.Maurer的通用统计检验，10.Lempel-Ziv压缩检验，11.线性复杂度检验，12.序列检验，13.近似熵检验，14.累加和检验，15.随机游动检验，16.随机游动状态频数检验。以下分别介绍这16种检测手段，这里须注意，下面讲到的很多例子里面的小样本仅仅是为了作示例性的说明，比如说，n=10。这个正态近似值并不适用于这些例子。2.1频数（一位）检验2.1.1检验目的该检验主要是看0和1在整个序列中所占的比例。检验的目的是确定序列中的1和0数是否与真正的随机序列中的1和0数近似相同。检验评定1码占1/2，也就是说，在整个序列中0和1的数目是一样的。其余别的检验手段都是在该检验成立的基础上进行的，并且没有任何证据表明被测序列是不随机的。2.1.2函数调用Frequency（n），这里n表示一串二进制序列的长度。函数中用的其余的参数来源于待检验的码：表示一串随机或者伪随机码序列，即=1，2，…，n。2.1.3检验统计量和参照分布sobs:Xi和的绝对值除以序列的长度，其中Xi=2e-1=。检验统计量的标准分布是半正态分布（当n很大时）。（注意：如果z（zsobs/2）服从正态分布，那么|z|就服从半正态分布。）如果序列是随机的，那么正负趋于互相抵消，这样检验统计量将约等于。如果有太多的或者太多的，那么将导致检验统计量比要大。检验过程（）变换作1：序列（）中的“0”和“1”变换做–1和+1，并相加得到，其中Xi=2-1。比如说，如果=1011010101，那么n=10，而21)1(1)1(1)1(11)11(ns。（2）计算统计检验量nSobsns在这个例子中632455532.0s102obs（3）计算P值)2(erfcPobss本例中527089.0)2632455532.0(erfcP2.1.5决策规则（在1%水平）如果计算出来的P值小于0.01，则判定序列是非随机的。否则序列是随机的。2.1.6结论以及检测结果的解释本例中P值大于0.01，所以判定该序列为随机序列。注意P值较小时（小于0.01），这是因为nS或者obss较大引起的，正值越大说明“1”码太多，负SnSn值越大说明“0”码越多。2.1.7输入序列尺寸建议每个待检测序列昀少应包含100位，即n大于等于100。2.1.8示例（input）（input）n=100（processing）（processing）（output）（conclusion）2.2块内频数检验2.2.1检验目的此检验主要是看M位的子块中“1”码的比例。该检验的目的是判定M位的子块内“1”码的频率是否像随机假设下所预期的那样，近似于M/2。当M=1时，该检测相当于检测1位，即频数（一位）检验。2.2.2函数调用BlockFrequency(M,n)：M代表每一块的长度。n代表整串序列的长度。函数中用的其余的参数来源于待检验的码：表示一串随机或者伪随机码序列，即=1，，…，n。2.2.3检验统计量表示M位子块内“1”码所占比例与预期的比例1/2的接近程度。该检验统计量的标准分布是分布。2.2.4检测过程（1）将输入的序列划分成个非重叠子块。（忽略无用的位）比如说，如果n=10，M=3，=0110011010，那么序列可分为三个子块，即011，001和101.昀后一位0应舍弃。（2）确定每个M位的子块中“1”码的比例：在本部分例子中，。（3）计算检验统计量：在上例中，。（4）计算P-值：，比如说，在本例中，2.2.5决策规则（当水平为1%）如果计算出来的P值小于0.01，则判定序列是非随机的。否则序列是随机的。2.2.6结论以及检测结果的解释由于2.2.4部分中第四步计算得到的P值大于0.01，所以该序列是随机的。注意一个小的P值（小于0.01）以为着至少在某一子块中“0”码和“1”码的比例与等比例的“0”、”1”码之间有个大偏差。2.2.7输入序列尺寸建议建议灭个待检验的序列至少要包含100位，即n要大于等于100。注意。M应当大于0.01n，并且N要小于100。2.2.8示例2.3游程检验2.3.1检验目的此检验主要是看游程的总数，游程指的是一个没有间断的相同数序列，即游程或者是“1111…”或者是“0000…”。一个长度为k的游程包含k个相同的位。游程检测的目的是判定不同长度的“1”游程的数目以及“0”游程的数目是否跟理想的随机序列的期望值相一致。具体的讲，就是该检验手段判定在这样的“0”“1”子块之间的振荡是否太快或太慢。2.3.2函数调用Runs(n)：n表示一串序列的长度。函数中用的其余的参数来源于待检验的码：表示一串随机或者伪随机码序列，即=1，，…，n。2.3.3检验统计量及其标准分布长度为n的序列中，总的游程数，即“0”游程的总数加上“1”游程的总数。检验统计量的标准分布是一个分布。2.3.4检验过程注意：游程检验是以频数检验成立为前提的。（1）计算检验前输入序列中“1”的个数：。例如，如果，则n=10、（2）判定“游程检验”的前提条件“频数检验”是否成立：、如果，那么“游程检验”无需进行。也就是说在这种情况下“频数检验”不成立，那么“游程检验”可免。如果该步检验不成立，那么P值设置为0.0000。注意对这步检验，已经在测试编码中提前定义了。在本部分的例子中，由于，故而也就是说处于被选范围之内，所以“游程检验“可以运行。（3）计算检验统计量，这里当时；反之，。由于这里的，故而（4）计算P值：本例中，2.3.5决策规则（在水平为1%）如果计算出来的P值小于0.01，则判定序列是非随机的。否则序列是随机的。2.3.6结论以及检测结果的解释由于在2.3.4的第4步中得到的P值是大于0.01的，所以我们的结论就是序列是随机的。注意：一个较大的值就意味着在序列中的振荡太快；而一个较小的则意味着振荡太慢。（一个振荡指的是一个从1到0的变化或者一个从0到1的变化）。一个快速振荡发生在有很多变化得时候，比如说010101010一位一振荡的情况。而一个慢速的振荡流的游程数要比理想的随机序列中的游程数少得多。比如说，一段由100个“1”的序列后面跟着一段73个“0”的序列，其后又跟着一段127个“1”的序列（总共300位）组成的长序列（总共300位），仅仅包含3个游程，然而理想的随机信号应当有150个。2.3.7输入信号尺寸建议每个待检验序列至少应包含100bits，即n不小于100。2.3.8示例2.4块内昀长游程检验2.4.1检验目的该检验主要是看长度为M-bits的子块中的昀长“1”游程。这项检验的目的是判定待检验序列的昀长“1”游程的长度是否同随机序列的相同。注意：昀长“1”游程长度上的一个不规则变化意味着相应的“0”游程长度上也有一个不规则变化，因此，仅仅对“1”游程进行检验室足够的。2.4.2函数调用LongestRunOfOnes（n），n表示一串序列的长度。函数中用的其余的参数来源于待检验的码：表示一串随机或者伪随机码序列，即=1，，…，n。M表示每个子块的长度。检验编码已经被提前设置，对应着不同的值有不同的n值，M取三个数值8、128、和10000。如下图所示：N表示子块的数目，与选择的M值相对应。2.4.3检验统计量及其标准分布表示在长度为M-bit的子块中被观察到得昀长游程与M-bit长的子块中的昀长长度的期望之间的匹配程度。检验统计量的标准分布是一个分布。2.4.4检验过程（1）将序列分作长度为M-bit的子块。（2）将各个子块中的昀长“1”游程的频率按类列成表格形式M值由测试编码（程序）给出，相应的具有下面的值，如表所示（3）计算，其中K和N的值由M值决定，如下图所示：在2.4.8中所举例子中，（5）计算P值例中的2.4.5决策规则（在水平为1%时）如果计算出来的P值小于0.01，则判定序列是非随机的。否则序列是随机的。2.4.6结论以及对检验结果的解释对于2.4.8中所举的例子，P值是大于0.01的，所以所检测的序列是随机的。注意，值大意味着被检验的序列中有太多的“1”.2.4.7输入信号尺寸建议每个待检验序列应包含的昀小bits当与2.4.2中所列的表格相一致。2.4.8示例2.5二元矩阵秩检验2.5.1检验目的该检验主要是看整个序列的分离子矩阵的秩。目的是核对源序列中固定长度子链间的线性依赖关系。2.5.2函数调用Ranking（n）n序列的长度另外一些被此函数使用的输入量由待检验的码决定：表示一串随机或者伪随机码序列，即=1，，…，n。M表示每个矩阵的行数。Q表示每个矩阵的列数。2.5.3检验统计量及其标准分布表示由序列分隔组成的矩阵中秩的数目与假设是随机数时秩的数目之间的匹配程度。检验统计量的标准分布是一个分布。2.5.4检验过程（1）将序列分成M*Q-bit的子块；那么将会出现个这样的子块。多余的位将被舍弃不用。然后将产生的各个子块组成M*Q的矩阵。每一行填入源序列中的连续Q-bit的子块。举例说明，如果则可以将其分成个矩阵。注意昀后面的两位（0和1）被舍弃。这两个矩阵是和注意第一个矩阵的第一排是昀前面的三位，第二行是随后的三位，第三行是接下来的三位。第二个矩阵的构成与第一个是相似的。（2）确定每个矩阵的秩，其中对于本部分的例子，第一个矩阵的秩是2，第二个的秩是3。（3）令FM=满秩矩阵的数目，FM-1=秩为满秩-1的矩阵数目，N-FM-FM-1=其余矩阵的数目。比如说在上面的例子中，N=0（4）计算上例中（6）计算P值在上例中，2.5.5决策规则（1%）如果计算出来的P值小于0.01，则判定序列是非随机的。否则序列是随机的。2.5.6结论及其解释由于2.5.4第（5）步计算得到的P值大于0.01，所以被检验的序列是个随机序列。注意，值大，因而P值小，这意味着被检验的序列的秩分布与相应的随机序列有一个偏离。2.5.7输入信号尺寸建议待测信号的位数昀小为n大于或者等于38MQ。2.5.8示例2.6离散傅里叶变换检验2.6.1检验目的本检验主要是看对序列进行分步傅里叶变换后的峰值高度。目的是探测待检验信号的周期性，以此揭示其与相应的随机信号之间的偏差程度。做法是观察超过95%阈值的峰值数目与低于5%峰值的数目是否有显著不同。2.6.2函数调用DiscreteFourierTransform（n），其中n表示序列的长度另外一些被此函数使用的输入量由待检验的码决定：表示一串随机或者伪随机码序列，即=1，，…，n。2.6.3检验统计量及其标准分布表示归一化后的观察到的和预期的超过95%阈值的频率数的差值。检验统计量的标准分布是一个正态分布。2.6.4检验过程（1）将序列中的“0”和“1”转换成“-1”和“+1”，其中比如说，如果，，则（2）对X进行离散傅里叶变换。（3）计算这里S’表示S的前n/2个元素。modulus函数产生一系列的峰值高度。（4）计算。在随机假设的前提下95%的峰高阈值不会超过T。（5）计算超过95%阈值的峰的个数，小于T。上例中，（6）计算M个峰中实际观察到的峰高小于T的峰的个数。上例中，（7）