标准搜索结果: 'GB/T 32915-2016'
| 标准编号 | GB/T 32915-2016 (GB/T32915-2016) | | 中文名称 | 信息安全技术 二元序列随机性检测方法 | | 英文名称 | Information security technology -- Randomness test methods for binary sequence | | 行业 | 国家标准 (推荐) | | 中标分类 | L80 | | 国际标准分类 | 35.040 | | 字数估计 | 23,217 | | 发布日期 | 2016-08-29 | | 实施日期 | 2017-03-01 | | 起草单位 | 国家密码管理局商用密码检测中心、中国科学院软件研究所、北京信息科学技术研究院 | | 归口单位 | 全国信息安全标准化技术委员会(SAC/TC 260) | | 标准依据 | 国家标准公告2016年第14号 | | 提出机构 | 国家密码管理局 | | 发布机构 | 中华人民共和国国家质量监督检验检疫总局、中国国家标准化管理委员会 | GB/T 32915-2016
Information security technology - Randomness test methods for binary sequence
ICS 35.040
L80
中华人民共和国国家标准
信息安全技术
二元序列随机性检测方法
2016-08-29发布
2017-03-01实施
中华人民共和国国家质量监督检验检疫总局
中国国家标准化管理委员会发布
目次
前言 Ⅲ
1 范围 1
2 术语和定义 1
3 符号 2
4 随机性检测 3
4.1 单比特频数检测方法 3
4.1.1 概述 3
4.1.2 检测步骤 3
4.1.3 结果判定 3
4.2 块内频数检测方法 3
4.2.1 概述 3
4.2.2 检测步骤 3
4.2.3 结果判定 3
4.3 扑克检测方法 4
4.3.1 概述 4
4.3.2 检测步骤 4
4.3.3 结果判定 4
4.4 重叠子序列检测方法 4
4.4.1 概述 4
4.4.2 检测步骤 4
4.4.3 结果判定 5
4.5 游程总数检测方法 5
4.5.1 概述 5
4.5.2 检测步骤 5
4.5.3 结果判定 5
4.6 游程分布检测方法 5
4.6.1 概述 5
4.6.2 检测步骤 5
4.6.3 结果判定 6
4.7 块内最大“1”游程检测方法 6
4.7.1 概述 6
4.7.2 检测步骤 6
4.7.3 结果判定 6
4.8 二元推导检测方法 6
4.8.1 概述 6
4.8.2 检测步骤 6
4.8.3 结果判定 7
4.9 自相关检测方法 7
4.9.1 概述 7
4.9.2 检测步骤 7
4.9.3 结果判定 7
4.10 矩阵秩检测方法 7
4.10.1 概述 7
4.10.2 检测步骤 7
4.10.3 结果判定 8
4.11 累加和检测方法 8
4.11.1 概述 8
4.11.2 检测步骤 8
4.11.3 结果判定 8
4.12 近似熵检测方法 8
4.12.1 概述 8
4.12.2 检测步骤 8
4.12.3 结果判定 9
4.13 线性复杂度检测方法 9
4.13.1 概述 9
4.13.2 检测步骤 9
4.13.3 结果判定 10
4.14 Maurer通用统计检测方法 10
4.14.1 概述 10
4.14.2 检测步骤 10
4.14.3 结果判定 10
4.15 离散傅立叶检测方法 10
4.15.1 概述 10
4.15.2 检测步骤 10
4.15.3 结果判定 11
5 随机数发生器检测 11
5.1 随机数发生器检测概述 11
5.2 采集 11
5.3 检测 11
5.4 判定 11
附录A(资料性附录) 随机性检测原理 12
附录B(资料性附录) 随机性检测参数设置表 19
前言
本标准按照GB/T 1.1-2009给出的规则起草。
请注意本文件的某些内容可能涉及专利。本文件的发布机构不承担识别这些专利的责任。
本标准由国家密码管理局提出。
本标准由全国信息安全标准化技术委员会(SAC/TC260)归口。
本标准起草单位:国家密码管理局商用密码检测中心、中国科学院软件研究所、北京信息科学技术
研究院。
本标准主要起草人:李大为、冯登国、陈华、张超、周永彬、董芳、范丽敏、许囡囡、邓开勇、罗鹏。
信息安全技术
二元序列随机性检测方法
1 范围
本标准规定了商用密码应用中的随机性检测指标和检测方法。
本标准适用于对随机数发生器产生的二元序列的随机性检测。
2 术语和定义
下列术语和定义适用于本文件。
2.1
二元序列 binarysequence
由“0”和“1”组成的比特串。
2.2
产生随机二元序列的器件或程序。
2.3
随机性假设 randomnesshypothesis
对二元序列做随机性检测时,首先假设该序列是随机的,这个假设称为原假设或零假设,记为H0。
与原假设相反的假设,即这个序列是不随机的,称为备择假设,记为Hα。
2.4
随机性检测 randomnesstest
用于二元序列检测的一个函数或过程,可以通过它来判断是否接受随机性原假设。
2.5
显著性水平 significancelevel
随机性检测中错误地判断某一个随机序列为非随机序列的概率,用α来表示。
2.6
样本 sample
用于随机性检测的二元序列,称为样本。
2.7
样本长度 samplelength
一个样本的比特个数。
2.8
样本数量 samplesize
随机性检测的样本的个数。
2.9
检测参数 testparameter
随机性检测需要设定的参数。
2.10
游程 run
序列中由连续的“0”或者“1”组成的自序列,并且该子序列的前导与后继元素都与其本身的元素
不同。
3 符号
下列符号适用于本文件。
α 显著性水平
H0 原假设(零假设)
Hα 备择假设
ε 待检序列
n 待检序列的比特长度
εi 待检序列中的某一个比特,εi=(0,1)
ε' 在ε的基础上按照一定的规则产生出的新序列
Xi 2εi-1
m 子序列的比特长度
∑ 求和符号
* 乘法,有时省略
ln(x) x的自然对数
log2(x) 以2为底的x的对数
x 不大于x的最大整数
max 从若干个元素中取最大值
Φ(x) 标准正态分布函数
V 统计值
erfc 一种衡量样本随机性好坏的度量指标。
π 待检序列中1的比例
Vn(obs) 待检序列中游程的总数
ApEn(m) 待检序列的近似熵
K 通用统计检测中待检序列L 位子序列个数
L 通用统计中子序列长度
Li 线性复杂度检测中子序列的线性复杂度
M 矩阵秩检测中矩阵的行数
N 一个n比特序列中m 位子序列的个数
Q 矩阵秩检测中矩阵的列数,或者是通用统计检测中初始序列L位子序列的个数
d 自相关检测中的时延
modulus(x) 用来计算复系数x的模值的运算
ÑΨ2m 重叠子序列检测中的第一个统计值
Ñ2Ψ2m 重叠子序列检测中的第二个统计值
4 随机性检测
4.1 单比特频数检测方法
4.1.1 概述
单比特频数检测是最基本的检测,用来检测一个二元序列中0和1的个数是否相近。也就是说,若
已知一个长度为n的二元序列,检测该序列是否具有较好的0、1平衡性。
4.1.2 检测步骤
单比特频数检测步骤如下:
第一步:该检测将待检序列ε中的0和1分别转换成-1和1,Xi=2εi-1(1≤i≤n)。
第二步:累加求和计算得到Sn=∑
i=1
Xi。
第三步:计算统计值V=
|Sn|
第四步:计算P_value=erfc
÷ 。
4.1.3 结果判定
将4.1.2中计算得出的P_value结果与显著性水平α进行比较,如果P_value≥α,则认为待检序
列通过单比特频数检测;否则认为该待检序列未通过单比特频数检测。
4.2 块内频数检测方法
4.2.1 概述
块内频数检测用来检测待检序列的m 位子序列中1的个数是否接近
。对随机序列来说,其任意
长度的m 位子序列中1的个数都应该接近
4.2.2 检测步骤
块内频数检测步骤如下:
第一步:将待检序列ε分成N=
个长度为m 的非重叠子序列,将多余的比特舍弃。
第二步:计算每个子序列中1所占的比例πi=
j=1
ε(i-1)m+j
,1≤i≤N 。
第三步:计算统计量V=4m∑
i=1
πi-
第四步:计算P_value=igamc
,V
÷。
4.2.3 结果判定
将4.2.2中计算得出的P_value结果与显著性水平α进行比较,如果P_value≥α,则认为待检序
列通过块内频数检测;否则认为该待检序列未通过块内频数检测。
4.3 扑克检测方法
4.3.1 概述
扑克检测用来检测长度为m 的2m 种子序列类型的个数是否接近,对于随机的序列,2m 种子序列
的个数应该接近。
4.3.2 检测步骤
扑克检测步骤如下:
第一步:将待检序列ε划分成N=
个长度为m 的非重叠子序列,将多余的比特舍弃。统计第i
种子序列模式出现的频数,用ni 1≤i≤2m()表示。
第二步:计算统计值V=
2m
N∑
2m
i=1
n2i-N 。
第三步:计算P_value=igamc
2m-1
,V
÷。
4.3.3 结果判定
将4.3.2中计算得出的P_value结果与显著性水平α进行比较,如果P_value≥α,则认为待检序
列通过扑克检测;否则认为该待检序列未通过扑克检测。
4.4 重叠子序列检测方法
4.4.1 概述
对任意的正整数m,长度为m 的二元序列有2m 种。重叠子序列检测将长度为n的待检序列划分
成n个可叠加的m 位子序列。对随机二元序列来说,由于其具有均匀性,故m 位可叠加子序列的每一
种模式出现的概率应该接近。
4.4.2 检测步骤
重叠子序列检测步骤如下:
第一步:由待检序列ε构造一个新的序列ε',构造方法如下:将序列ε最开始的m-1位数据添加到
序列ε的结尾即可得到新序列ε',新序列ε'的长度为n'=n+m-1。
第二步:计算ε'中每一种m 位子序列模式(共有2m 个)出现的频数,记m 位子序列模式i1i2im
的出现频数为vi1i2im。计算每一种m-1位子序列模式(共有2m-1个)出现的频数,记m-1位子序列
模式i1i2im-1的出现频数为vi1i2im-1。计算每一个m-2位子序列模式(共有2
m-2个)出现的频数,
记m-2位子序列模式i1i2im-2的出现频数为vi1i2im-2。
第三步:计算
Ψ2m =
2m
n ∑i1i2imv
i1i2im -n
Ψ2m-1=
2m-1
n ∑i1i2im-1v
i1i2im-1-n
Ψ2m-2=
2m-2
n ∑i1i2im-2v
i1i2im-2-n
第四步:计算
ÑΨ2m =Ψ2m -Ψ2m-1
Ñ2Ψ2m =Ψ2m -2Ψ2m-1+Ψ2m-2
第五步:计算P_value1=igamc2m-2,
ÑΨ2m
÷,P_value2=igamc2m-3,
Ñ2Ψ2m
÷。
4.4.3 结果判定
将4.4.2中计算得出的两个P _value结果与显著性水平α 进行比较。如果P _value1≥α 且
P_value2≥α,则认为待检序列通过重叠子序列检测。
4.5 游程总数检测方法
4.5.1 概述
游程是指序列中由连续的“0”或者“1”组成的子序列,并且该子序列的前导与后继元素都与其本身
的元素不同。游程总数检测主要检测待检序列中游程的总数是否服从随机性要求。
4.5.2 检测步骤
游程总数检测步骤如下:
第一步:对长度为n 的待检序列ε1ε2εn,计算Vnobs()=∑
n-1
i=1
ri()+1。其中,当εi=εi+1时,
ri()=0;否则,ri()=1。
第二步:计算序列中1的比例π=
i=1
εi
第三步:计算P_value=erfc
Vn(obs)-2nπ1-π()
2 2nπ1-π()
ú。
4.5.3 结果判定
将4.5.2中计算得出的P_value结果与显著性水平α进行比较。如果P_value≥α,则认为待检序
列通过游程总数检测。
4.6 游程分布检测方法
4.6.1 概述
游程分布检测用于检测序列中相同长度游程分布是否均匀,随机的序列中,相同长度的游程数目应
该接近一致。
4.6.2 检测步骤
游程分布检测步骤如下:
第一步:计算ei=
n-i+3
2i+2
,1≤i≤n,并求出满足ei≥5的最大整数k。
第二步:统计待检序列ε中每一个游程的长度。变量bi、gi 分别记录一个二元序列中长度为i的
1游程和0游程的数目。
第三步:计算V=∑
i=1
bi-ei() 2
ei +∑
i=1
gi-ei() 2
ei
第四步:计算P_value=igamck-1,
÷。
4.6.3 结果判定
将4.6.2中计算得出的P_value结果与显著性水平α进行比较。如果P_value≥α,则认为待检序
列通过游程分布检测。
4.7 块内最大“1”游程检测方法
4.7.1 概述
块内最大“1”游程检测将待检序列划分成N 个长度为m 的子序列,此时n=N×m。统计各个子
序列中的最长“1”游程长度,通过并将其归入相应的集合,根据各个子序列中最大1游程的分布来评价
待检序列的随机性。
4.7.2 检测步骤
块内最大“1”游程的检测步骤如下:
第一步:将待检序列ε划分成N=
个长度为m 的非重叠子序列,舍弃多余的位不用。
第二步:计算每一个子序列中最大1游程的长度,并将其归入相应的集合{v0,v1,,v6}。
第三步:计算统计值V=∑
i=0
vi-Nπi() 2
Nπi
。其中,vi 和πi 的定义参见A.7。
第四步:计算P_value=igamc3,
÷。
4.7.3 结果判定
将4.7.2中计算得出的P_value结果与显著性水平α进行比较。如果P_value≥α,则认为待检序
列通过块内最大“1”游程检测。
4.8 二元推导检测方法
4.8.1 概述
二元推导检测的目的是判定第k次二元推导序列中0和1的个数是否接近一致。一次二元推导序
列是一个长度为n-1的二元序列,它是通过依次将初始序列中两个相邻比特作异或操作所得的结果。
长度为n-k的第k次二元推导序列,是成功执行上述操作k次所得的结果序列。二元推导检测用于
检测k次推导后0,1的个数是否接近一致,对于一个随机的序列,无论多少次推导之后其0,1的个数都
应该接近一致。
4.8.2 检测步骤
二元推导检测步骤如下:
第一步:对待检序列ε,依次将初始序列中相邻两个比特作异或操作得到新序列ε',即ε'i=εi
εi+1。
第二步:重复第一步:操作k次。
第三步:将新序列ε'中的0和1分别转换成-1和1,然后对其累加求和得Sn-k=∑
n-k
i=1
(2ε'i-1)。
第四步:计算统计值V=
Sn-k
n-k
第五步:计算P_value=erfc(
)。
4.8.3 结果判定
将4.8.2中计算得出的P_value结果与显著性水平α进行比较。如果P_value≥α,则认为待检序
列通过二元推导检测。
4.9 自相关检测方法
4.9.1 概述
自相关检测用来检测待检序列与将其左移(逻辑左移)d位后所得新序列的关联程度。一个随机序
列应该和将其左移任意位所得的新序列都是独立的,故其关联程度也应该很低,即得到的新序列中0,1
的个数应该接近一致。
4.9.2 检测步骤
自相关检测步骤如下:
第一步:计算A d()=∑
n-d-1
i=0
εi εi+d() 。
第二步:计算统计值V=
2A d()- n-d()/2[ ]{ }
n-d
第三步:计算P_value=erfc
÷。
4.9.3 结果判定
将4.9.2中计算得出的P_value结果与显著性水平α进行比较。如果P_value≥α,则认为待检序
列通过自相关检测。
4.10 矩阵秩检测方法
4.10.1 概述
矩阵秩检测用来检测待检序列中给定长度的子序列之间的线性独立性。由待检序列构造矩阵,然
后检测矩阵的行或列之间的线性独立性,矩阵秩的偏移程度可以给出关于线性独立性的量的认识,从而
影响对二元序列随机性好坏的评价。
4.10.2 检测步骤
矩阵秩检测步骤如下:
第一步:将待检序列ε分成大小为32×32的子序列,共有N=
32×32
个,舍弃多余的位不用。将
每一个32×32的子序列组装成一个32×32的矩阵,此矩阵有32行32列,每一行则由序列ε中连续的
32位填充。
第二步:计算每一个矩阵的秩Rii=1,2,,N()。
第三步:令FM 为秩为32的矩阵的个数,令FM-1为秩为31的矩阵的个数,则N-FM-FM-1为秩
小于31的矩阵的个数。
第四步:计算统计值
V=
FM-0.2888N()2
0.2888N +
FM-1-0.5776N()2
0.5776N +
N-FM-FM-1-0.1336N()2
0.1336N
第五步:计算P_value=igamc1,
÷。
4.10.3 结果判定
将4.10.2中计算得出的P_value结果与显著性水平α进行比较。如果P_value≥α,则认为待检
序列通过矩阵秩检测。
4.11 累加和检测方法
4.11.1 概述
累加和检测通过判断待检序列的各个子序列中最大的偏移(与0之间),也就是最大累加和与一个
随机序列应具有的最大偏移相比较,以判断待检序列的随机性。
4.11.2 检测步骤
累加和检测步骤如下:
第一步:将待检序列ε中的0和1分别转换为-1和1,Xi=2εi-11≤i≤n()。
第二步:计算Si=Si-1+Xi,其中S1=X1,1≤i≤n()。
第三步:计算Z=max1≤i≤n Si 。
第四步:计算
P_value=1- ∑
[(n/z)-1]/4
i=[-(n/z)+1]/4
4i+1()z
÷-Φ
4i-1()z
+ ∑
[(n/z)-1]/4
i=[-(n/z)-3]/4
4i+3()z
÷-Φ
4i+1()z
ú 。
4.11.3 结果判定
将4.11.2中计算得出的P_value结果与显著性水平α进行比较。如果P_value≥α,则认为待检
序列通过累加和检测。
4.12 近似熵检测方法
4.12.1 概述
近似熵检测通过比较m 位可重叠子序列模式的频数和m+1位可重叠子序列模式的频数来评价
其随机性。近似熵检测是对两个相邻长度的可重叠子序列模式出现频数的检测。近似熵给出了当子序
列长度m 增加1时,m 位可重叠子序列模式和m+1位可重叠子序列模式之间的频数之间的差异有多
大。因此,小的差异值说明待检序列具有规则性和连续性;而大的差异值则表明待检序列具有不规则性
和不连续性。对任意一个m 来说,随机序列的近似熵应该近似等于ln2。
4.12.2 检测步骤
近似熵检测步骤如下:
第一步:由待检序列ε构造一个新的序列ε',构造方法如下:将序列ε最开始的m-1位数据添加到
序列ε的结尾即可得到ε',新序列ε'的长度为n'=n+m-1。
第二步:计算ε'中所有的2m 个m 位子序列模式的出现频数,记m 位模式i1i2im 出现的频数
为vi1i2im。
第三步:对于所有的j0≤j≤2m-1(),计算Cmj=
vi1i2im
第四步:计算φ m
() =∑
2m-1
i=0
CmilnCmi 。
第五步:用m+1代替m,重复操作第一步至第四步,计算得到φ m+1
() 。
第六步:计算ApEn m()=φ
(m)-φ
(m+1),计算统计值V=2n[ln2-ApEn(m)]。
第七步:计算P_value=igamc2m-1,
÷。
4.12.3 结果判定
将4.12.2中计算得出的P_value结果与显著性水平α进行比较。如果P_value≥α,则认为待检
序列通过近似熵检测。
4.13 线性复杂度检测方法
4.13.1 概述
线性复杂度检测用于检测各等长子序列的线性复杂度分布是否符合随机性的要求。将待检序列划
分成N 个长度为M 的子序列,此时n=N×M,然后利用Berle......
|