NIST随机性检测方法研究

王 超，温 涛，段冉阳

(中国电子信息产业集团有限公司第六研究所，北京 100083)

0 引言

近年来，我国信息化建设步伐不断加快，移动通信系统、卫星通信系统和物联网系统飞速发展，这些系统中的敏感信息需要密码技术来保证信息安全。尽管密码安全并不等于信息安全，但是如果没有密码安全，对整个系统安全而言将是灾难性的。因此，从这个角度来看，密码安全是信息安全的基石，研究密码安全对信息安全具有重要意义。

对输出的序列进行随机性检测[1-3]是评价密码安全的一个重要手段。美国国家标准与技术研究所(National Institute of Standards and Technology，NIST)发布的NIST统计检测程序sts-2.1.2(The NIST Statistical Test Suite)[4]，包括15种随机性检测方法和9种伪随机数生成器。15种随机性检测方法[5-6]分别从不同的角度刻画输出序列的伪随机性质。

本文首先介绍NIST统计检测程序，然后阐述NIST统计检测程序的不足以及如何改进。这些改进包括增加容忍度概念，从而扩展检测程序框架；增加统计量T，从而非重叠模板匹配检验输出唯一结论。

1 统计学基础

检测密码算法输出序列的随机性，即检验其是否真随机或与真随机之间的差距，通常采用统计学中假设检验方法。

首先，视密码算法输出序列为二进制序列，是仅由0、1组成的二元序列，进行随机性假设。假设该序列是随机的，这个假设称为源假设或零假设，记为H0。与源假设相反的假设，即这个序列是不随机的，称为备择假设，记为H1。已知真随机序列上构造出的某统计量符合某一特定分布，那么通过源假设，即假设二元序列是随机的，可知此二元序列的这个样本统计量也应该服从这个特定分布。分布可以是均匀分布、开方分布等。

其次，每一个检验可能犯两种类型的错误，如表1所示。

在样本容量固定时，犯这两类错误的概率是相互制约的，无法使得它们同时尽可能地小。在检验中错误地判断某一个随机序列为非随机序列的概率(即表1中的第一类错误概率)，称为显著性水平，用a来表示。

表1 统计检验错误概率

判断源假设成立的方法有2类：门限值方法和Pvalue方法。

门限值方法：按指定的显著性水平a，查指定分布的分位数表，得到临界值，确定拒绝域。计算二元序列的样本统计量，如果统计量落入源假设的拒绝域，则拒绝H0，否则接受H0。

Pvalue方法：Pvalue值为1代表完全随机序列，值为0代表完全非随机序列。于是，若Pvalue≥a，则接受H0，否则拒绝H0。

一般直接与假设总体分布对照时使用门限值方法，而与补余误差函数(Complementary Error Function)、不完全伽马函数(Incomplete Gamma Function)对照时使用Pvalue方法。NIST统计检测程序采用Pvalue方法。

显著性水平a通常取值为0.1，0.05，0.01，0.005，NIST统计检测程序中显著性水平的缺省值为0.01。

2 NIST统计检测程序

NIST发布的NIST统计检测程序sts-2.1.2，包含频数检验、块内频数检验、游程检验、块内最长游程检验、二元矩阵秩检验、离散傅里叶检验、非重叠模板匹配检验、重叠模板匹配检验、Maurer通用检验、线性复杂度检验、重叠子序列检验、近似熵检验、累加和检验、随机游动检验、随机游动状态频数检验，共计15种随机性检测方法。

(1)频数检验

单比特频数检验简称为频数检验，是观测1在二元序列中所占的比例，考查其是否与真随机序列中的1所占比例近似相同。1在真随机序列中占比为1/2。频数检验的参数是二元序列的比特长度和二元序列本身。检验过程中使用了补余误差函数。频数检验要求二元序列比特长度至少为100。

(2)块内频数检验

块内频数检验是观测1在所有非重叠M比特长子序列(称为块)中所占的比例，真随机序列中占比为M/2。块内频数检验的参数是二元序列的比特长度、分组比特长度M和二元序列本身。检验过程中使用了不完全伽马函数。块内频数检验要求二元序列比特长度至少为100，分组比特长度至少为20且分组比特长度大于二元序列比特长度的1%。从而分组的块数(即二元序列的比特长度/分组比特长度M向下取整)小于100。

(3)游程检验

游程检验是观测二元序列中游程(即0游程和1游程)总数是否与相应真随机序列游程总数接近。0游程是指二元序列中由连续的0组成的子序列，并且此子序列的前导与后继元素都是1;1游程是指二元序列中由连续的1组成的子序列，并且此子序列的前导与后继元素都是0。游程检验展示了二元序列中0游程和1游程之间的距离(即振幅)与真随机序列相比是否太大或太小。游程检验的参数是二元序列的比特长度和二元序列本身。检验过程中使用了补余误差函数。游程检验要求二元序列比特长度至少为100。

(4)块内最长游程检验

