GM-T 0005-2021 清晰版 随机性检测规范

ICS35.030CCSL80中华人民共和国密码行业标准代替GM／T0005—2012R2021-10-18发布2022-05-01实施国家密码管理局发布GM／T0005—2021 1范围 2规范性引用文件 3术语和定义 4符号 5随机性检测方法 5.1单比特频数检测方法 5.2块内频数检测方法 5.3扑克检测方法 5.4重叠子序列检测方法 5.5游程总数检测方法 5.6游程分布检测方法 5.7块内最大游程检测方法 5.8二元推导检测方法 5.9自相关检测方法 5.10矩阵秩检测方法 5.11累加和检测方法 5.12近似熵检测方法 5.13线性复杂度检测方法 5.14Maurer通用统计检测方法 5.15离散傅立叶检测方法 6随机性检测判定 6.2样本通过率判定 6.3样本分布均匀性判定 6.4随机性检测结果判定 附录A（规范性）样本长度及检测设置 附录B（资料性）随机性检测原理 附录C（资料性）随机性检测结果示例 ⅠGM／T0005—2021本文件依据GB/T1.1—2020给出的规则起草。本文件代替GM/T0005—2012《随机性检测规范》，对随机性检测进行规范，为二元序列的随机性检测工作提供科学依据。与GM/T0005—2012相比，除编辑性修改外主要技术变化如下：元序列的随机性检测”（见第1章和2012年版的第1章定义（见2012年版的第2章新增了术语“样本集”（见3.6);说明（见第4章第5章和2012年版的第4章均匀性判定要求［见第6章和2012年版的第5章52012B;k2012lBBAn请注意本文件的某些内容可能涉及专利。本文件的发布机构不承担识别这些专利的责任。本文件的附录A是规范性附录。本标准的附录B、附录C是资料性附录。本文件由密码行业标准化技术委员会提出并归口。本文件起草单位：国家密码管理局商用密码检测中心、中国科学院软件研究所、中国科学院信息工程研究所、北京宏思电子技术有限责任公司、浙江大学。本文件主要起草人：罗鹏、毛颖颖、陈华、范丽敏、马原、李亚威、张文婧、沈海斌、陈美会、朱少峰、张贺、朱双怡。本文件的历次版本发布情况为：—GM/T0005—2012。1GM／T0005—2021本文件规定了适用于二元序列的随机性检测指标和检测方法。2规范性引用文件本文件没有规范性引用文件。3术语和定义下列术语和定义适用于本文件。3.1注：如无特别说明，本文件所指的序列均为二元序列。3.2对二元序列做随机性检测时，首先假设该序列是随机的，这个假设称为原假设或零假设，记为H0。3.3用于二元序列检测的一个函数或过程，可以通过它来判断是否接受随机性原假设。3.4随机性检测中错误地判断随机序列为非随机序列的概率。3.5用于随机性检测的二元序列。3.6多个样本的集合。3.7样本的比特个数。3.8样本集中的样本个数。2GM／T0005—20213.9随机性检测需要设定的参数。下列符号适用于本文件。K：通用统计检测中待检序列L位子序列个数。L：通用统计中子序列长度。Li：线性复杂度检测中子序列的线性复杂度。M：矩阵秩检测中矩阵的行数。V：统计值。xi：2εi-Σ：求和符号。lnΦQ℃35随机性检测方法5.1单比特频数检测方法单比特频数检测是最基本的检测，用来检测一个二元序列中0和1的个数是否相近。随机序列应具有较好的0、1平衡性。单比特频数检测步骤如下。in检测设置按附录A要求，检测原理见附录B的B.1。特频数检测，否则未通过单比特频数检测。5.2块内频数检测方法块内频数检测步骤如下。m4GM／T0005—2021Q℃＝P℃检测设置按附录A要求，检测原理见B.2。频数检测，否则未通过块内频数检测。5.3扑克检测方法数应该接近。扑克检测步骤如下。i扑克检测步骤如下。Q℃＝P℃检测设置按附录A要求，检测原理见B.3。检测，否则未通过扑克检测。5.4重叠子序列检测方法类模式出现的概率应该接近。重叠子序列检测步骤如下。ii5GM／T0005—2021iiiiiiiii。第三步：计算第四步：计算,第六步：计算Q_℃alue1=P_℃alue1,Q_℃alue2=P_℃alue2。检测设置按附录A要求，检测原理见B.4。列检测。5.5游程总数检测方法游程是指序列中由连续的“0”或者“1”组成的子序列，并且该子序列的前导与后继元素都与其本身的元素不同。游程总数检测主要检测待检序列中游程的总数是否服从随机性要求。游程总数检测步骤如下。n-1εi=0in6GM／T0005—2021检测设置按附录A要求，检测原理见B.5。总数检测，否则未通过游程总数检测。5.6游程分布检测方法游程分布检测用于检测序列中相同长度游程分布是否均匀，随机的序列中，相同长度的游程数目应该接近一致，且游程长度每增加一比特，游程数目应接近减半。游程分布检测步骤如下。i。ikQ℃＝P℃检测设置按附录A要求，检测原理见B.6。分布检测，否则未通过游程分布检测。5.7块内最大游程检测方法块内最大游程检测方法分别对块内最大“1”游程和块内最大“0”游程两种模式进行检测。将待检序游程长度，根据各个子序列中最大“1”游程、最大“0”游程的分布来评价待检序列的随机性。7照表B.3的规则将其归入相应的集合中。iii件附表B.4。Q℃＝P℃检测设置按附录A要求，检测原理见B.7。最大游程检测，否则未通过块内最大游程检测。5.8二元推导检测方法二元初始序列，依次将初始序列中两个相邻比特做异或操作，即可得到该序列的一次二元推导序列，长个随机的序列，无论进行多少次推导，其0、1的个数都应该接近一致。二元推导检测步骤如下。n－k检测设置按附录A要求，检测原理见B.8。推导检测，否则未通过二元推导检测。8GM／T0005—20215.9自相关检测方法列应该和将其左移任意位所得的新序列都是独立的，故其关联程度也应该很低，即初始序列与将其左移。自相关检测步骤如下。n－d-1检测设置按附录A要求，检测原理见B.9。关检测，否则未通过自相关检测。5.10矩阵秩检测方法矩阵秩检测用来检测待检序列中给定长度的子序列之间的线性独立性。由待检序列构造矩阵，然后检测矩阵的行或列之间的线性独立性，矩阵秩的偏移程度可以给出关于线性独立性的量的认识，从而影响对二元序列随机性好坏的评价。矩阵秩检测步骤如下。矩阵秩检测步骤如下。的32位填充。Rii=1NFFN－FM－FM-1小于31的矩阵的个数。第四步：计算统计值V=十十5776N十十5776N1336N9Q℃＝P℃检测设置按附录A要求，检测原理见B.10。阵秩检测，否则未通过矩阵秩检测。累加和检测方法分别对前向累加和、后向累加和两种模式进行检测。前向累加和检测从待检序列第1比特开始，逐比特向后计算，后向累加和检测从待检序列最后1比特开始，逐比特向前计算，通过判断待检序列的各个子序列中最大的偏移（与0之间也就是最大累加和与一个随机序列应具有的最大偏移相比较，以判断待检序列的随机性。累加和检测步骤如下。ii第四步：计算Q℃＝P℃检测设置按附录A要求，检测原理见B.11。加和检测，否则未通过累加和检测。5.12近似熵检测方法表明待检序列具有规则性和连续性；差异值较大则表明待检序列具有不规则性和不连续性。对任意一GM／T0005—2021近似熵检测步骤如下。iiiijii制数值。。Q℃＝P℃检测设置按附录A要求，检测原理见B.12。似熵检测，否则未通过近似熵检测。5.13线性复杂度检测方法线性复杂度检测用于检测各等长子序列的线性复杂度分布是否符合随机性的要求。将待检序列划LiLi线性复杂度检测步骤如下：LiiiGM／T0005—2021iiiiiQΨ＝PΨ检测设置按附录A要求，检测原理见B.13。性复杂度检测，否则未通过线性复杂度检测。如果待检序列能被显著地压缩，则认为该序列不随机。Maurer多余位舍弃不用。jLjjjijjjiji。检测设置按附录A要求，检测原理见B.14。GM／T0005—2021MaurerMaurer5.15离散傅立叶检测方法离散傅立叶检测使用频谱的方法来检测序列的随机性。对待检序列进行傅立叶变换后可以得到尖正常的范围；如果不正常的尖峰个数超过了允许值，即可认为待检序列是不随机的。离散傅立叶检测步骤如下：i2εi-1。ff。fjjfjfjj \j。检测设置按附录A要求，检测原理见B.15。散傅立叶检测，否则未通过离散傅立叶检测。6随机性检测判定应采用第5章规定的15种随机性检测方法和附录A规定的检测设置对二元序列样本集进行随机性检测。一种随机性检测方法对应至少一个随机性检测项目，其中如某一项随机性检测方法采用不同检测参数设置（详见附录A或具有不同检测模式（如块内最大游程检测方法、累加和检测方法或具GM／T0005—2021有多个统计值（如重叠子序列检测方法应作为单独的随机性检测项目进行检测，并分别对二元序列样本集的每个检测项目的样本通过率、分布均匀性进行合格判定。比如累加和检测方法包括前向累加和、后向累加和两种模式，前向累加和、后向累加和应作为2个独立的检测项目进行检测，并分别对二元序列样本集中前向累加和、后向累加和的样本通过率、分布均匀性进行合格判定。本文件确定二元序列样本集中的样本数量为1000。6.2样本通过率判定集通过该项检测，否则未通过此项检测。例如，样本数量为1000个，则通过该检测项目的样本个数应大于或等于981。6.3样本分布均匀性判定i=10。6.4随机性检测结果判定当所有随机性检测项目的检测结果同时满足6.2规定的样本通过率判定和6.3规定的样本分布均匀性判定时，该二元序列样本集通过本文件的随机性检测，否则未通过随机性检测。GM／T0005—2021附录A（规范性）样本长度及检测设置A.120000比特样本使用的检测方法与检测参数长度为20000比特的样本按照表A.1的随机性检测方法和检测参数进行随机性统计检测。表A.120000比特样本检测设置序号随机性检测方法检测参数1单比特频数检测 2块内频数检测m=10003扑克检测m=4,84重叠子序列检测m=3,55游程总数检测—6游程分布检测 7块内最大游程检测m=1288二元推导检测k=3,79自相关检测d=2,8,16累加和检测—近似熵检测m=2,5离散傅立叶检测—A.21000000比特样本适用的检测方法与检测参数长度为1000000比特的样本按照表A.2的随机性检测方法和检测参数进行随机性统计检测。表A.21000000比特样本检测设置序号随机性检测方法检测参数1单比特频数检测 2块内频数检测m=100003扑克检测m=4,84重叠子序列检测m=3,55游程总数检测—6游程分布检测—7块内最大游程检测m=10000表A.21000000比特样本检测设置（续）序号随机性检测方法检测参数8二元推导检测k=3,79自相关检测矩阵秩检测—累加和检测 近似熵检测m=2,5线性复杂度检测m=500,1000通用统计检测L=7,Q=1280离散傅立叶检测 A.3100000000比特样本检测建议长度为100000000比特的样本按照表A.3的随机性检测方法和检测参数进行随机性统计检测。表A.3100000000比特样本检测设置序号随机性检测方法检测参数1单比特频数检测 2块内频数检测m=1000003扑克检测m=4,84重叠子序列检测m=3,5,75游程总数检测—6游程分布检测—7块内最大游程检测m=100008二元推导检测k=3,7,159自相关检测矩阵秩检测 累加和检测 近似熵检测m=5,7线性复杂度检测m=5000通用统计检测L=7,Q=1280离散傅立叶检测—GM／T0005—2021附录B（资料性）随机性检测原理B.1单比特频数检测单比特频数检测是最基本的检测，用来检测一个二元序列中0和1的个数是否相近。已知一个长其统计值V应服从标准正态分布：B.2块内频数检测一一m该统计量应该服从自由度为N的χ2分布。B.3扑克检测i的个数是否接近。B.4重叠子序列检测类模式出现的概率应接近。iiiiii2mii2mii：，。B.5游程总数检测游程是二元序列的一个子序列，由连续的0或者1组成，并且其前导和后继元素都与其本身的元素不同。游程总数检测主要检测待检序列中游程的总数是否服从随机性要求。应服从标准正态分布。B.6游程分布检测i2-i。iikiB.7块内最大游程检测将待检序列划分成N个等长的子序列，根据各个子序列中最大“1”／“0”游程的分布来评价待检序列的随机性。ii概率iiGM／T0005—2021nm≥1288≥6272≥750000表B.2K的取值m8K356表B.3集合定义规则对应集合m=8m=128m=10000集合0≤1≤4≤10集合125集合236集合3≥47集合48集合5≥9集合6≥16素个数℃3加1。iim=8m=128m=100000123456B.8二元推导检测GM／T0005—2021B.9自相关检测列应该和将其左移任意位所得的新序列都是独立的，故其关联程度也应该很低。n－d-1为时延。B.10矩阵秩检测矩阵秩检测用来检测待检序列中给定长度的子序列之间的线性独立性。由待检序列构造矩阵，然后检测矩阵的行或列之间的线性独立性，矩阵秩的偏移程度可以给出关于线性独立性的量的认识，从而影响对序列随机性好坏的评价。FFMM-1M-1M=V=十十5776N十十5776N2888N矩阵概率，N为由序列构造的矩阵的总个数。累加和检测将待检序列的各个子序列中最大的偏移（与0之间也就是最大累加和与一个随机序列应具有的最大偏移相比较，以判断待检序列的最大偏移是过大还是过小。实际上，随机序列的最大偏移应该接近0，所以累加和不能过大，也不能过小（累加和可以是负数）。根据最大偏移值来判断待检序列的随机程度。i表B.5累加和的计算前向累加和模式后向累加和模式SS2=x1+x2:SK＝x1+x2+…+xK:Sn＝x1+x2+…+xK+…+xnSS::Sn＝xn＋xn-1+…+xn－K+1+…+x1GM／T0005—2021iP十∝十∝iB.12近似熵检测i叠子序列，令jilili1ii。B.13线性复杂度检测ii iTiiiiiiiGM／T0005—2021ii：著地压缩，则认为该序列是不随机的，因为随机序列是不能被显著压缩的。通用统计检测可以用来检测待检序列多方面的特性，但这并不意味着通用统计检测是前面几个检测的拼装，通用统计检测完全采取了和其他检测所不同的方法，可以检测待检序列某些统计上的缺陷。一个序列可以通过通用统计检测当且仅当这个序列是不可压缩的。通用统计检测需要的数据量很大，它将序列分成长度为L的子序列，然后将待检序列分成两部分：LL首先，从头开始遍历初始序列（以块为单位找到每一个L位模式在初始序列中最后出现的位置（块号如果一个L位模式在初始序列中没有出现，那么将其位置设置为0；此后，从头开始遍历检测序列，每一次都会得到一个L位子序列，计算这个子序列所在的位置与其前面最后一次出现的位置差，也果相加。这样，就可以得到统计值：计算期望值：十∞fn-L验的次数，那么有：∞标准差按如下计算：LKGM／T0005—2021B.15离散傅立叶检测离散傅立叶变换检测使用频谱的方法来检测序列的随机性。对待检序列进行傅立叶变换后可以得入不正常的范围；如果不正常的尖峰个数超过了允许值，即可认为待检序列是不随机的。kji≡\。 jj jj\准正态分布。附录C（资料性）随机性检测结果示例Cn=128输出：P_Ψalue=0.215925,Q_Ψalue=0.892038C2n=100m=10V=7.200输出：P_Ψalue=0.706438,Q_Ψalue=0.706438C.3扑克检测n=128m=4输出：P_Ψalue=0.213734,Q_Ψalue=0.213734C4n=128m=2输出：P_Ψalue1=0.436868;P_Ψalue2=0.723Q_Ψalue1=0.436868;Q_ΨaC5n=128GM／T0005—2021V=0.494817输出：P_Ψalue=0.620729,Q_Ψalue=0.310364C60001001111010110100000001101011111001100111001101101100010110010n=128输出：P_Ψalue=0.970152,Q_Ψalue=0.970152C7(1)块内最大“1”游程检测0001001111010110100000001101011111001100111001101101100010110010n=128输出：P_Ψalue=0.180598,Q_Ψalue=0.180598(2)块内最大“0”游程检测0001001111010110100000001101011111001100111001101101100010110010n=128输出：P_Ψalue=0.839299,Q_Ψalue=0.839299C8000100111101011010000000110101111100110011100110110