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

ICs35.040

L80

备案号:36832—⒛12

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

GM/T0005-2012

随机性检测规范

Randomnesstestspecification

⒛12-O3-21发布⒛12-0S-21实施

国家密码管理局发布

GM/T0005-⒛12

目次

目刂·………………………¨

舀I

1范围·……………f··……………………¨1

2术语和定义¨………·……………………1

3符号和缩略语¨………·…………………3

·…¨

4二元序列的检测……………………4

¨……·

4.1数据格式……………………4

…

……·

4,2显著性水平………∵…··……………

¨:::·4

¨……·

4.3样本长度…¨…¨………………¨………4

……………¨¨¨·

………

¨¨¨¨¨¨…¨¨¨¨

4.4¨¨¨¨¨¨¨¨¨¨¨¨¨

吞¨¨¨¨¨¨¨¨¨¨¨

检测项目¨¨¨¨¨4

4,5结果分析……………8

5随机数发生器的检测¨………………·…………………8

5,1采样…………………8

…

5.2存储…………………·……………8

5,3检测¨………………·

9

5.4判定…¨……………9

附录A(资料性附录)随机性检测原理…………………10

¨

…………·

A,1单比特频数检测……………………10

A。2块内频数检测…………………¨10

………·

A.3扑克检测…………………10

¨

A.4重叠子序列检测………·………………………10

………………·

A,5游程总数检测……………………11

A.6游程分布检测……………………11

“

A。7块内最大1”游程检测……¨…………………¨…………¨…11

A.8二元推导检测……………………12

…

A。9相……………………·

自关检测12

A,10矩阵秩检测¨……·………………13

A.11累加和检测……………………¨13

A,12近似熵检测………………………13

A.13线性复杂度检测………………·…………………14

A。14Maurer通…………

用统计检测14

A。15离散傅立叶检测…………………15

…

附录B(资料性附录)随机性检测参数设置表………………·………16

附录C(资料性附录)随机性检测结果分析表¨………………·………17

髦

Ⅱ

Ⅱ

⒒GM/T0005-⒛12

■

■

亠

■刚曰

Ⅱ

■本标准依据GB/T1.1-2009给出的规则起草。

■

本标准对随机性检测进行规范,为随机性的评估提供科学依据。

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

Ⅱ本标准的附录A、附录B和附录C是资料性附录。

■本标准由国家密码管理局提出并归口。

Ⅱ起:国密码理局用码检测心、国学研所。

本标准草单位家管商密中中科院软件究

主:李、、1张、、、、。

⒒本标准要起草人大为冯登国陈华超周永彬董芳范丽敏许囡囡

Ⅱ

■

冖

■

■

Ⅱ

Ⅱ

鹰]

廖

蘧

藤

蓦

爨

蠛

濠

LⅡ

GM/T0005—2012

随机性检测规范

1范围

本标准规定了商用密码应用中的随机性检测指标和检测方法。

本标准适用于对随机数发生器产生的二元序列的随机性检测。

2术语和定义

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

2.1

二,

元序列"narysequen漠

““

由0”和1”组成的比特串。

2.2

ⅡⅡmbergenerator

随机数发生器ra1ndom

产生随机序列的设备或程序称为随机数发生器。

2.3

随机性假设randomnesshypothesis

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

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

2.4

随机性检测randomnesstest

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

2.5

显著性水平significance1eveI

地一机列机列的概,用α表示。

随机性检测中错误判断某个随序为非随序率来

2.6

样本sample

用于随机性检测的二元序列,称为样本。

2.7

样本长度sampIe1ength

一

个样本的比特个数。

2.8

样本数量samp1esize

随机性检测的样本的个数。

2.9

检测参数testparameter

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

2.10

P值P-vaIue

一种衡量样本随机性好坏的度量指标。

1

GM/T0005-⒛12

2.11

游程mn

““

指序列中由连续的0”或1”组成的子序列,并且该子序列的前导与后继元素都与其本身元素不同。

2,12

单比特频数检测monobitfreqlIencytest

一种统计检测项目,用于检测待检序列中0和1的个数是否相近。

2.13

thinablock

块内频数检测frequencytest耐

“”

一种统计检测项目,用于检测待检序列的留位子序列(称为块)中1的个数是否接近昭/2。

2,14

扑克检测pokertest

一种统计检测项目的个数是否接近。

2,15

重叠子序列

一种统计是否接近。

2.16

游程总

一种

2,17

游程

一种

2.18

块内

一种统服从随机性

要求。

2.19

二元推导检

一种统计检测过依次将初始序列

相两个比特作异三元推导序列中0和1的

中邻

一

数量是否接近致。

2.20

,ntest

自相关检测al1tocorreIati】

一〃

种统计检测项目,用于检测待检序列与将其逻辑左移位后所得新序列的关联程度。

2.21

矩阵秩检测binarymatrixranktest

一种统计检测项目,用于检测待检序列中给定长度的子序列之间的线性独立性。

2.22

累加和检测cumulativetest

一种统计检测项目,它将待检序列的各个子序列中最大偏移(这里指与0之间的最大偏移,即最大

累加和)与一个随机序列应具有的最大偏移相比较,以判断待检序列的最大偏移是否过大或过小。

2.23

近似熵检测approximateentropyte乩

一种统计检测项目,通过比较9,a位可重叠子序列模式的频数和9Pa+1位可重叠子序列模式的频数

2

GˇI/T000⒌-2012

来检测其随机性。

2.24

线性复杂度检测Iinearcomplexitytest

