摘要：本文档对GM/T 0005—2012《随机数检测规范》和GM/T 0005—2021《随机数检测规范》进行对比研究，分析评估这些差异对随机性检测程序修订的影响，并给出随机性检测模块升级的建议。

关键词：二元序列，随机性，随机性检测，Q-value，P-value，分布均匀性。

 背景

近期，密码行业标准《随机数检测规范》的2021版^[1]正式发布。整体而言，《随机数检测规范》的2021版和2012版^[2]差异不是非常大，但涉及的内容和分布的范围都比较广。本文梳理两个版本的主要差异以及可能影响随机性检测模块/工具升级的内容，为随机性检测程序的升级做一定的支撑。

2. 规范的差异性对比

《随机数检测规范》的2021版和2012版的差异主要体现在如下几个方面。

l  检测项的差异：15个检测项中有3个检测项有少许差异。

l  检测参数的差异：如样本长度、块内频数检测的参数等。

l  判定准则的差异：如增加了Q值分布均匀性检测这种二级检测。

2.1 检测项存在的差异

2.1.1 检测线差异的概况

检测项还是15个，但其中有3个检测项有一定程度的修订，见下表2.1。

表2.1 随机性检测项的差异

2.1.2 块内最大游程检测的差异

块内最大游程检测共涉及如下修订：

1）新增块内最大0游程检测。此检测的执行流程和块内最大1游程检测一样，仅仅是检测对象从1游程变为0游程。详情可参见2021版的5.7节。

2）πi值的修订。πi值有两处修订：

a)      子序列长度m = 10000（当n >= 750,000时m取此值）时π_i的取值差异较大，如下表2.2所示。此处修订的参数值变化较大，且涉及常用的样本长度n=1000×1000和n=1024×1024，因此对随机性检测模块影响较大。这些π_i取值的详情也可参见2021版标准附录B.7节的表B.4。

b)      子序列长度m = 128（当750,000 > n >= 6272时m取此值）时π_i的取值仅π₂有微小差异（0.2493还是0.2494），如下表2.3所示。此处修订差异小，且不涉及常用样本长度n=1000×1000或n=1024×1024，故对随机性检测模块影响非常小。

表2.2 块内最大游程检测在m=10000时的π_i值差异

表2.3 块内最大游程检测在m=128时的π_i值差异

2.1.3 累加和检测的差异

累加和检测共涉及一处修订：2012版只执行前向累加和检测，而2021版不仅有前向累加和检测，还新增了后向累加和检测。

Ø  前向累加和检测：从待检序列的第１比特开始，逐比特向后计算；

Ø  后向累加和检测：从待检序列的最后１比特开始，逐比特向前计算。

检测的其余计算步骤相同。

2.1.4 游程分布检测的差异

游程分布检测的差异主要在于计算统计量时2021版使用修订的ei值。文[3]说明了游程分布检测存在的不足以及修订方式。个人理解是，在2012版中是按理想序列的游程分布的期望值进行计算，但是实际检测中的待检序列并非理想序列；如果还是按理想序列的游程分布来计算的话，就可能与待检序列的实际情况产生较大的误差。2021版吸纳上述研究成果，按待检序列的实际总数游程来计算的。

游程分布检测的详细对比见下表2.4。

表2.4 游程分布检测的差异

2.1.5 新增Q值的计算

每个检测项都增加了Q值的计算，具体原因请见2.3.3 新增的二级检测与Q值。

2.2 检测参数存在的差异

2.2.1 检测参数差异的概况

检测参数的差异包括：

Ø  整体检测参数的差异：例如样本长度出现了差异。

Ø  检测项目检测参数的差异：例如块内频数检测的参数有了明显变化。

2.2.2 整体检测参数

整体检测参数变化较小，如下表2.5所示。

表2.5 整体检测参数的差异

2.2.3 检测项检测参数的差异

2021版在附录A中给出了三种样本长度（20,000、1,000,000、100,000,000比特）以及对应的检测项参数，本节以最常用的样本长度1,000,000比特进行对比分析，详情见下表2.6。

1)      块内频数检测：参数m从100调整为10000。调整后的m使得子序列可以按字节对齐，更加利于处理。

2)      重叠子序列检测：参数m = 2, 5调整为m = 3, 5。在m=2时，会存在比较尴尬的“0-位”子序列模式及其频数，以及有点小别扭的 =0，所以相比而言m = 3更适合该项检测。

3)      线性复杂度检测：参数m = 500调整为m = 500, 1000。线性复杂度检测是所有检测项中检测速度最慢的那一类，新增的m=1000可能会使得本来就比较慢的随机性检测雪上加霜。

表2.6 检测项检测参数的差异

2.3 判定准则存在的差异

2.3.1 判断准则差异的概况

判断准则主要存在两点差异：

Ø  明确了独立检测项的要求：首次在标准中明确了独立检测项的要求，包括不同检测参数、不同检测方式、多个统计值的检测项。

Ø  新增了二级检测样本分布均匀性：增加了二级检测——基于Q_value而不是P_value的样本分布均匀性。

2.3.2 新增对独立检测项的说明

2021版的6.1节明确规定了具有不同检测参数的同一检测项、不同检测方式的同一检测项、多个统计值的检测项都要作为单独的随机性检测项。按此要求，检测项一共有27项，具体如下表2.7所示。

表2.7 独立检测项清单（以1,000,000比特样本为例）

2021版6.1节的相关规定摘抄如下：“一种随机性检测方法对应至少一个随机性检测项目，其中如某一项随机性检测方法采用不同检测参数设置（详见附录Ａ），或具有不同检测模式（如块内最大游程检测方法、累加和检测方法），或具有多个统计值（如重叠子序列检测方法），应作为单独的随机性检测项目进行检测，并分别对二元序列样本集的每个检测项目的样本通过率、分布均匀性进行合格判定。比如累加和检测方法包括前向累加和、后向累加和两种模式，前向累加和、后向累加和应作为２个独立的检测项目进行检测，并分别对二元序列样本集中前向累加和、后向累加和的样本通过率、分布均匀性进行合格判定。”

2.3.3 新增的二级检测与Q值

在达标判定准则部分，2021版增加了二级检测——样本分布均匀性检测，如下表2.8所示。

表2.8 达标判定准则的差异

样本分布均匀性检测在NIST的随机性检测文档NIST SP800-22^[4]中就曾使用。文[5]分析认为NIST SP800-22的样本分布均匀性检测基于P_value执行，有不足之处，并提出基于Q_value的分布均匀性检测。该方法被吸纳进2021版。

2021版的样本分布均匀性检测方法和NIST SP800-22描述一致，只不过不是对P_value进行统计，而是对Q_value进行统计。因此，2021版在每个具体的检测项中增加Q_value的计算。Q_value具体方法如下。

Ø  开方分布型检测项：如块内频数检测、扑克检测，Q_value和P_value相等，都用统计量V计算igamc，即

。

Ø  正态分布检测型检测项：如单比特检测、游程总数检测，用统计量V的原始值而不是绝对值去计算erfc,，即

。

2.4 其它差异

2021版附录C增加了测试向量，这对工程人员而言是个有利的支撑。看来当年征求意见时提出的意见被采纳了。