块内最长游程检验是观测非重叠M比特长块中最长游程长度是否与真随机序列中最长游程长度近似致。块内最长游程检验的参数是二元序列的比特长度、分组比特长度M和二元序列本身。其中分组比特长度M由预设算法决定，即当二元序列比特长度小于6 272时取值为8，当小于750 000时取值为128，当大于等于750 000时取值为10 000。检验过程中使用了不完全伽马函数。块内最长游程检验要求二元序列比特长度至少为128。

(5)二元矩阵秩检验

二元矩阵秩检验是观测二元序列中分离子矩阵的秩是否与真随机序列的情况接近。二元矩阵秩检验的参数包括二元序列的比特长度和二元序列本身。NIST统计检测程序中约定子矩阵为32行32列。检验过程中使用了不完全伽马函数。二元矩阵秩检验要求二元序列比特长度至少为38 912(38×子矩阵行数×子矩阵列数)。

(6)离散傅里叶检验

离散傅里叶检验是观测二元序列进行离散傅里叶变换后峰值的数目是否与真随机序列的情况接近。离散傅里叶检验的参数包括二元序列的比特长度和二元序列本身。检验过程中使用了补余误差函数。离散傅里叶检验要求二元序列比特长度至少为1 000。

(7)非重叠模板匹配检验

非重叠模板匹配检验，是观测二元序列中与预先指定的m(m取值为9或10，本文采用9)比特长非周期二元序列匹配次数是否与真随机序列的情况接近。这样的m比特长非周期二元序列有多个，由模板定义，NIST统计检测程序中指定148组9比特二元序列。非重叠是指当发现匹配序列后，检测窗口跳至匹配序列整体之后再继续检测。非重叠模板匹配检验的参数包括二元序列的比特长度和二元序列本身。本文的非重叠模板匹配检验由148个子检验组成。检验过程中使用了不完全伽马函数。NIST统计检测程序中约定分组块数N=8，分组比特长度M=n/N。

(8)重叠模板匹配检验

重叠模板匹配检验是观测二元序列中与预先指定的m比特长非周期二元序列(NIST统计检测程序中约定为m个比特1)匹配次数是否与真随机序列的情况接近。重叠是指当发现匹配序列后，检测窗口跳移至下一比特，然后继续检测。重叠模板匹配检验的参数包括二元序列的比特长度和二元序列本身。检验过程中使用了不完全伽马函数。重叠模板匹配检验中每一个模板的比特长度m取值为9或10(本文采用9)，二元序列比特长度至少为106，NIST统计检测程序中约定自由度K=5(考查0次、1次、…、5次及以上，共6类)，分组比特长度M=1 032，分组的块数N=n/M。

(9)Maurer通用检验

Maurer通用检验是考查二元序列在没有信息损失的条件下能否进行显著压缩。真随机序列不能被显著压缩。Maurer通用检验的参数包括二元序列的比特长度和二元序列本身，内部分组长度L、初始分组数Q、检测分组数K由算法依据二元序列的比特长度计算得到。检验过程中使用了补余误差函数。Maurer通用检验要求二元序列比特长度至少为387 840。

(10)线性复杂度检验

线性复杂度检验是观测二元序列对应的线性反馈移位寄存器(LFSR)的长度(称为线性复杂度)是否足够大。真随机序列的线性复杂度较大。线性复杂度检验的参数是二元序列的比特长度、分组比特长度M和二元序列本身。NIST统计检测程序中约定自由度K=6。检验过程中使用了不完全伽马函数。线性复杂度检验中二元序列比特长度至少为106，分组比特长度M介于500与5 000之间，本文取M=500。

(11)重叠子序列检验

重叠子序列检验是观测二元序列中m比特长重叠子序列每一种模式(共2m种)的出现次数是否接近。真随机序列中各模式出现次数是近似一样的。重叠子序列检验的参数是二元序列的比特长度n、分组比特长度M和二元序列本身。检验过程中使用了不完全伽马函数。重叠子序列检验中m+2小于log2n向下取整。本文取n=106，m=16。

(12)近似熵检验

近似熵检验是观测二元序列中m比特长重叠子序列每一种模式(共2m种)的出现次数与m+1比特长重叠子序列每一种模式的出现次数之间的关系。近似熵检验的参数是二元序列的比特长度n、分组比特长度M和二元序列本身。检验过程中使用了不完全伽马函数。近似熵检验中m+5小于log2n向下取整。本文取n=106，m=12。

(13)累加和检验

累加和检验首先将二元序列中0映射为-1，1映射为1，然后正序或逆序依次计算累加和，观测整个过程中正序或逆序的累加和最大值(统称为最大偏移)，最后考查累加和最大值是否过大。真随机序列的累加和最大值接近0。累加和检验的参数是二元序列的比特长度n和二元序列本身。检验过程中使用了不完全伽马函数。累加和检验中二元序列比特长度至少为100。

(14)随机游动检验

