GB/T32915-2016
信息安全技术二元序列随机性检测方法
Informationsecuritytechnology—Randomnesstestmethodsforbinarysequence
- 中国标准分类号（CCS）L80
- 国际标准分类号（ICS）35.040
- 实施日期2017-03-01
- 文件格式PDF
- 文本页数23页
- 文件大小466.06KB
以图片形式预览信息安全技术二元序列随机性检测方法
信息安全技术二元序列随机性检测方法
国家标准 GB/T32915一2016 信息安全技术 二元序列随机性检测方法 Informationseeuritytechnoogy一Randomnesstestmethodsforbmarysequenee 2016-08-29发布 2017-03-01实施 国家质量监督检验检疫总局 发布 国家标准化管理委员会国家标准
GB/T32915一2016 4.9自相关检测方法 4.9.1概述 4.9.2检测步骤 4.9.3结果判定 4.10矩阵秩检测方法 4.10.1概述 4.10.2检测步骤 4.10.3结果判定 4.11累加和检测方法 4.11.1概述 4.11.2检测步骤 结果判定 4.1l.3 4.12近似嫡检测方法 4.12.1概述 4.12.2检测步骤 4.12.3结果判定 4.13线性复杂度检测方法 4.13.1概述 4.13.2检测步骤 4.13.3结果判定 4.14Maurer通用统计检测方法 4.l4.概述 4.14.2检测步骤 4.14.3结果判定 4.15离散傅立叶检测方法 4.15,1概述 4.15.2检测步骤 4.15.3结果判定 随机数发生器检测 5.1随机数发生器检测概述 5.2采集 5.3检测 5.4判定 附录A资料性附录随机性检测原理 l2 附录B(资料性附录随机性检测参数设置表 19
GB/T32915一2016 前 言 本标准按照GB/T1.1一2009给出的规则起草
请注意本文件的某些内容可能涉及专利
本文件的发布机构不承担识别这些专利的责任 本标准由国家密码管理局提出
本标准由全国信息安全标准化技术委员会(SAC/Tc260)归口
本标准起草单位国家密码管理局商用密码检测中心、科学院软件研究所、北京信息科学技术 研究院
本标准主要起草人:李大为、冯登国、陈华、张超、周永彬、董芳、范丽敏、许囱闵囱、邓开勇、罗鹏
m
GB/T32915一2016 信息安全技术 二元序列随机性检测方法 范围 本标准规定了商用密码应用中的随机性检测指标和检测方法
本标准适用于对随机数发生器产生的二元序列的随机性检测
术语和定义 下列术语和定义适用于本文件
2.1 二元序列binaryseguence 由“o”和“1”组成的比特串
2.2 随机数发生器 randomnumbergenerator 产生随机二元序列的器件或程序
随机性假设ramdommessyphsis 对二元序列做随机性检测时,首先假设该序列是随机的,这个假设称为原假设或零股设,记为H
与原假设相反的假设,即这个序列是不随机的,称为备择假设,记为H
2.4 随机性检测randomnesstest 用于二元序列检测的一个函数或过程,可以通过它来判断是否接受随机性原假设
2.5 显著性水平signifieaneelevel 随机性检测中错误地判断某一个随机序列为非随机序列的概率,用a来表示
2.6' 样本sample 用于随机性检测的二元序列,称为样本
样本长度samplelength 个样本的比特个数
2.8 样本数量samplesize 随机性检测的样本的个数 检测参数tesparameter 随机性检测需要设定的参数
GB/T32915一2016 2.10 游程run 序列中由连续的“o”或者“1”组成的自序列,并且该子序列的前导与后继元素都与其本身的元素 不同 符号 下列符号适用于本文件
显著性水平 H 原假设(零假设 H 备择假设 待检序列 待检序列的比特长度 待检序列中的某一个比特，e;=(0,1) 在e的基础上按照一定的规则产生出的新序列 x 2e， 子序列的比特长度 " 求和符号 乘法,有时省略 ln(.r r的自然对数 以2为底的r的对数 log(.r) 不大于的最大整数 Lr 从著干个元素中取最大值 maX 更(.r 标准正态分布函数 统计值 余误差函数(ComplementaryErrorFunetion _value -种衡量样本随机性好坏的度量指标
erfc GammaFunction 不完全伽玛函数(nomplete igamc 待检序列中1的比例 V.(obs) 待检序列中游程的总数 ApEn(m 待检序列的近似嫡 通用统计检测中待检序列L位子序列个数 K 通用统计中子序列长度 L 线性复杂度检测中子序列的线性复杂度 L M 矩阵秩检测中矩阵的行数 爪 N 个个n比特序列中m位子序列的个数 矩阵秩检测中矩阵的列数,或者是通用统计检测中初始序列L位子序列的个数 Q 自相关检测中的时延 d 用来计算复系数工的模值的运算 modlulus(.r " 重叠子序列检测中的第一个统计值 重叠子序列检测中的第二个统计值 V'重
GB/T32915一2016 随机性检测 4.1单比特频数检测方法 4.1.1概述 单比特频数检测是最基本的检测,用来检测一个二元序列中0和1的个数是否相近
也就是说,若 已知一个长度为n的二元序列检测该序列是否具有较好的0、1平衡性
4.1.2检测步骤 单比特频数检测步骤如下 第一步;该检测将待检序列e中的0和1分别转换成一1和1,X，=2e，一1(1
GB/T32915一2016 列通过块内频数检测;否则认为该待检序列未通过块内频数检测
4.3扑克检测方法 4.3.1概述 扑克检测用来检测长度为m的2”种子序列类型的个数是否接近,对于随机的序列,2”种子序列 的个数应该接近
4.3.2检测步骤 扑克检测步骤如下 "个长度为朋的非重叠子序列,将多余的比特舍弃
统计第 第一步:将待检序列划分成N- 种子序列模式出现的频数,用n,((I
GB/T32915一2016 第四步;计算 Vw=w
一更; 'y;=更一2y;-十更; 一？ V重" V'更; 第五步;计算P_aluel=igame ,P_alue2=igamc2" 4.4.3结果判定 将4.4.2中计算得出的两个Ptalue结果与显著性水平a进行比较
如果Paluel>a P_talue2>a,则认为待检序列通过重叠子序列检测
4.5游程总数检测方法 4.5.1概述 游程是指序列中由连续的“0"或者“1”组成的子序列,并且该子序列的前导与后继元素都与其本身 的元素不同
游程总数检测主要检测待检序列中游程的总数是否服从随机性要求
4.5.2检测步骤 游程总数检测步骤如下 3 时 第一步:对长度为n的待检序列eie2E
,计算V.(obs)= r(i)十1
其中,当e，=e+ r(i)=0;否则,r(i)=1
第二步;计算序列中1的比例开= IV.ods)一2ur一T门 第三步;计算尸 alue=erfe 22nr( 一开 4.5.3结果判定 将4.5.2中计算得出的Pualue结果与显著性水平a进行比较
如果Pualue>a,则认为待检序 列通过游程总数检测
4.6游程分布检测方法 4.6.1概述 游程分布检测用于检测序列中相同长度游程分布是否均匀,随机的序列中,相同长度的游程数目应 该接近一致
4.6.2检测步骤 游程分布检测步骤如下 第一步计算
-",1sis胖来出病足"a了的最大做数么 第二步;统计待检序列e中每一个游程的长度
变量b、越，分别记录一个二元序列中长度为i的 1游程和0游程的数目
(gi一e" 第三步;计算v-二 -十
GB/T32915一2016 第四步;计算P_alue一iganeck一1 9 4.6.3结果判定 将4.6.2中计算得出的P_alue结果与显著性水平a进行比较
如果P_calue>a,则认为待检序 列通过游程分布检测
4.7块内最大“1”游程检测方法 4.7.1概述 块内最大“1”游程检测将待检序列划分成N个长度为的子序列,此时=N×m
统计各个子 序列中的最长“1”游程长度,通过并将其归人相应的集合,根据各个子序列中最大1游程的分布来评价 待检序列的随机性
4.7.2检测步骤 块内最大“1”游程的检测步骤如下 第一步;将待检序列e划分成N- "个长度为"的非重叠子序列,贪弃多余的位不用 第二步;计算每一个子序列中最大1游程的长度,并将其归人相应的集合{u UnU1，U u;一N开 第三步;计算统计值V 其中,u，和开，的定义参见A.7
-习 N开 第四步;计算P_alue=igamnc3. 4.7.3结果判定 将4.7.2中计算得出的P_alue结果与显著性水平a进行比较
如果P_alue>a,则认为待检序 列通过块内最大“1”游程检测
4.8二元推导检测方法 4.8.1概述 二元推导检测的目的是判定第人次二元推导序列中0和1的个数是否接近一致
一次二元推导序 列是一个长度为n-1的二元序列,它是通过依次将初始序列中两个相邻比特作异或操作所得的结果
长度为n一的第次二元推导序列,是成功执行上述操作瓦次所得的结果序列
二元推导检测用于 检测次推导后0,l的个数是否接近一致,对于一个随机的序列,无论多少次推导之后其0,l的个数都 应该接近一致
4.8.2检测步骤 二元推导检测步骤如下 第一步;对待检序列e,依次将初始序列中相邻两个比特作异或操作得到新序列e',即e'=e e+1
第二步;重复第一步;操作次
出一 第三步:将新序列'中的0和1分别转换成一1和1,然后对其累加求和得S！一
GB/T32915一2016 第四步;计算统计值V n 第五步:计算P_alue=erfc( 厄 4.8.3结果判定 将4.8.2中计算得出的P_alue结果与显著性水平a进行比较
如果P_alue>a,则认为待检序 列通过二元推导检测
4.9自相关检测方法 4.9.1概述 自相关检测用来检测待检序列与将其左移(逻辑左移)d位后所得新序列的关联程度
一个随机序 列应该和将其左移任意位所得的新序列都是独立的,故其关联程度也应该很低,即得到的新序列中0,1 的个数应该接近一致
4.9.2检测步骤 自相关检测步骤如下 第 一步计算A(d)-习e田ea 2A)二["-d)/l 第二步;计算统计值V= 、n一d 第三步;计算P_alue=ert 4.9.3结果判定 将4.9.2中计算得出的P_alue结果与显著性水平
进行比较
如果P_talue>a,则认为待检序 列通过自相关检测
4.10矩阵秩检测方法 4.10.1概述 矩阵秩检测用来检测待检序列中给定长度的子序列之间的线性独立性
由待检序列构造矩阵,然 后检测矩阵的行或列之间的线性独立性,矩阵秩的偏移程度可以给出关于线性独立性的量的认识,从而 影响对二元序列随机性好坏的评价
4.10.2检测步骤 矩阵秩检测步骤如下 第一步;将待检序列e分成大小为32×32的子序列,共有N 个,舍弃多余的位不用
将 2又2 每一个32×32的子序列组装成一个32×32的矩阵,此矩阵有32行32列,每一行则由序列e中连续的 32位填充
第二步;计算每一个矩阵的铁R.( i=l,2,,N 第三步令F,为秩为32的矩阵的个数,令F为秩为3的矩阵的个数,则N一F一F为秧
GB/T32915一2016 小于31的矩阵的个数
第四步;计算统计值 E"一0288Ee一MsrraNy.一r一rl8 0.2888N O.5776N 0.1336N 第五步:计算P_value=iganc 4.10.3结果判定 将4.10.2中计算得出的P_alue结果与显著性水平
进行比较
如果P_ulue>a.则认为待检 序列通过矩阵秩检测
4.11累加和检测方法 4.11.1概述 累加和检测通过判断待检序列的各个子序列中最大的偏移(与0之间),也就是最大累加和与一个 随机序列应具有的最大偏移相比较,以判断待检序列的随机性
4.11.2检测步骤 累加和检测步骤如下 第一步;将待检序列e中的0和1分别转换为-1和1,X，,=2e;一1(1
GB/T32915一2016 ’ 序列e的结尾即可得到e',新序列'的长度为n 一n十m-1
第二步;计算e'中所有的2”个m位子序列模式的出现频数,记m位模式i,出现的频数 为u,i
v1 第三步;对于所有的i(0<<2"-1),计算C"- 第四步;计算9(a 第五步;用m十1代替m,重复操作第一步至第四步,计算得到9("十 第六步;计算ApEn(w)=早"”一早"",计算统计值V=2a[In2-ApEawm]. 第七步;计算P_alue=igamc2" 4.12.3结果判定 将4.12.2中计算得出的P_ulue结果与显著性水平a进行比较
如果P_vulue>a,则认为待检 序列通过近似嫡检测
4.13线性复杂度检测方法 4.13.1概述 线性复杂度检测用于检测各等长子序列的线性复杂度分布是否符合随机性的要求
将待检序列划 分成N个长度为M的子序列,此时n=N×M,然后利用Berlekamp-Massey算法计算每个子序列的线 性复杂度Li,根据L，的分布情况判断待测序列的随机性
4.13.2检测步骤 线性复杂度检测步骤如下 第一步;将待检序列e划分为N-"个长度为m的非重叠子序列,将多余的比特舍弃 Lmn 第二步;计算每一个子序列的线性复杂度L,(
GB/T32915一2016 4.13.3结果判定 将4.13.2中计算得出的P_ulue结果与显著性水平a进行比较
如果P_ulue>a,则认为待检 序列通过线性复杂度检测
4.14Maurer通用统计检测方法 4.14.1概述 Maurer通用统计检测用于检测待检序列能否被无损压缩
因为随机序列是不能被显著压缩,因此 如果待检序列能被显著地压缩,则认为该序列不随机
4.14.2检测步骤 Maurer通用统计检测步骤如下 第一步;将待检序列e分成两部分;初始序列和测试序列
初始序列包括Q个L位的非重叠的子 序列,测试序列包括K个L位的非重叠的子序列,将多余的位(不够组成一个完整的位子序列)舍 弃,K -Q. - 第二步针对初始序列,创建一个表,它以L位值作为表中的索引值T,(1
GB/T32915一2016 第四步;计算门限值T=/2.99573274n
第五步计算N,=0贴x" 第六步:计算系数f，小于门限值丁的复数个数,记作N1 第七步计算统计值V=(N-N,)， 0.95×0.05× 第八步;计算P_ulue=erfe 见 4.15.3结果判定 将4.15.2中计算得出的尸_alue结果与显著性水平
进行比较 如果尸_-wie>,则认为待检 序列通过离散傅立叶检测
注:本章规定的检测方法说明性原理参见附录A,检测参数设置参见附录B 随机数发生器检测 5.1 随机数发生器检测概述 对随机数发生器的检测,首先对采集到的二元序列进行随机性检测,在随机性检测的基础上对随机 数发生器进行判断
随机性检测的方法利用第4章规定的15种随机性检测方法
5.2采集 本标准宜采集随机数样本数量不少于1000,每个样本长度不低于10比特
5.3检测 对每一个样本按第4章措述的检测方法进行检测,分别得到每一个随机性检测项目的P_ualue 值,记录这些结果
5.4判定 对于每一个随机性检测项目,统计P_u/ue值不小于显著性水平a(表示该样本通过该项检测)的 样本个数
记样本数武为
刚道过给围的样本个数丛不小于一一何如.当样本数 量为1000个,显著性水平
为0.0时,如果通过的样本个数不小于981,则随机数发生器通过此项检 测;否则,未通过此项检测
如果随机数发生器通过本标准规定的所有检测项目,则随机数发生器通过本标准检测;否则,未通 过本标准检测
对于使用随机数发生器的各种装置或设备,其随机性检测可参照本标准
11
GB/T32915一2016 附 录A 资料性附录 随机性检测原理 单比特频数检测 A.1 单比特频数检测是最基本的检测,用来检测一个二元序列中0和1的个数是否相近
也就是说,若 已知一个长度为n的二元序列,检测该序列是否具有较好的0、1平衡性
令nw,n分别表示该序列中 0和1的数目
对一个随机序列,当其长度充分大时,其统计值V应该服从标准正态分布: V-2("- A.2块内频数检测 块内频数检测用来检测待检序列的m位子序列中1的个数是否接近m/2
对随机序列来说,其任 意长度的朋位子序列中1的个数都应该接近n/2
块内频数检测将待检序列划分成N个子序列,每个子序列的长度为从,有从=N×m
当然,如果 "不能被朋整除,必然会有多余位,此时将多余的位舍弃
计算每一个子序列中1所占的比例,设为 ,1
GB/T32915一2016 艾 令A(d (e，田en表示待检序列与将其左移d位后所得新序列之间不同元素的个数,称 d为时延
2[A(d -d/2 n一 统计值V一 应该服从标准正态分布
nd A.10 矩阵秩检测 矩阵秩检测用来检测待检序列中给定长度的子序列之间的线性独立性
由待检序列构造矩阵,然 后检测矩阵的行或列之间的线性独立性,矩阵秩的偏移程度可以给出关于线性独立性的量的认识,从而 影响对序列随机性好坏的评价 对于一个MxQ矩阵来说,其秩(用R表示)可以取下=0,1,2,,m[m=min(M.Q)]之间的数
对于一个由随机序列构造的MXQ矩阵来说,R取r的概率，应为 Q)(1一2-M ，=2r(Q+M- “i一" p，=2 令Fn.F
和N一F
一r,分别表示秩为M.M-1以及秩小于M-1的矩阵个数,选取M- 32,Q=32,则统计值 一r Fu-0.2888N" N二F二F-0.1336ND E V=- O.1336N 0.2888N 0.5776N 应该服从自由度为2的X=分布
其中,0.2888,0.5776和0.1336分别为秩为32、31以及小于31 的矩阵概率,N为由序列构造的矩阵的总个数
A.11累加和检测 累加和检测将待检序列的各个子序列中最大的偏移(与0之间),也就是最大累加和与一个随机序 列应具有的最大偏移相比较,以判断待检序列的最大偏移是过大还是过小
实际上,随机序列的最大偏 移应该接近0,所以累加和不能过大,也不能过小累加和可以是负数)
根据最大偏移值来判断待检序 列的随机程度
构造随机变量X=2e;一1,设 s，=X，十+X，=2(e十+e)-; 累加和检测根据s的最大值maxi,|s来检测待检序列的随机性
根据以下方法计算P一alue 一1)=
GB/T32915一2016 著地压缩,则认为该序列是不随机的,因为随机序列是不能被显著压缩的
通用统计检测可以用来检测待检序列多方面的特性,但这并不意味着通用统计检测是前面几个检 测的拼装,而是通用统计检测完全采取了和其他检测所不同的方法
一个序列可以通过通用统计检测 当且仅当这个序列是不可压缩的
通用统计检测的目的是检测待检序列任何统计上的缺陷
通用统计检测需要的数据量很大,它将序列分成长度为L的子序列,然后将待检序列分成两部分 初始序列和检测序列
初始序列包括Q个子序列,Q应该大于等于10×2';检测序列包括K个子序 列,K应该大于等于1000×2 因此,序列长度n应为10×2十1000×2',而L的取值范围应为 1
GB/T32915一2016 附 录 B 资料性附录 随机性检测参数设置表 随机性检测参数设置表见表B.1 表B.1 序列长度儿=1000000比特时 序号 检测项目 序列长度及参数建议 的参数推荐值 单比特频数检测 l00 7 块内频数检测 n=100 n>100,>20 扑克检测 m=4,8 重叠子序列检测 m=2,5 log21 游程总数检测 n100 游程分布检测 n>100 块内最大“1”游程检测 当M=8时,N>16,n=N×M m=10000 二元推导检测 n>100 k=3,7 n 2 自相关检测 l=1,2,8,16 n-d)>10 nM×Q 矩阵秩检测 10 M=32.Q=32 -N×MxQ要小 1 累加和检测 n>100 12 近似嫡检测 =5 log"n n>10" Me[500,500o] 13 线性复杂度检测 =500 >200 M n=(Q十K)×1 LE[l,16],Q>10×2"” 通用统计检测 14 Q~l000×2' 离散傅立叶检测 n>1000 19
信息安全技术二元序列随机性检测方法GB/T32915-2016
在现代的信息安全技术中，加密算法是保证数据安全的重要手段之一。而加密算法的安全性取决于密钥的随机性。因此，在加密过程中需要使用高质量的随机数生成器来产生随机密钥。
然而，由于计算机系统的本质特点，所产生的随机数实际上并不是完全随机的，而是伪随机数。这就需要对随机数的随机性进行检测。
二元序列是一种被广泛应用于随机性检测的方法。它通过比较随机序列中01出现的次数，判断随机序列的随机程度。
GB/T32915-2016是中国国家标准化组织发布的一项关于二元序列随机性检测方法的标准。该标准详细描述了二元序列随机性检测的方法、指标、样本大小以及结果评估等内容。
该标准主要包括以下三个部分：
- 二元序列统计检测方法
- 二元序列长程相关检测方法
- 二元序列最大次数检测方法
这些方法旨在检测随机序列中01出现的规律性，从而判断其是否具有足够的随机性。对于不符合要求的序列，需要进行进一步的处理或者重新产生随机数。
总之，二元序列随机性检测是保证信息安全的重要手段之一。GB/T32915-2016提供了一套完整的二元序列随机性检测标准，可以有效地检测随机数生成器的质量。
信息安全技术二元序列随机性检测方法的相关资料
- 了解信息安全技术公钥基础设施证书策略与认证业务声明框架GB/T26855-2011
- 信息安全技术引入可信第三方的实体鉴别及接入架构规范GB/T28455-2012
- 信息系统安全管理评估要求GB/T28453-2012
- 信息安全技术应用软件系统通用安全技术要求GB/T28452-2012
- GB/T28447-2012信息安全技术电子认证服务机构运营管理规范解析
- 信息安全技术二元序列随机性检测方法GB/T32915-2016
- 信息安全技术二元序列随机性检测方法GB/T32915-2016
- 信息安全技术二元序列随机性检测方法GB/T32915-2016
- 信息安全技术二元序列随机性检测方法GB/T32915-2016
- 信息安全技术二元序列随机性检测方法GB/T32915-2016
- 信息安全技术二元序列随机性检测方法GB/T32915-2016
