Standards related to:

GM/T 0005-2012GM/T 0005-2012

GM

CRYPTOGRAPHY INDUSTRY STANDARD

OF THE PEOPLE’S REPUBLIC OF CHINA

ICS 35.040

L 80

RECORD NO.. 36832-2012

Randomness test specification

ISSUED ON. MARCH 21, 2012

IMPLEMENTED ON. MARCH 21, 2012

Issued by. State Cryptography Administration

Table of Contents

Foreword ... 3

1 Scope .. 4

2 Terms and conventions ... 4

3 Symbols and abbreviations ... 8

4 Binary sequence test .. 9

5 Test for random number generator ... 17

Annex A (Informative) Principle for randomness test ... 19

Annex B (Informative) Table of randomness test parameters ... 29

Annex C (Informative) Analytical table of randomness test results .. 30

Foreword

This Standard was drafted in accordance with the rules given in GB/T 1.1-2009.

This Standard is a standard for randomness test and provides scientific basis

for randomness assessment.

Attention is drawn to the possibility that some of the elements of this document

may be the subject of patent rights. The issuer of this document shall not be

held responsible for identifying any or all such patent rights.

Annex A, Annex B and Annex C to this Standard are informative.

This Standard was proposed by and shall be under the jurisdiction of the State

Cryptography Administration of the People’s Republic of China.

The drafting organizations of this Standard. State Cryptography Administration

Commercial Cryptography Testing Center, Institute of Software Chinese

Academy of Sciences.

The main drafters of this Standard. Li Dawei, Feng Dengguo, Chen Hua, Zhang

Chao, Zhou Yongbin, Dong Fang, Fan Limin, Xu Nannan.

Randomness test specification

1 Scope

This Standard specifies the randomness test parameters and test methods in

the commercial cryptography application.

This Standard applies to the randomness test for binary sequence which is

generated by random number generator.

2 Terms and conventions

For the purposes of this document, the following terms and definitions apply.

2.1

binary sequence

Bit string which comprises “0” and “1”.

2.2

random number generator

Random number generator refers to a device or program which generates

random sequences.

2.3

randomness hypothesis

For the randomness test of binary sequence, first make a hypothesis that the

sequence is random, which is called original hypothesis or null hypothesis,

denoted as H0. Alternative hypothesis refers to the hypothesis which is contrary

to original hypothesis, i.e. this sequence is not random, denoted as Hα.

2.4

randomness test

A function or process for binary sequence test, through which it is determined

whether the original hypothesis of randomness is acceptable.

2.5

2.13

frequency test within a block

A statistical test item which is used to test whether the number of ones in the

m-bit subsequences (namely “blocks”) of sequence to be tested is close to m/2.

2.14

poker test

A statistical test item which is used to test whether the number of all modes of

the m-bit non-overlap subsequences in sequence to be tested are close.

2.15

serial test

A statistical test item which is used to test whether the numbers of all modes of

the m-bit overlapping subsequences in sequence to be tested are close.

2.16

runs test

A statistical test item which is used to test whether the total number of runs of

sequence to be tested complies with the randomness requirements.

2.17

runs distribution test

A statistical test item which is used to test whether the numbers of equal-length

runs of sequence to be tested are close to identical.

2.18

test for the longest run of ones in a block

A statistical test item which is used to test whether the distribution of the

maximum “1” runs of all equal-length subsequences of subsequences to be

tested comply with the randomness requirements.

2.19

binary derivative test

A statistical test item. Binary derivative sequence is a new sequence which is

generated by an original sequence; and it is the result which is obtained from

the exclusive-OR operation of two adjacent bits of the original sequence in turn.

The object of binary derivative test is to determine whether the numbers of 0

and 1 in the k-th binary derivative sequence are close to identical.

2.20

autocorrelation test

A statistical test item which is used to test the correlation degree between a

sequence to be tested and a new sequence which is obtained after logic shit of

it by d bits.

2.21

