GM/T 0005-2021 随机性检测规范

ICS35030

CCSL.80

中华人民共和国密码行业标准

GM/T0005—2021

代替GM/T0005—2012

随机性检测规范

Randomnesstestspecification

2021-10-18发布2022-05-01实施

国家密码管理局发布

GM/T0005—2021

目次

前言

…………………………Ⅰ

范围

1………………………1

规范性引用文件

2…………………………1

术语和定义

3………………1

符号

4………………………2

随机性检测方法

5…………………………3

单比特频数检测方法

5.1………………3

块内频数检测方法

5.2…………………3

扑克检测方法

5.3………………………4

重叠子序列检测方法

5.4………………4

游程总数检测方法

5.5…………………5

游程分布检测方法

5.6…………………6

块内最大游程检测方法

5.7……………6

二元推导检测方法

5.8…………………7

自相关检测方法

5.9……………………8

矩阵秩检测方法

5.10……………………8

累加和检测方法

5.11……………………9

近似熵检测方法

5.12……………………9

线性复杂度检测方法

5.13……………10

通用统计检测方法

5.14Maurer………………………11

离散傅立叶检测方法

5.15……………12

随机性检测判定

6…………………………12

概述

6.1…………………12

样本通过率判定

6.2……………………13

样本分布均匀性判定

6.3………………13

随机性检测结果判定

6.4………………13

附录规范性样本长度及检测设置

A()…………………14

附录资料性随机性检测原理

B()………………………16

附录资料性随机性检测结果示例

C()…………………23

GM/T0005—2021

前言

本文件依据给出的规则起草

GB/T1.1—2020。

本文件代替随机性检测规范对随机性检测进行规范为二元序列的随机性

GM/T0005—2012《》,,

检测工作提供科学依据与相比除编辑性修改外主要技术变化如下

。GM/T0005—2012,:

本文件适用范围由适用于对随机数发生器产生的二元序列的随机性检测改为适用于对二

a)“”“

元序列的随机性检测见第章和年版的第章

”(120121);

删除了随机数发生器值游程的术语以及单比特频数检测等个检测项的术语

b)“”、“P”、“”“”15

定义见年版的第章新增了术语样本集见

(20122),“”(3.6);

修改了符号αPvalue的说明见第章和年版的第章增加了符号αTQvalue的

c)、_(420123),、_

说明见第章

(4);

删除了二元序列的检测章节新增随机性检测方法章节分别从概述检测步骤结果判定

d)“”,“”,、、

对项检测方法进行展开说明其中每项检测方法的检测步骤中均增加Qvalue的计算见

15,_(

第章和年版的第章

520124);

删除了随机数发生器的检测章节新增随机性检测判定章节分别从概述样本通过率判

e)“”,“”,、

定样本分布均匀性判定随机性检测结果判定进行说明其中增加了对Qvalue的样本分布

、、,_

均匀性判定要求见第章和年版的第章

[620125)];

修改游程分布检测方法中的统计值构造方法见和年版的

f)(5.6.220124.4.7);

块内最大游程检测方法新增块内最大游程检测模式见

g)“0”(5.7);

累加和检测方法新增后向累加和检测模式见

h)(5.11);

删除随机性检测参数设置表见年版的表

i)“”(2012B.1);

新增三种样本长度及检测设置表见附表

j)(A.1、A.2、A.3);

删除随机性检测结果分析表见年版的附录

k)“”(2012C);

随机性检测原理调整为附录见附录及年版的附录

l)B(B2012A);

修改块内最大游程的i取值见附表及年版的附表

m)π(B.42012A.3);

新增随机性检测结果示例见附录

n)(C)。

请注意本文件的某些内容可能涉及专利本文件的发布机构不承担识别这些专利的责任

。。

本文件的附录是规范性附录本标准的附录附录是资料性附录

A。B、C。

本文件由密码行业标准化技术委员会提出并归口

。

本文件起草单位国家密码管理局商用密码检测中心中国科学院软件研究所中国科学院信息工

:、、

程研究所北京宏思电子技术有限责任公司浙江大学

、、。

本文件主要起草人罗鹏毛颖颖陈华范丽敏马原李亚威张文婧沈海斌陈美会朱少峰

:、、、、、、、、、、

张贺朱双怡

、。

本文件的历次版本发布情况为

:

———GM/T0005—2012。

Ⅰ

GM/T0005—2021

随机性检测规范

1范围

本文件规定了适用于二元序列的随机性检测指标和检测方法

。

2规范性引用文件

本文件没有规范性引用文件

。

3术语和定义

下列术语和定义适用于本文件

。

31

.

二元序列binarysequence

由和组成的比特串

“0”“1”。

注如无特别说明本文件所指的序列均为二元序列

:,。

32

.

随机性假设randomnesshypothesis

对二元序列做随机性检测时首先假设该序列是随机的这个假设称为原假设或零假设记为H

,,,0。

与原假设相反的假设即这个序列是不随机的称为备择假设记为Hα

,,,。

33

.

随机性检测randomnesstest

用于二元序列检测的一个函数或过程可以通过它来判断是否接受随机性原假设

,。

34

.

显著性水平significancelevel

随机性检测中错误地判断随机序列为非随机序列的概率

。

35

.

样本sample

用于随机性检测的二元序列

。

36

.

样本集samplegroup

多个样本的集合

。

37

.

样本长度samplelength

样本的比特个数

。

38

.

样本数量samplesize

样本集中的样本个数

。

1

GM/T0005—2021

39

.

检测参数testparameter

随机性检测需要设定的参数

。

4符号

下列符号适用于本文件

。

d自相关检测中序列逻辑左移的位数

:。

H原假设零假设

0:()。

Hα备择假设

