书 书 书犐犆犛 ３５ ． ０３０ 犆犆犛犔 ８０ 中华人民共和国密码行业标准 犌犕 ／ 犜 ０００５ — ２０２１ 代替 犌犕 ／ 犜 ０００５ — ２０１２ 随机性检测规范 犚犪狀犱狅犿狀犲狊狊狋犲狊狋狊狆犲犮犻犳犻犮犪狋犻狅狀 ２０２１  １０  １８ 发布 ２０２２  ０５  ０１ 实施 国家密码管理局 发布目 　　 次 前言 Ⅰ ………………………………………………………………………………………………………… １ 　 范围 １ ……………………………………………………………………………………………………… ２ 　 规范性引用文件 １ ………………………………………………………………………………………… ３ 　 术语和定义 １ ……………………………………………………………………………………………… ４ 　 符号 ２ ……………………………………………………………………………………………………… ５ 　 随机性检测方法 ３ ………………………………………………………………………………………… 　 ５．１ 　 单比特频数检测方法 ３ ……………………………………………………………………………… 　 ５．２ 　 块内频数检测方法 ３ ………………………………………………………………………………… 　 ５．３ 　 扑克检测方法 ４ ……………………………………………………………………………………… 　 ５．４ 　 重叠子序列检测方法 ４ ……………………………………………………………………………… 　 ５．５ 　 游程总数检测方法 ５ ………………………………………………………………………………… 　 ５．６ 　 游程分布检测方法 ６ ………………………………………………………………………………… 　 ５．７ 　 块内最大游程检测方法 ６ …………………………………………………………………………… 　 ５．８ 　 二元推导检测方法 ７ ………………………………………………………………………………… 　 ５．９ 　 自相关检测方法 ８ …………………………………………………………………………………… 　 ５．１０ 　 矩阵秩检测方法 ８ …………………………………………………………………………………… 　 ５．１１ 　 累加和检测方法 ９ …………………………………………………………………………………… 　 ５．１２ 　 近似熵检测方法 ９ …………………………………………………………………………………… 　 ５．１３ 　 线性复杂度检测方法 １０ …………………………………………………………………………… 　 ５．１４ 　 Ｍａｕｒｅｒ 通用统计检测方法 １１ ……………………………………………………………………… 　 ５．１５ 　 离散傅立叶检测方法 １２ …………………………………………………………………………… ６ 　 随机性检测判定 １２ ………………………………………………………………………………………… 　 ６．１ 　 概述 １２ ………………………………………………………………………………………………… 　 ６．２ 　 样本通过率判定 １３ …………………………………………………………………………………… 　 ６．３ 　 样本分布均匀性判定 １３ ……………………………………………………………………………… 　 ６．４ 　 随机性检测结果判定 １３ ……………………………………………………………………………… 附录 Ａ （ 规范性 ） 　 样本长度及检测设置 １４ ………………………………………………………………… 附录 Ｂ （ 资料性 ） 　 随机性检测原理 １６ ……………………………………………………………………… 附录 Ｃ （ 资料性 ） 　 随机性检测结果示例 ２３ ………………………………………………………………… 犌犕 ／ 犜 ０００５ — ２０２１前 　　 言 　　 本文件依据 ＧＢ ／ Ｔ１．１ — ２０２０ 给出的规则起草 。 本文件代替 ＧＭ ／ Ｔ０００５ — ２０１２ 《 随机性检测规范 》， 对随机性检测进行规范 ， 为二元序列的随机性 检测工作提供科学依据 。 与 ＧＭ ／ Ｔ０００５ — ２０１２ 相比 ， 除编辑性修改外主要技术变化如下 ： ａ ） 　 本文件适用范围由 “ 适用于对随机数发生器产生的二元序列的随机性检测 ” 改为 “ 适用于对二 元序列的随机性检测 ”（ 见第 １ 章和 ２０１２ 年版的第 １ 章 ）； ｂ ） 　 删除了 “ 随机数发生器 ”、“ Ｐ 值 ”、“ 游程 ” 的术语以及 “ 单比特频数检测 ” 等 １５ 个检测项的术语 定义 （ 见 ２０１２ 年版的第 ２ 章 ）， 新增了术语 “ 样本集 ”（ 见 ３．６ ）； ｃ ） 　 修改了符号 α 、 犘 ＿ 狏犪犾狌犲 的说明 （ 见第 ４ 章和 ２０１２ 年版的第 ３ 章 ）， 增加了符号 α 犜 、 犙 ＿ 狏犪犾狌犲 的 说明 （ 见第 ４ 章 ）； ｄ ） 　 删除了 “ 二元序列的检测 ” 章节 ， 新增 “ 随机性检测方法 ” 章节 ， 分别从概述 、 检测步骤 、 结果判定 对 １５ 项检测方法进行展开说明 ， 其中每项检测方法的检测步骤中均增加 犙 ＿ 狏犪犾狌犲 的计算 （ 见 第 ５ 章和 ２０１２ 年版的第 ４ 章 ）； ｅ ） 　 删除了 “ 随机数发生器的检测 ” 章节 ， 新增 “ 随机性检测判定 ” 章节 ， 分别从概述 、 样本通过率判 定 、 样本分布均匀性判定 、 随机性检测结果判定进行说明 ， 其中增加了对 犙 ＿ 狏犪犾狌犲 的样本分布 均匀性判定要求 ［ 见第 ６ 章和 ２０１２ 年版的第 ５ 章 ）］； ｆ ） 　 修改游程分布检测方法中的统计值构造方法 （ 见 ５．６．２ 和 ２０１２ 年版的 ４．４．７ ）； ｇ ） 　 块内最大游程检测方法新增块内最大 “ ０ ” 游程检测模式 （ 见 ５．７ ）； ｈ ） 　 累加和检测方法新增后向累加和检测模式 （ 见 ５．１１ ）； ｉ ） 　 删除 “ 随机性检测参数设置表 ”（ 见 ２０１２ 年版的表 Ｂ．１ ）； ｊ ） 　 新增三种样本长度及检测设置表 （ 见附表 Ａ．１ 、 Ａ．２ 、 Ａ．３ ）； ｋ ） 　 删除 “ 随机性检测结果分析表 ”（ 见 ２０１２ 年版的附录 Ｃ ）； ｌ ） 　 随机性检测原理调整为附录 Ｂ （ 见附录 Ｂ 及 ２０１２ 年版的附录 Ａ ）； ｍ ） 　 修改块内最大游程的 π 犻 取值 （ 见附表 Ｂ．４ 及 ２０１２ 年版的附表 Ａ．３ ）； ｎ ） 　 新增随机性检测结果示例 （ 见附录 Ｃ ）。 请注意本文件的某些内容可能涉及专利 。 本文件的发布机构不承担识别这些专利的责任 。 本文件的附录 Ａ 是规范性附录 。 本标准的附录 Ｂ 、 附录 Ｃ 是资料性附录 。 本文件由密码行业标准化技术委员会提出并归口 。 本文件起草单位 ： 国家密码管理局商用密码检测中心 、 中国科学院软件研究所 、 中国科学院信息工 程研究所 、 北京宏思电子技术有限责任公司 、 浙江大学 。 本文件主要起草人 ： 罗鹏 、 毛颖颖 、 陈华 、 范丽敏 、 马原 、 李亚威 、 张文婧 、 沈海斌 、 陈美会 、 朱少峰 、 张贺 、 朱双怡 。 本文件的历次版本发布情况为 ： ——— ＧＭ ／ Ｔ０００５ — ２０１２ 。 Ⅰ 犌犕 ／ 犜 ０００５ — ２０２１随机性检测规范 １ 　 范围 本文件规定了适用于二元序列的随机性检测指标和检测方法 。 ２ 　 规范性引用文件 本文件没有规范性引用文件 。 ３ 　 术语和定义 下列术语和定义适用于本文件 。 ３ ． １ 　 二元序列 　 犫犻狀犪狉狔狊犲狇狌犲狀犮犲 由 “ ０ ” 和 “ １ ” 组成的比特串 。 注 ： 如无特别说明 ， 本文件所指的序列均为二元序列 。 ３ ． ２ 　 随机性假设 　 狉犪狀犱狅犿狀犲狊狊犺狔狆狅狋犺犲狊犻狊 对二元序列做随机性检测时 ， 首先假设该序列是随机的 ， 这个假设称为原假设或零假设 ， 记为 犎 ０ 。 与原假设相反的假设 ， 即这个序列是不随机的 ， 称为备择假设 ， 记为 犎 α 。 ３ ． ３ 　 随机性检测 　 狉犪狀犱狅犿狀犲狊狊狋犲狊狋 用于二元序列检测的一个函数或过程 ， 可以通过它来判断是否接受随机性原假设 。 ３ ． ４ 　 显著性水平 　 狊犻犵狀犻犳犻犮犪狀犮犲犾犲狏犲犾 随机性检测中错误地判断随机序列为非随机序列的概率 。 ３ ． ５ 　 样本 　 狊犪犿狆犾犲 用于随机性检测的二元序列 。 ３ ． ６ 　 样本集 　 狊犪犿狆犾犲犵狉狅狌狆 多个样本的集合 。 ３ ． ７ 　 样本长度 　 狊犪犿狆犾犲犾犲狀犵狋犺 样本的比特个数 。 ３ ． ８ 　 样本数量 　 狊犪犿狆犾犲狊犻狕犲 样本集中的样本个数 。 １ 犌犕 ／ 犜 ０００５ — ２０２１３ ． ９ 　 检测参数 　 狋犲狊狋狆犪狉犪犿犲狋犲狉 随机性检测需要设定的参数 。 ４ 　 符号 下列符号适用于本文件 。 犱 ： 自相关检测中序列逻辑左移的位数 。 犎 ０ ： 原假设 （ 零假设 ）。 犎 α ： 备择假设 。 犓 ： 通用统计检测中待检序列 犔 位子序列个数 。 犔 ： 通用统计中子序列长度 。 犔 犻 ： 线性复杂度检测中子序列的线性复杂度 。 犕 ： 矩阵秩检测中矩阵的行数 。 犿 ： 子序列的比特