binary matrix rank test

A statistical test item which is used to test the linear independence between

given-length subsequences of sequences to be tested.

2.22

cumulative test

A statistical test item which is used to determine whether the maximum

deviation of a sequence to be tested is too large or too small, by comparing the

maximum deviation of all subsequences of sequence to be tested (here, it

refers to the maximum deviation from 0, i.e. the maximum cumulative sum) and

the maximum deviation of a random sequence.

2.23

approximate entropy test

A statistical test item which is used to determine the randomness by comparing

the frequency of the m-th bit overlapping sequence mode and the frequency of

the m + 1-bit overlapping subsequence mode.

2.24

linear complexity test

A statistical test item which is used to determine whether the distribution of

linear complexities of a sequence to be test comply with the randomness

requirements.

2.25

Maurer’s “Universal Test”

b) Calculate the length of the longest run of ones in each subsequence and

include them into a corresponding set {v0, v1, ., v6}.

c) Calculate the statistical value . See Annex A.7 for the

definitions of vi and πi.

d) Calculate .

e) If P-value ≥ α, then the sequence to be tested passes the test for the

longest run of ones in a block.

4.4.9 Binary derivative test

a) For the sequence to be tested ε, conduct exclusive-OR operation of two

adjacent bits in the original sequence to obtain a new sequence ε’, i.e.

b) Repeat operation a) for k times. k = 3,7 in this Specification.

c) Convert the 0 and 1 in the new sequence ε’ respectively into -1 and 1 and

then do cumulative summation to obtain .

d) Calculate the statistical value .

e) Calculate .

f) If P-value ≥ α, then the sequence to be tested passes the binary derivative

test.

4.4.10 Autocorrelation test

a) Calculate . d = 1, 2, 8, 16 in this Specification.

b) Calculate the statistical value .

c) Calculate .

d) If P-value ≥ α, then the sequence to be tested passes the autocorrelation

test.

Annex A

(Informative)

Principle for randomness test

A.1 Monobit frequency test

The monobit frequency test is a most basic test which is used to test whether

the numbers of zeros and ones in a binary sequence are close, i.e. if a binary

sequence of length n is known, it is tested whether the sequence has good

balance of zeros and ones. Let n0 and n1 denote the numbers of zeros and ones

in the sequence. For a random sequence, when its length is sufficiently large,

its statistical value V shall be of standard normal distribution.

A.2 Frequency test within a block

The frequency test within a block is used to test whether the number of ones in

the m-bit subsequences of the sequence to be tested is close to m/2. For a

random sequence, the number of ones in the m-bit subsequences of any length

shall be close to m/2.

In the frequency test within a block, the sequence to be tested is divided into N

subsequences, the length of each subsequence m, n = N * m. Certainly, if n

can’t be divided exactly by m, there will definitely be redundant bits, and then

the abundant bits shall be abandoned. Calculate the proportion of ones in each

subsequence, and set πi = . Let the cumulative sum of the

proportions of ones in all N subsequences as the statistical value, and then.

The statistical value shall follow the x2 distribution with degree of freedom N.

A.3 Poker test

For any positive integer m, there are 2m binary sequences of length m. Divide

the sequence to be tested into non-overlapping subsequences of

length m; and use ni (1 ≤ i ≤ 2m) to represent the number of the i-th subsequence

Annex C

(Informative)

Analytical table of randomness test results

Table C.1

S.N. Test item Principle Parameter requirement Fail analysis

Monobit frequency

test

Test whether the numbers of zeros and ones

in the sequence to be tested are close

n >100

Indicate the number of

zeros or ones is too

small

Frequency test

within a block

whether the number of ones in the m-bit

subsequences is close to m/2

n ≥ 100, m ≥ 20

The proportion of zeros

and ones in the m-bit

subsequences is

unbalanced

3 Poker test

The 2m kinds of subsequences of length m.

Use the length to divide the sequence to be

tested and test whether the numbers of

...

...