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

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

0背  景

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

0规范的差异性对比

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

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

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

判定准则的差异:如增加了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的取值仅π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版不仅有前向累加和检测,还新增了后向累加和检测。

前向累加和检测:从待检序列的第1比特开始,逐比特向后计算;

后向累加和检测:从待检序列的最后1比特开始,逐比特向前计算。

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

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

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增加了测试向量,这对工程人员而言是个有利的支撑。看来当年征求意见时提出的意见被采纳了。

0随机性检测模块升级建议

3.1 升级建议概述

如前所述,GM/T 0005《随机数检测规范》的2021版和2012版在检测项、检测参数、判定准则等方面都存在或多或少的差异。关于如何升级,本节给出一些建议供参考。

概况起来,随机性检测程序的升级首先应考虑兼容国家标准GB/T 32915—2016《信息安全技术 二元序列随机性检测方法》,其次考虑兼容前述检测项差异、检测参数差异、判断准则差异。

3.2 兼容国家标准GB/T 32915—2016

国家标准GB/T 32915—2016《信息安全技术 二元序列随机性检测方法》是以GM/T 0005—2012为基础升级的国标版本,主要内容和2012版差异非常小,后文在提到GB/T 32915—2016的检测内容时可能会与GM/T 0005—2012的相关内容混在一起。目前,GB/T 32915—2016和GM/T 0005—2021是共存阶段。因此,随机性检测模块优先支持GM/T 0005—2021,但也应尽量考虑适当兼容GB/T 32915—2016标准。

3.3 兼容检测项的差异

针对检测项的差异,可以考虑如下方式进行带兼容性的升级,详情见下表3.1。

表3.1 兼容检测项差异的升级建议

3.4 兼容检测参数差异

针对检测参数的差异,可以考虑如下方式进行带兼容性的升级,详情见下表3.2。

表3.2 兼容检测参数差异的升级建议

此外,所有检测项都可根据实际情况考虑支持2021版附录A中其它检测参数,甚至是任意的有效设定值。

3.5 兼容判断准则差异

针对判断准则的差异,可以考虑如下方式进行带兼容性的升级,详情见下表3.3。

表3.3 兼容判断准则差异的升级建议

参考文献

[1]密码行业标准化技术委员会. GM/T 0005-2021: 随机性检测规范[S]. 北京: 中国标准出版社, 2022.

[2]密码行业标准化技术委员会. GM/T 0005-2012: 随机性检测规范[S]. 北京: 中国标准出版社, 2012.

[3]Fan, LM, Chen, H, Chen, MH, et al. Corrected runs distribution test for pseudorandom number generators[J]. ELECTRONICS LETTERS, 2016, 52(4): 281-282.

[4]NIST SP800-22r1a. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. 2010.

[5]庄家,马原,朱双怡,林璟锵,荆继武. Q_Value检测:一种新的随机数统计检测方法[J]. 密码学报, 2016, 3(02): 192-201.

声明:本文来自密码头条,版权归作者所有。文章内容仅代表作者独立观点,不代表安全内参立场,转载目的在于传递更多信息。如有侵权,请联系 anquanneican@163.com。