标准搜索结果: 'GM/T 0005-2021'
| 标准编号 | GM/T 0005-2021 (GM/T0005-2021) | | 中文名称 | 随机性检测规范 | | 英文名称 | Randomness test specification | | 行业 | Chinese Industry Standard (推荐) | | 中标分类 | L80 | | 国际标准分类 | 35.040 | | 字数估计 | 30,391 | | 发布日期 | 2021-10-18 | | 实施日期 | 2022-05-01 | GM/T 0005-2021
Randomness test specification
ICS 35.030
CCSL80
中华人民共和国密码行业标准
代替GM/T 0005-2012
随 机 性 检 测 规 范
2021-10-18发布
2022-05-01实施
国家密码管理局 发 布
目次
前言 Ⅰ
1 范围 1
2 规范性引用文件 1
3 术语和定义 1
4 符号 2
5 随机性检测方法 3
5.1 单比特频数检测方法 3
5.2 块内频数检测方法 3
5.3 扑克检测方法 4
5.4 重叠子序列检测方法 4
5.5 游程总数检测方法 5
5.6 游程分布检测方法 6
5.7 块内最大游程检测方法 6
5.8 二元推导检测方法 7
5.9 自相关检测方法 8
5.10 矩阵秩检测方法 8
5.11 累加和检测方法 9
5.12 近似熵检测方法 9
5.13 线性复杂度检测方法 10
5.14 Maurer通用统计检测方法 11
5.15 离散傅立叶检测方法 12
6 随机性检测判定 12
6.1 概述 12
6.2 样本通过率判定 13
6.3 样本分布均匀性判定 13
6.4 随机性检测结果判定 13
附录A(规范性) 样本长度及检测设置 14
附录B(资料性) 随机性检测原理 16
附录C(资料性) 随机性检测结果示例 23
随 机 性 检 测 规 范
1 范围
本文件规定了适用于二元序列的随机性检测指标和检测方法。
2 规范性引用文件
本文件没有规范性引用文件。
3 术语和定义
下列术语和定义适用于本文件。
3.1
二元序列 binarysequence
由“0”和“1”组成的比特串。
注:如无特别说明,本文件所指的序列均为二元序列。
3.2
随机性假设 randomnesshypothesis
对二元序列做随机性检测时,首先假设该序列是随机的,这个假设称为原假设或零假设,记为H0。
与原假设相反的假设,即这个序列是不随机的,称为备择假设,记为Hα。
3.3
随机性检测 randomnesstest
用于二元序列检测的一个函数或过程,可以通过它来判断是否接受随机性原假设。
3.4
显著性水平 significancelevel
随机性检测中错误地判断随机序列为非随机序列的概率。
3.5
样本 sample
用于随机性检测的二元序列。
3.6
样本集 samplegroup
多个样本的集合。
3.7
样本长度 samplelength
样本的比特个数。
3.8
样本数量 samplesize
样本集中的样本个数。
∇2Ψ2m:重叠子序列检测中的第二个统计值。
5 随机性检测方法
5.1 单比特频数检测方法
5.1.1 概述
单比特频数检测是最基本的检测,用来检测一个二元序列中0和1的个数是否相近。随机序列应
具有较好的0、1平衡性。
5.1.2 检测步骤
单比特频数检测步骤如下。
第一步:该检测将待检序列ε中的0和1分别转换成-1和1,Xi=2εi-1(1≤i≤n)。
第二步:累加求和计算得到Sn=∑
i=1
Xi。
第三步:计算统计值V=
Sn
第四步:计算P_value=erfc
2 。
第五步:计算Q_value=
2erfc
2 。
检测设置按附录A要求,检测原理见附录B的B.1。
5.1.3 结果判定
将5.1.2中计算得出的P_value结果与α进行比较,如果P_value≥α,则认为待检序列通过单比
特频数检测,否则未通过单比特频数检测。
5.2 块内频数检测方法
5.2.1 概述
块内频数检测用来检测待检序列的m 位子序列中1的个数是否接近
。对随机序列来说,其任意
长度的m 位子序列中1的个数都应该接近
5.2.2 检测步骤
块内频数检测步骤如下。
第一步:将待检序列ε分成N=
个长度为m 的非重叠子序列,将多余的比特舍弃。
第二步:计算每个子序列中1所占的比例πi=
j=1
ε(i-1)m+j
,1≤i≤N。
第三步:计算统计量V=4m∑
i=1
πi-
第四步:计算P_value=igamc
,V
2 。
第五步:计算Q_value=P_value。
检测设置按附录A要求,检测原理见B.2。
5.2.3 结果判定
将5.2.2中计算得出的P_value结果与α进行比较,如果P_value≥α,则认为待检序列通过块内
频数检测,否则未通过块内频数检测。
5.3 扑克检测方法
5.3.1 概述
扑克检测用来检测长度为m 的2m类子序列的个数是否接近。对于随机的序列,2m类子序列的个
数应该接近。
5.3.2 检测步骤
扑克检测步骤如下。
第一步:将待检序列ε划分成N=
个长度为m 的非重叠子序列,将多余的比特舍弃。统计第i
类子序列模式出现的频数,用ni(1≤i≤2m)表示。
第二步:计算统计值V=
2m
N∑
2m
i=1
n2i-N。
第三步:计算P_value=igamc
2m-1
,V
2 。
第四步:计算Q_value=P_value。
检测设置按附录A要求,检测原理见B.3。
5.3.3 结果判定
将5.3.2中计算得出的P_value结果与α进行比较,如果P_value≥α,则认为待检序列通过扑克
检测,否则未通过扑克检测。
5.4 重叠子序列检测方法
5.4.1 概述
对任意的正整数m,长度为m 的二元序列有2m类。重叠子序列检测将长度为n的待检序列划分
成n个可叠加的m 位子序列。对随机二元序列来说,由于其具有均匀性,故m 位可叠加子序列的每一
类模式出现的概率应该接近。
5.4.2 检测步骤
重叠子序列检测步骤如下。
第一步:由待检序列ε构造一个新的序列ε',构造方法如下:将序列ε最开始的m-1位数据添加到
序列ε的结尾即可得到新序列ε',新序列ε'的长度为n'=n+m-1。
第二步:计算ε'中每一类m 位子序列模式(共有2m类)出现的频数,记m 位子序列模式i1i2im的
-1.5< Ti≤-0.5,v2加1;
-0.5< Ti≤0.5,v3加1;
0.5< Ti≤1.5,v4加1;
1.5< Ti≤2.5,v5加1;
Ti >2.5,v6加1。
第六步:计算统计值V=∑
i=0
(vi-Nπi)2
Nπi
。其中,πi值为:
π0=0.010417,π1=0.031250,π2=0.125,π3=0.500,π4=0.250,π5=0.062500,π6=0.020833。
第七步:计算P_value=igamc3,
2 。
第八步:计算Q_value=P_value。
检测设置按附录A要求,检测原理见B.13。
5.13.3 结果判定
将5.13.2中计算得出的P_value结果与α进行比较。如果P_value≥α,则认为待检序列通过线
性复杂度检测,否则未通过线性复杂度检测。
5.14 Maurer通用统计检测方法
5.14.1 概述
Maurer通用统计检测用于检测待检序列能否被无损压缩。因为随机序列是不能被显著压缩,因此
如果待检序列能被显著地压缩,则认为该序列不随机。
5.14.2 检测步骤
Maurer通用统计检测步骤如下:
第一步:将待检序列ε分成两部分:初始序列和测试序列。初始序列包括Q 个L 位的非重叠的子
序列,测试序列包括K 个L 位的非重叠的子序列,K=
L -Q
,末尾不够组成一个完整L 位子序列的
多余位舍弃不用。
第二步:针对初始序列,创建一个表,它以L 位值作为表中的索引值,Tj(0≤j< 2L)表示表中第j
个元素的值,计算Tj=i(1≤i≤Q),其中j是初始序列中第i个L 位子序列的十进制表示。
第三步:计算sum=∑
Q+K
i=Q+1
log2(i-Tj),其中,j是待检序列中第i个L 位子序列的十进制表示,Tj
表示当前表中第j个元素的值,在遍历第i个(Q+1≤i≤Q+K)L 位子序列后,应更新Tj=i。
第四步:计算V=
sum
K -E
(L)
,E(L)和σ的计算见B.14。
第五步:计算P_value=erfc
2 。
第六步:计算Q_value=
2erfc
2 。
检测设置按附录A要求,检测原理见B.14。
5.14.3 结果判定
将5.14.2中计算得出的P_value结果与α进行比较。如果P_value≥α,则认为待检序列通过
Maurer通用统计检测,否则未通过 Maurer通用统计检测。
5.15 离散傅立叶检测方法
5.15.1 概述
离散傅立叶检测使用频谱的方法来检测序列的随机性。对待检序列进行傅立叶变换后可以得到尖
峰高度,根据随机性的假设,这个尖峰高度不能超过某个门限值(与序列长度n有关),否则将其归入不
正常的范围;如果不正常的尖峰个数超过了允许值,即可认为待检序列是不随机的。
5.15.2 检测步骤
离散傅立叶检测步骤如下:
第一步:将待检序列ε中的0和1分别转换成-1和1,得到新序列X1,X2,,Xn,其中Xi=
2εi-1。
第二步:对新序列进行傅立叶变换,得到一系列的复数f0,f1,,fn-1。
第三步:对每一个fj,计算其系数modj=modulus(fj)= fj,这里j∈ 0,n/2-1 。
第四步:计算门限值T= 2.995732274*n。
第五步:计算N0=0.95*
第六步:计算系数modj小于门限值T 的复数个数,记作N1。
第七步:计算统计值V=
N1-N0
0.95*0.05*
3.8
第八步:计算P_value=erfc
2 。
第九步:计算Q_value=
2erfc
2 。
检测设置按附录A要求,检测原理见B.15。
5.15.3 结果判定
将5.15.2中计算得出的P_value结果与α进行比较。如果P_value≥α,则认为待检序列通过离
散傅立叶检测,否则未通过离散傅立叶检测。
6 随机性检测判定
6.1 概述
应采用第5章规定的15种随机性检测方法和附录A规定的检测设置对二元序列样本集进行随机
性检测。一种随机性检测方法对应至少一个随机性检测项目,其中如某一项随机性检测方法采用不同
检测参数设置(详见附录A),或具有不同检测模式(如块内最大游程检测方法、累加和检测方法),或具
有多个统计值(如重叠子序列检测方法),应作为单独的随机性检测项目进行检测,并分别对二元序列样
本集的每个检测项目的样本通过率、分布均匀性进行合格判定。比如累加和检测方法包括前向累加和、
后向累加和两种模式,前向累加和、后向累加和应作为2个独立的检测项目进行检测,并分别对二元序
列样本集中前向累加和、后向累加和的样本通过率、分布均匀性进行合格判定。
本文件确定二元序列样本集中的样本数量为1000。
6.2 样本通过率判定
对于每一个随机性检测项目,统计二元序列样本集中P_value值大于或等于α的样本个数,本文
件确定的用于样本通过率检测的显著性水平α=0.01。
记样本数量为s,当通过某检测项目的样本个数大于或等于s1-α-3
α(1-α)
s 时,认为该样本
集通过该项检测,否则未通过此项检测。例如,样本数量为1000个,则通过该检测项目的样本个数应
大于或等于981。
6.3 样......
|