对公银行账号/支付宝 中国标准英文版 技术翻译  数据库收录: 159759 更新: 2021-01-06  
现货的,9秒内发货  

GB/T 32915-2016

标准搜索结果: 'GB/T 32915-2016'
标准号码内文价格美元第2步交付天数标准名称状态
GB/T 32915-2016 英文版 150 购买 3分钟内自动发货[PDF],有增值税发票。 信息安全技术 二元序列随机性检测方法 有效

   
基本信息
标准编号 GB/T 32915-2016 (GB/T32915-2016)
中文名称 信息安全技术 二元序列随机性检测方法
英文名称 Information security technology - Randomness test methods for binary sequence
行业 国家标准 (推荐)
中标分类 L80
国际标准分类 35.040
字数估计 23,245
发布日期 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
随机数发生器 randomnumbergenerator
产生随机二元序列的器件或程序。
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 统计值
P_value 余误差函数(ComplementaryErrorFunction)
erfc 一种衡量样本随机性好坏的度量指标。
igamc 不完全伽玛函数(IncompleteGammaFunction)
π 待检序列中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,然后利用Berlekamp-Massey算法计算每个子序列的线
性复杂度Li,根据Li 的分布情况判断待测序列的随机性。
4.13.2 检测步骤
线性复杂度检测步骤如下:
第一步:将待检序列ε划分为N=
个长度为m 的非重叠子序列,将多余的比特舍弃。
第二步:计算每一个子序列的线性复杂度Li 1≤i≤N()。
第三步:计算μ=
2+
9+ -1()m+1
36 -
2m
3+
÷。
第四步:对每一个子序列,计算Ti= -1()m Li-μ()+
第五步:设置7个正整数v0,v1,,v6,将这7个正整数的初值都设为0。对所有的1≤i≤N 有:
Ti≤-2.5,v0 加1;
-2.5-1.5-0.50.51.5Ti>2.5,v6 加1。
第六步:计算统计值V=∑
i=0
vi-Nπi() 2
Nπi
。其中,πi 值为:π0=0.010417,π1=0.03125,π2=
0.12500,π3=0.5000,π4=0.25000,π5=0.06250,π6=0.020833。
第七步:计算P_value=igamc3,
÷。
4.13.3 结果判定
将4.13.2中计算得出的P_value结果与显著性水平α进行比较。如果P_value≥α,则认为待检
序列通过线性复杂度检测。
4.14 Maurer通用统计检测方法
4.14.1 概述
Maurer通用统计检测用于检测待检序列能否被无损压缩。因为随机序列是不能被显著压缩,因此
如果待检序列能被显著地压缩,则认为该序列不随机。
4.14.2 检测步骤
Maurer通用统计检测步骤如下:
第一步:将待检序列ε分成两部分:初始序列和测试序列。初始序列包括Q 个L 位的非重叠的子
序列,测试序列包括K 个L 位的非重叠的子序列,将多余的位(不够组成一个完整的L 位子序列)舍
弃,K=
L -Q
第二步:针对初始序列,创建一个表,它以L 位值作为表中的索引值,Tj(1≤j≤2L)表示表中第
j个元素的值,计算Tj=i(1≤i≤Q),其中j是初始序列中第i个L 位子序列的十进制表示。
第三步:计算sum=∑
Q+K
i=Q+1
log2i-Tj(),其中,遍历完第i(Q+1≤i≤Q+K)个L 位子序列后,应
更新Tj=i。
第四步:计算V=
sum
K -E
(L)
,E L()和σ的计算参见A.14。
第五步:计算P_value=erfc
÷。
4.14.3 结果判定
将4.14.2中计算得出的P_value结果与显著性水平α进行比较。如果P_value≥α,则认为待检
序列通过 Maurer通用统计检测。
4.15 离散傅立叶检测方法
4.15.1 概述
离散傅立叶检测使用频谱的方法来检测序列的随机性。对待检序列进行傅立叶变换后可以得到尖
峰高度,根据随机性的假设,这个尖峰高度不能超过某个门限值(与序列长度n有关),否则将其归入不
正常的范围;如果不正常的尖峰个数超过了允许值,即可认为待检序列是不随机的。
4.15.2 检测步骤
离散傅立叶检测步骤如下:
第一步:将待检序列ε中的0和1分别转换成-1和1,得到新序列X1,X2,,Xn Xi=2εi-1()。
第二步:对新序列进行傅立叶变换,得到一系列的复数f1,f2,,fn。
第三步:对每一个fi,计算其系数modi=modulusfi()= fi,这里i∈ 0,n/2-1[ ]。
第四步:计算门限值T= 2.995732274n。
第五步:计算N0=0.95×
第六步:计算系数fi 小于门限值T 的复数个数,记作N1。
第七步:计算统计值V= N1-N0()/0.95×0.05×
第八步:计算P_value=erfc
÷。
4.15.3 结果判定
将4.15.2中计算得出的P_value结果与显著性水平α进行比较。如果P_value≥α,则认为待检
序列通过离散傅立叶检测。
注:本章规定的检测方法说明性原理参见附录A,检测参数设置参见附录B。
5 随机数发生器检测
5.1 随机数发生器检测概述
对随机数发生器的检测,首先对采集到的二元序列进行随机性检测,在随机性检测的基础上对随机
数发生器进行判断。随机性检测的方法利用第4章规定的15种随机性检测方法。
5.2 采集
本标准宜采集随机数样本数量不少于1000,每个样本长度不低于106 比特。
5.3 检测
对每一个样本按第4章描述的检测方法进行检测,分别得到每一个随机性检测项目的P_value
值,记录这些结果。
5.4 判定
对于每一个随机性检测项目,统计P_value值不小于显著性水平α(表示该样本通过该项检测)的
样本个数。记样本数量为s,则通过检测的样本个数应不小于s1-a-3
a(1-a)
÷。例如,当样本数
量为1000个,显著性水平α为0.01时,如果通过的样本个数不小于981,则随机数发生器通过此项检
测;否则,未通过此项检测。
如果随机数发生器通过本标准规定的所有检测项目,则随机数发生器通过本标准检测;否则,未通
过本标准检测。
对于使用随机数发生器的各种装置或设备,其随机性检测可参照本标准。
附 录 A
(资料性附录)
随机性检测原理
A.1 单比特频数检测
单比特频数检测是最基本的检测,用来检测一个二元序列中0和1的个数是否相近。也就是说,若
已知一个长度为n的二元序列,检测该序列是否具有较好的0、1平衡性。令n0,n1 分别表示该序列中
0和1的数目。对一个随机序列,当其长度充分大时,其统计值V 应该服从标准正态分布:
V=2n
n1
n -
A.2 块内频数检测
块内频数检测用来检测待检序列的m 位子序列中1的个数是否接近m/2。对随机序列来说,其任
意长度的m 位子序列中1的个数都应该接近m/2。
块内频数检测将待检序列划分成N 个子序列,每个子序列的长度为m,有n=N×m。当然,如果
n不能被m 整除,必然会有多余位,此时将多余的位舍弃。计算每一个子序列中1所占的比例,设为
πi=
j=1
ε(i-1)m+j
,1≤i≤N 。将所有N 个子序列中1所占的比例的累加和作为统计值。
V=4m∑
i=1
πi-
该统计量应该服从自由度为N 的χ2 分布 。
A.3 扑克检测
对任意的正整数m,长度为m 的二元序列有2m 种。将待检序列划分成N=
个长度为m 的非
叠加的子序列,用ni 1≤i≤2m()表示第i种子序列类型的个数。扑克检测用来检测这2m 种子序列类
型的个数是否接近。
统计值V=∑
2m
i=1
ni-
2m
2m
2m
N∑
2m
i=1
n2i-N 应该服从自由度为2m-1的χ2 分布。
A.4 重叠子序列检测
对任意的正整数m,长度为m 的二元序列有2m 种。重叠子序列检测将长度为n的待检序列划分
成n个可叠加的m 位子序列。对随机二元序列来说,由于其具有均匀性,故m 位可叠加子序列的每一
种模式出现的概率应该接近。
在重叠子序列检测中,m 位子序列共有2m 种模式,记为i1,i2,,im。令vi1i2im 表示模式为
(i1,i2,,im)的子序列出现的个数。则统计值
Ψ2m = ∑
i1i2im
vi1i2im -
2m
2m
2m
n ∑i1i2im vi1i2im -
2m
2m
n ∑i1i2imv
i1i2im -n
应该服从χ2 类型的分布,但是并不服从χ2 分布,因为各vi1i2im之间并不独立。
令统计值ÑΨ2m 和Ñ2Ψ2m:
ÑΨ2m =Ψ2m -Ψ2m-1
Ñ2Ψ2m =Ψ2m -2Ψ2m-1+Ψ2m-2
其中,Ψ20=Ψ2-1=0。则统计值ÑΨ2m 和Ñ2Ψ2m 应该分别服从自由度为2m-1和2m-2的χ2 分布。
A.5 游程总数检测
游程是二元序列的一个子序列,由连续的0或者1组成,并且其前导和后继元素都与其本身的元素
不同。
游程总数检测主要检测待检序列中游程的总数是否服从随机性要求。
令Vn(obs)表示待检序列的游程总数,π表示该序列中1所占的比例,Φ z()为标准正态分布,则:
V=
Vn(obs)-2nπ1-π()
2nπ1-π()
服从标准正态分布。
A.6 游程分布检测
连续1(或0)的一个游程称为一个块(或一个间断)。如果待检二元序列是随机的,则相同长度游程
的数目接近一致。一个长度为n的随机二元序列中长度为i的游程的数目的期望值为ei=
n-i+3
2i+2
令k为满足ei≥5的最大整数i。令bi,gi 分别表示一个二元序列中长度为i的“1”游程和“0”游程的数
目,对于每一个i,1≤i≤k。统计值V 近似地服从自由度为2k-2的χ2 分布:
V=∑
i=1
bi-ei() 2
ei +∑
i=1
gi-ei() 2
ei
A.7 块内最大“1”游程检测
将待检序列划分成N 个等长的子序列,根据各个子序列中最大1游程的分布来评价待检序列的随
机性。
将待检序列划分成N 个长度为m 的子序列,此时n=N×m。根据m 的大小,对应着K+1个集
合(与m 的大小有关),然后计算每个子序列的最大“1”游程的长度,并将其归入相应的集合。设这K+1
个集合中的元素个数分别为v0,v1,v2,,vk v0+v1+v2++vk=N(),统计值V 应该服从自由度为
K 的χ2 分布:
V=∑
i=0
vi-Nπi() 2
Nπi
K 和πi 的取值与m 有关,表A.1、表A.2和表A.3分别给出了当m 取8、128和10000时对应的
K 值大小、vi 定义以及πi 的取值。
表A.1
m 8 128 10000
K 3 5 6
表A.2
vi m=8 m=128 m=10000
v0 ≤1 ≤4 ≤10
v1 2 5 11
v2 3 6 12
v3 ≥4 7 13
v4 8 14
v5 ≥9 15
v6 ≥16
表A.3
πi m=8 m=128 m=10000
π0 0.2148 0.1174 0.0882
π1 0.3672 0.2430 0.2092
π2 0.2305 0.2493 0.2483
π3 0.1875 0.1752 0.1933
π4 0.1027 0.1208
π5 0.1124 0.0675
π6 0.0727
A.8 二元推导检测
二元推导序列是由初始序列生成的一个新的序列。第一次二元推导序列是一个长度为n-1的二
元序列,它是通过依次将初始序列中两个相邻比特作异或操作所得的结果。长度为n-k的第k次二
元推导序列,是成功执行上述操作k次所得的结果序列。
二元推导检测的目的是判定第k次二元推导序列中0和1的个数是否接近一致。令pk 为第k次
二元推导序列中1的比例。统计值V=2 n-k
pk
n-k-
÷应该服从标准正态分布。
A.9 自相关检测
自相关检测用来检测待检序列与将其左移(逻辑左移)d位后所得新序列的关联程度。一个随机序
列应该和将其左移任意位所得的新序列都是独立的,故其关联程度也应该很低。
令A d()=∑
n-d-1
i=0
εi 􀱇εi+d() 表示待检序列与将其左移d位后所得新序列之间不同元素的个数,称
d为时延。
统计值V=
2[A d()- n-d()/2]
n-d
应该服从标准正态分布。
A.10 矩阵秩检测
矩阵秩检测用来检测待检序列中给定长度的子序列之间的线性独立性。由待检序列构造矩阵,然
后检测矩阵的行或列之间的线性独立性,矩阵秩的偏移程度可以给出关于线性独立性的量的认识,从而
影响对序列随机性好坏的评价。
对于一个M×Q 矩阵来说,其秩(用R 表示)可以取r=0,1,2,,m[m=minM,Q()]之间的数。
对于一个由随机序列构造的M×Q 矩阵来说,R 取r的概率pr 应为:
pr=2r(Q+M-r)-MQ∏
r-1
i=0
(1-2i-Q)(1-2i-M)
1-2i-r
令FM、FM-1和N-FM-FM-1分别表示秩为M、M-1以及秩小于M-1的矩阵个数,选取M=
32,Q=32,则统计值
V=
FM -0.2888N() 2
0.2888N +
FM-1-0.5776N() 2
0.5776N +
N-FM -FM-1-0.1336N() 2
0.1336N
应该服从自由度为2的χ2 分布。其中,0.2888、0.5776和0.1336分别为秩为32、31以及小于31
的矩阵概率,N 为由序列构造的矩阵的总个数。
A.11 累加和检测
累加和检测将待检序列的各个子序列中最大的偏移(与0之间),也就是最大累加和与一个随机序
列应具有的最大偏移相比较,以判断待检序列的最大偏移是过大还是过小。实际上,随机序列的最大偏
移应该接近0,所以累加和不能过大,也不能过小(累加和可以是负数)。根据最大偏移值来判断待检序
列的随机程度。
构造随机变量Xi=2εi-1,设
Si=X1++Xi=2ε1++εi()-i
累加和检测根据 Si 的最大值max1≤i≤n Si 来检测待检序列的随机性。
根据以下方法计算P-value:
P (max
1≤i≤n
Si ≥z) =1-∑
+∞
i= -∞
P 4i-1()z+∞
i= -∞
P 4i+1()zP_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
A.12 近似熵检测
近似熵检测通过比较m 位可重叠子序列模式的频数和m+1位可重叠子序列模式的频数来评价
其随机性。近似熵检测是对两个相邻长度的可重叠子序列模式出现频数的检测,设Yi m()=
εi+1,εi+2,,εi+m-1(),令
Cmi =
n-m+1
#j:1≤j≤n-m+1,Yj(m)=Yi(m){ }=πl
(m)=∑
2m
l=1
πlnπl
式中:
Cmi 表示模式Yi m()在待检序列中出现的相对频数;
πl 表示模式l=i1,i2,,im()在待检序列中出现的相对频数;
(m)表示所有2m 个m 位子序列模式相对频数分布的熵。
定义近似熵ApEn m()为:ApEn m()=φ
(m)-φ
(m+1)。这里,ApEn0()=-φ
(1)。
近似熵给出了当子序列长度m 增加1时,m 位可重叠子序列模式和m+1位可重叠子序列模式之
间的频数之间的差异有多大。因此,小的ApEn m()值说明待检序列具有规则性和连续性;而大的
ApEn m()值则表明待检序列具有不规则性和不连续性。
对任意一个m 来说,可以得到随机序列(不规则序列)的近似熵ApEn m()应该近似地等于ln2。
所以,统计值V=2n[ln2-ApEn(m)]应该服从自由度为2m 的χ2 分布。
A.13 线性复杂度检测
将待检序列划分成 N 个长度为M 的子序列,此时n=N×M,然后利用Berlekamp-Massey
算法计算每个子序列的线性复杂度Li,计算Ti= -1()M Li-μ()+
,其中μ=
2+
9+ -1()M+1
36 -
2M
3+
÷。
选择K+1个不相交的独立的集合,然后将各个子序列的TM 按集合分类,统计各个集合中出现的
TM 个数,分别记作v0,v1,,vK,显然v0+v1++vK=N。
统计值V=∑
i=0
vi-Nπi() 2
Nπi
应该服从自由度为K 的χ2 分布。
本标准选择K=6,设置7个正整数v0,v1,,v6,将这7个正整数的初值都设置为0,对所有的
i∈ 1,N[ ]:
如果:Ti≤-2.5,v0 加1;
-2.5-1.5-0.50.51.5Ti>2.5,v6 加1。
其中,对应的πi 值为:π0=0.010417,π1=0.03125,π2=0.12500,π3=0.5000,π4=0.25000,π5=
0.06250,π6=0.020833。
A.14 Maurer通用统计检测
Maurer通用统计(简称通用统计)检测主要检测待检序列能否被无损压缩。如果待检序列能被显
著地压缩,则认为该序列是不随机的,因为随机序列是不能被显著压缩的。
通用统计检测可以用来检测待检序列多方面的特性,但这并不意味着通用统计检测是前面几个检
测的拼装,而是通用统计检测完全采取了和其他检测所不同的方法。一个序列可以通过通用统计检测
当且仅当这个序列是不可压缩的。通用统计检测的目的是检测待检序列任何统计上的缺陷。
通用统计检测需要的数据量很大,它将序列分成长度为L 的子序列,然后将待检序列分成两部分:
初始序列和检测序列。初始序列包括Q 个子序列,Q 应该大于等于10×2L;检测序列包括K 个子序
列,K 应该大于等于1000×2L。因此,序列长度n应为10×2L+1000×2L,而L 的取值范围应为
1≤L≤16,建议L 取不小于6的值。显然,当L=6时,有n=387840。当序列长度n一定时,宜选择
K=
L -Q
,Q 的取值应该保证L 位子序列的所有2L 个模式都在初始序列中至少出现一次。
首先,从头开始遍历初始序列(以块为单位),找到每一个L 位模式在初始序列中最后出现的位置
(块号),如果一个L 位模式在初始序列中没有出现,那么将其位置设置为0;此后,从头开始遍历检测序
列,每一次都会得到一个L 位子序列,计算这个子序列所在的位置与其前面最后一次出现的位置差,也
就是块号相减,称相减结果为距离,那么再对距离求以2为底的对数;最后,将所有的求对数的结果相
加。这样,就可以得到统计值:
fn=
K∑
Q+K
i=Q+1
log2(距离)
统计值fn 应该渐近服从单边正态分布,本标准采用如下公式来计算该期望值:
μ=E fn()=2-L∑
+∞
......
   
       隐私   ·  优质产品   ·  退款政策   ·  公平交易   ·  关于我们
宁德梧三商贸有限公司 (营业执照期限:2019-2049年. 纳税人识别号:91350900MA32WE2Q2X)
对公账号开户银行:中国建设银行 | 账户名称:宁德梧三商贸有限公司 | 账户号码:35050168730700000955
本公司专职于中国国家标准行业标准英文版