一种统计检测项目,用于检测待检序列的线性复杂度的分布是否符合随机性要求。

2,25

Maurer通s“UniversalTest”

用统计检测Maurer′

一种统计检测项目,用于检测待检序列能否被压缩(无损压缩)。如果待检序列能被显著地压缩,那

么就认为该序列是不随机的。

2.26

离散傅立叶检测discretefouriert

一种统计检测项目,用于检常的峰值个数是否超过了允

许值。

3符号和缩略语

下列符号和

A夕E″(昭)

Ffo

Hα

K

L

Lj

M

N

Q序列的个数

y

ˇ

17(obs)

’

】∶【∶‘

氵

丿

召'↓c

zg‘z9,zc不完

ln(J)J的自然

1og2(jr)以2为底的r的

″2子序列的比特长度

maX从若干个元素中取最大值

仍J〃s(J)用来计算复系数=的模值的运算

`?2o歹

″待检序列的比特长度

Pvalue一个真随机序列比待检验序列随机性差的概率

Φ(tr)标准正态分布函数

∑求和符号

乘法,有时省略

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

;z

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

α显著性水平

GM/T0005-⒛12

ε待检序列

ε

一比,ε=(0,1)

氵待检序列中的某个特氵

εe的上一

在基础按照定的规则产生出的新序列

t待检序列中1的比例

lJj不大于J的最大整数

4二元序列的检测

4.1数据格式

待检数据以比特串的形式接受检测。

4.2显著性水平

α

本标准确定的显著性水平为=0.01。

菇

4.3样本长度

本标准中样本长度选取106比特。

4.4检测项目

4.4,1概述

采用的随机性检测项目共有15项,分为比特频检测、、、

本标准别单数块内频数检测扑克检测重叠

“

1”二

、总测、测、测、元、、

子列检测游程数检游程分布检块内最大游程检推导检测相矩

序自关检测阵秩

Maurer通A描

、、、

测、和测近熵检测线性复杂检测用测、立。

检累加检似度统计检离散傅叶检测附录

述了这15种检测项目的原理。

4.4.2单比特频数检测

εj≤

a)0和1分1,Xj=2εj-1(1≤″

将待检序列中的别转换成-1和)。

b)对其累加求和得S″=∑饪lX氵。

c)计算统计值V=弋|。

旁

d)计算Pvalue=erFc(V/￠

D。

α

e)Pvalue≥

,则认为检列通过比频检测。

如果待序单特数

4.4.3块内频数检测

″

a将待检序歹分成N〓勿_个长度为叨的非重叠子序歹刂",将多余的比特舍弃本规范

取狃〓ˉ∞°

d蝻

∑⒐

b)1所比刀=J=1,1≤j≤N。

计算每个子序列中占的例氵

″z

o计斛量卜2。

算呓←钥

Pv·al¨=忉狃c谬

ω滩,詈

)°

GM/T0005-2012

α

e)Pvalue≥

如果,则认为待检序列通过块内频数检测。

4.4.4扑克检测

a)检列划εN=|劳狃,将犭

将待序分成长度为的非重叠子序列多余的比特舍弃,统计第种子

|个

″j(1≤f≤

序列模式出现的频数,用2″)表示。本规范取PPa=4,8。

b)计算统计值y=符亻一N°

叁

c)计算Pvalue=Fg夕彻c((2″-1)/2,V/2)。

α

d)Pvalue≥

如果,则认为待检序列通过扑克检测。

4,4.5重叠子序列检测

′

a)ε一εεaPa-1位

由待检序列构造个新的序列,构造方法如下:将序列最开始的数据添加到序

′

e的可e′,新J的″=″-1。9,,=2,5。

列结尾即得到新序列序列长度为+掘本规范取

′

b)ε一99F倥(共2″)出,记9,a位犭J″

计算中每种宁序列模式有个现的频数子序列模式1J2…的出现

频数为vi%¨计算每一种勿-1位子序列模式(共有2″1个)出现的频数,记抑-1位子序列

%°

犭J″¨°一PPn-2位(共2″2个)出

模式1F2…l的出现频数为η1氵计算每个子序列模式有现

l吃→

,记PPz-2位氵J″

的频数子序列模式lf2…2的出现频数为⒒Ⅱ

l。刃2°

c)计算

呓〓″俨~∑υ~'旦〓彳岁~∑υ~″

≡

冖

2=午″

=午

嘁→Ⅱ→·廴r仙

岁

1j闯~匕Ι→1j只/氵

嘁~=午∑〗Ⅱ~弁·∑呓Ⅱ.~″

㈠)2=罕

d)计算

v匹—Ψ

:=￠∶廴l

ˉ

v2匹2Ι

:=匹冫喙l+嘁2

e)计算P-value1=fg口PPzc(2″2,V匹御c(2″3,V2Ψ

:/2),Pvalue2=jgΩ;i/2)。

αα

f)Pvalue1≥Pvalue2≥

如果且,则认为待检序列通过重叠子序列检测。

4.4,6游程总数检测

a)″ε(o犭(犭ε

对长度为的待检列lo…V″s)=Σ)+1。,当=ε,'(J)=0;否

序%,计算冫其中氵汁1时

则,'(j)=1。

;=1ε氵

1的π

b)计算序列中比例=∑。

Pl

⊙P涮⒃

计算奶()°

α

d)Pvalue≥

如果,则认为待检序列通过游程总数检测。

4.4,7游程分布检测

a)=(″—f→3)/2i+2,1≤f≤彳5的乃

计算白,并求出满足o≥最大整数。

GM/T0005-ˉ2012

b)列ε一。