GM/T 0005《随机性检测规范》2012版和2021版对比

置顶艾米的爸爸

已于 2022-08-26 10:17:13 修改

阅读量6w

点赞数 10

分类专栏：密码技术与应用国密密码文章标签：随机性检测随机数密码

于 2022-08-11 00:24:43 首次发布

本博客的博主原创文章均遵循 CC 4.0 BY-SA 版权协议，所有与之冲突的版权协议均为无效协议。

本文链接：https://blog.csdn.net/samsho2/article/details/126277014

版权

密码同时被 3 个专栏收录

226 篇文章

订阅专栏

密码技术与应用

183 篇文章

订阅专栏

国密

75 篇文章

订阅专栏

1. 背景

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

2. 规范的差异性对比

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

检测项的差异：15个检测项中有3个检测项有少许差异。
检测参数的差异：如样本长度、块内频数检测的参数等。
判定准则的差异：如增加了Q值分布均匀性检测这种二级检测。

2.1 检测项存在的差异

2.1.1 检测线差异的概况

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

表2.1 随机性检测项的差异

此外，离散傅里叶检测的差异主要在于第七步计算统计量时n除以的系数从2012版的4变为新版的3.8。

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

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

新增块内最大0游程检测。此检测的执行流程和块内最大1游程检测一样，仅仅是检测对象从1游程变为0游程。检测详情可参见2021版的5.7节。
πi值的修订。πi值有两处修订：
1. 子序列长度m = 10000（当n >= 750,000时m取此值）时πi的取值差异较大，如下表2.2所示。此处修订的参数值变化较大，且涉及常用的样本长度n=1000×1000和n=1024×1024，因此对随机性检测模块影响较大。这些πi取值的详情也可参见2021版标准附录B.7节的表B.4。
2. 子序列长度m = 128（当750,000 > n >= 6272时m取此值）时πi的取值仅π2有微小差异（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 离散傅里叶检测的差异

离散傅里叶检测的差异主要在于第七步计算统计量时n除以的系数从2012版的4变为新版的3.8，即计算统计值V的公式在2012版中是

在2021版中是

。

该系数一直在不断修订完善，比如在NIST SP800-22（2001年）和NIST SP800-22 rev1（2008年）中该系数为2，在NIST SP800-22 rev1a（2010年）、GM/T 0005-2012、GB/T 32915-2016中该系数为4，到了本次2021版再度修订为3.8。

2.1.6 增加了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。

块内频数检测：参数m从100调整为10000。调整后的m使得子序列可以按字节对齐，更加利于处理。
重叠子序列检测：参数m = 2, 5调整为m = 3, 5。在m=2时，会存在比较尴尬的“0-位”子序列模式及其频数，以及有点小别扭的 $\Psi ^2_{m-2}=0$ ，所以相比而言m = 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，即

$Q-value = P-Value = igamc(*,V/2)$ 。

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

$P-Value = erfc(|V|/\sqrt2)$ ， $Q-Value = erfc(V/\sqrt2)/2$ 。

2.4 其它差异

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

参考文献

密码行业标准化技术委员会. GM/T 0005-2021: 随机性检测规范[S]. 北京: 中国标准出版社, 2022.
密码行业标准化技术委员会. GM/T 0005-2012: 随机性检测规范[S]. 北京: 中国标准出版社, 2012.
Fan, LM, Chen, H ,Chen, MH, et al. Corrected runs distribution test for pseudorandom number generators[J]. ELECTRONICS LETTERS, 2016, 52(4): 281-282.
NIST SP800-22r1a. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. 2010.
庄家,马原,朱双怡,林璟锵,荆继武. Q_Value检测:一种新的随机数统计检测方法[J]. 密码学报, 2016, 3(02): 192-201.