随机游动检验，首先将二元序列中0映射为-1，1映射为1，然后正序依次计算累加和，在累加和组成的序列中首尾添加0组成新序列，0将新序列分割成数段。约定自由度K=8，即累加和划分为-4(含<-4)、-3、-2、-1、1、2、3、4(含>4)，共8类。最后记录每一段内各个累加和分类的出现次数，并考查其与真随机序列情况是否类似。随机游动检验由K个子检验组成，随机游动检验的参数是二元序列的比特长度n和二元序列本身。检验过程中使用了不完全伽马函数。随机游动检验中二元序列比特长度至少为106。

(15)随机游动状态频数检验

随机游动状态频数检验，首先将二元序列中0映射为-1，1映射为1，然后正序依次计算累加和。约定自由度K=18，即累加和划分为-9(含<-9)、-8、…、-1、1、…、8、9(含>9)，共18类。最后记录各个累加和分类的出现次数，并考查其与真随机序列情况是否类似。随机游动状态频数检验由K个子检验组成，随机游动状态频数检验的参数是二元序列的比特长度n和二元序列本身。检验过程中使用了补余误差函数。随机游动状态频数检验中二元序列比特长度至少为106。

3 NIST统计检测程序的改进

NIST统计检测程序存在的不足和相应改进如下：

(1)检测结果存储于多个文件之中

NIST统计检测程序的检测结果存储于多个文件之中，不方便观察。本文通过增加标识，将数十个日志文件整合至一个日志文件，便于检索。同时增加显示级别控制，根据详细、摘要、报警等不同需求，智能显示内容。

(2)基于传统的命令行方式交互

本文裁剪命令行交互功能，增加读配置文件方式实现参数自动读入功能，从而支持对多套参数进行检测，为支持自动化功能奠定基础。

(3)不支持自动化功能

NIST统计检测程序的检测结果需人工观察日志文件，缺少自动化功能。本文通过递归返回检测结果，自动判断源假设是否成立，实现自动化功能。同时，为支持批量检测功能提供支撑。

(4)不支持批量检测功能

待检测序列由密码算法加载伪随机产生的密钥和初始向量产生，为降低密钥和初始向量的选取对密码算法输出检验判断产生的影响，需要进行多次检测，并给出整体结论，即检测程序需要支持批量检测功能。

下面以AES算法进行频数检验和块内频数检验为例，说明容忍度的意义。

给定容忍度=0.02，显著性水平=0.01。令明文长度为AES的分组长度，即16字节，明文值为全0。使用伪随机方式产生密钥，对明文迭代使用AES算法加密，将每次AES算法加密后的密文组成一个输出序列，输出序列的长度为10 240比特，远大于进行频数检验和块内频数检验的最小长度100比特。然后对此输出序列进行NIST统计检测程序中的频数检验和块内频数检验，分别得到一个频数检验Pvalue值和一个块内频数检验Pvalue值。其中，块内频数检验中块长度取为128比特，满足以下要求：128>20、128>10 240/100和10 240/128<100。使用伪随机方式反复产生65 536次密钥，进行65 536次上述频数检验和块内频数检验。这些检验中共有645次频数检验的Pvalue小于0.01，609次块内频数检验的Pvalue小于0.01。因为645/65 536<0.02，609/65 536<0.02，所以在容忍度=0.02，显著性水平=0.01的前提下，认为AES算法输出的序列是随机的。

(5)非重叠模板匹配检验

考查NIST统计检测程序中非重叠模板匹配检验，当模板长度取9时，模板共有148个。因此非重叠模板匹配检验共有148个子检验。NIST统计检测程序没有将这148个检验结果进一步整合，如果1项子检验不通过就认为整体检验不通过，则整体检验过于严格，ZUC流密码算法[7]、Snow流密码算法[8]、Sosemanuk流密码算法[9]都不能通过这种严格的检验。

本文构造一个统计量如下：

T=

通过148个子检验结果衡量整体非重叠模板匹配检验。其中t1为1项子检验失败次数，t2为2项子检验失败次数，…，t6为6项及6项以上子检验失败次数。此统计量体现了子检验失败次数越多越严重。

下面分别对ZUC流密码算法、Snow流密码算法、Sosemanuk流密码算法和AES分组密码算法进行非重叠模板匹配检验，其中二元序列比特长度为106，模板的比特长度为9，检验次数为1 024，检验结果如表2所示。从表中最后一列值可以看出统计量的设计是合理的。

表2 非重叠模板匹配检验统计量表

(6)其他优化

裁剪NIST统计检测程序中伪随机数生成器功能，增加基于除法电路的线性反馈移位寄存器。相较于NIST统计检测程序中复杂的伪随机数生成器，线性反馈移位寄存器的输出具有易于理论推导的更简单形式和更良好的统计学特性[10]，适合用于本文中密钥和初始向量的随机性构造。

4 结论

本文首先详细介绍NIST统计检测程序，并描述了其存在的不足，然后以AES算法进行多次频数检验和块内频数检验为例，阐述了引入容忍度的意义，最后以ZUC流密码算法、Snow流密码算法、Sosemanuk流密码算法和AES分组密码算法为例，实验证明了本文构造的T统计量是合理的，从而进行非重叠模板匹配检验后，可得出唯一结论。