:。

K通用统计检测中待检序列L位子序列个数

:。

L通用统计中子序列长度

:。

Li线性复杂度检测中子序列的线性复杂度

:。

M矩阵秩检测中矩阵的行数

:。

m子序列的比特长度

:。

N一个待检测的n比特序列中m位子序列的个数

:。

n待检二元序列的比特长度

:。

Q矩阵秩检测中矩阵的列数或者是通用统计检测中初始序列L位子序列的个数

:,。

V统计值

:。

Xiεi

:2-1。

α用于样本通过率检测的显著性水平

:。

αT用于样本分布均匀性检测的显著性水平

:。

ε待检二元序列

:。

ε'在ε的基础上按照一定的规则产生出的新序列

:。

π待检二元序列中的比例

:1。

求和符号

∑:。

乘法有时省略

*:,。

xx的自然对数

ln():。

x以为底的x的对数

log2():2。

x不大于x的最大整数

:。

从若干个元素中取最大值

max:。

从若干个元素中取最小值

min:。

Φx标准正态分布的累积分布函数

():。

Pvalue一种衡量样本随机性好坏的度量指标用于样本通过率判定

_:,。

Qvalue一种衡量样本随机性好坏的度量指标用于样本分布均匀性判定

_:,。

erfc余误差函数

:(ComplementaryErrorFunction)。

igamc不完全伽玛函数

:(IncompleteGammaFunction)。

Vnobs待检二元序列中游程的总数

():。

AEnm待检二元序列的近似熵

p():。

modulusx用来计算复系数x的模值的运算

():。

2

GM/T0005—2021

2

Ψm重叠子序列检测中的第一个统计值

∇:。

2

2Ψm重叠子序列检测中的第二个统计值

∇:。

5随机性检测方法

51单比特频数检测方法

.

511概述

..

单比特频数检测是最基本的检测用来检测一个二元序列中和的个数是否相近随机序列应

,01。

具有较好的平衡性

0、1。

512检测步骤

..

单比特频数检测步骤如下

。

第一步该检测将待检序列ε中的和分别转换成和Xiεiin

:,()。

0n1-11=2-11≤≤

第二步累加求和计算得到Sn=Xi

:i。

∑=1

Sn

第三步计算统计值V

:=n。

V

第四步计算Pvalueerfc

:_=。

2

V

第五步计算Qvalue1erfc

:_=。

22

检测设置按附录要求检测原理见附录的

A,BB.1。

513结果判定

..

将中计算得出的Pvalue结果与α进行比较如果Pvalueα则认为待检序列通过单比

5.1.2_,_≥,

特频数检测否则未通过单比特频数检测

,。

52块内频数检测方法

.

521概述

..

m

块内频数检测用来检测待检序列的m位子序列中的个数是否接近对随机序列来说其任意

1。,

2

m

长度的m位子序列中的个数都应该接近

1。

2

522检测步骤

..

块内频数检测步骤如下

。

n

第一步将待检序列ε分成N个长度为m的非重叠子序列将多余的比特舍弃

:=m,。

m

εi-m+j

(1)

j=

1

第二步计算每个子序列中所占的比例πi=∑iN

:1m,1≤≤。

N

2

第三步计算统计量V=mπi-1

:4i=。

∑12

3

GM/T0005—2021

NV

第四步计算Pvalueigamc

:_=,。

22

第五步计算QvaluePvalue

:_=_。

检测设置按附录要求检测原理见

A,B.2。

523结果判定

..

将中计算得出的Pvalue结果与α进行比较如果Pvalueα则认为待检序列通过块内

5.2.2_,_≥,

频数检测否则未通过块内频数检测

,。

53扑克检测方法

.

531概述

..

扑克检测用来检测长度为m的m类子序列的个数是否接近对于随机的序列m类子序列的个

2。,2

数应该接近

。

532检测步骤

..

扑克检测步骤如下

。

n

第一步将待检序列ε划分成N个长度为m的非重叠子序列将多余的比特舍弃统计第i

:=m,。

m

类子序列模式出现的频数用nii表示

,(1≤≤2)。

m

m2

2

第二步计算统计值V=2ni-N

:Ni=。

∑1

mV

第三步计算Pvalueigamc2-1

:_=,。

22

第四步计算QvaluePvalue

:_=_。

检测设置按附录要求检测原理见

A,B.3。

533结果判定

..

将中计算得出的Pvalue结果与α进行比较如果Pvalueα则认为待检序列通过扑克

5.3.2_,_≥,

检测否则未通过扑克检测

,。

54重叠子序列检测方法

.

541概述

..

对任意的正整数m长度为m的二元序列有m类重叠子序列检测将长度为n的待检序列划分

,2。

成n个可叠加的m位子序列对随机二元序列来说由于其具有均匀性故m位可叠加子序列的每一

。,,

类模式出现的概率应该接近

。

542检测步骤

..

重叠子序列检测步骤如下

。

第一步由待检序列ε构造一个新的序列ε'构造方法如下将序列ε最开始的m位数据添加到

:,:-1

序列ε的结尾即可得到新序列ε'新序列ε'的长度为n'nm

,=+-1。

m

第二步计算ε'中每一类m位子序列模式共有类出现的频数记m位子序列模式iiim的

:(2),12…

4

GM/T0005—2021

m

出现频数为viiim计算每一类m位子序列模式共有-1类出现的频数记m位子序列模

12…。-1(2),-1

m

式iiim的出现频数为viiim计算每一个m位子序列模式共有-2类出现的频数记

12…-112…-1。-2(2),

m位子序列模式iiim的出现频数为viiim

-212…-212…-2。

第三步计算

:

m

22

Ψm=2viiim-n

12…

niiim,