GB/T 329152016 PDF in English
GB/T 329152016 (GB/T329152016, GBT 329152016, GBT329152016)
Standard ID  Contents [version]  USD  STEP2  [PDF] delivered in  Name of Chinese Standard  Status 
GB/T 329152016  English  150 
Add to Cart

09 seconds. Autodelivery.

Information security technology  Randomness test methods for binary sequence
 Valid 
Standards related to (historical): GB/T 329152016
PDF Preview
GB/T 329152016: PDF in English (GBT 329152016) GB/T 329152016
GB
NATIONAL STANDARD OF THE
PEOPLE’S REPUBLIC OF CHINA
ICS 35.040
L 80
Information security technology 
Randomness test methods for binary sequence
ISSUED ON. AUGUST 29, 2016
IMPLEMENTED ON. MARCH 01, 2017
Issued by. General Administration of Quality Supervision Inspection and
Quarantine of PRC;
Standardization Administration of PRC.
Table of Contents
Foreword ... 5
1 Scope ... 6
2 Terms and definitions ... 6
3 Symbol ... 7
4 Randomness test ... 9
4.1 Single bit frequency test method ... 9
4.1.1 Overview ... 9
4.1.2 Test procedures ... 9
4.1.3 Result determination ... 10
4.2 Block internal frequency test method ... 10
4.2.1 Overview ... 10
4.2.2 Test procedures ... 10
4.2.3 Result determination ... 10
4.3 Poker test method ... 11
4.3.1 Overview ... 11
4.3.2 Test procedures ... 11
4.3.3 Result determination ... 11
4.4 Overlapping subsequence test method ... 11
4.4.1 Overview ... 11
4.4.2 Test procedures ... 12
4.4.3 Result determination ... 12
4.5 Total run number test method ... 13
4.5.1 Overview ... 13
4.5.2 Test procedures ... 13
4.5.3 Result determination ... 13
4.6 Run distribution test method ... 13
4.6.1 Overview ... 13
4.6.2 Test procedures ... 14
4.6.3 Result determination ... 14
4.7 Maximum “1” run test method in block ... 14
4.7.1 Overview ... 14
4.7.2 Test procedures ... 14
4.7.3 Result determination ... 15
4.8 Binary derivation test method ... 15
4.8.1 Overview ... 15
4.8.2 Test procedures ... 15
4.8.3 Result determination ... 16
4.9 Autocorrelation test method... 16
4.9.1 Overview ... 16
4.9.2 Test procedures ... 16
4.9.3 Result determination ... 17
4.10 Matrix rank test method ... 17
4.10.1 Overview ... 17
4.10.2 Test procedures ... 17
4.10.3 Result determination ... 18
4.11 Cumulative sum test methods ... 18
4.11.1 Overview ... 18
4.11.2 Test procedures ... 18
4.11.3 Result determination ... 18
4.12 Approximate entropy test method ... 19
4.12.1 Overview ... 19
4.12.2 Test procedures ... 19
4.12.3 Result determination ... 20
4.13 Linear complexity test method ... 20
4.13.1 Overview ... 20
4.13.2 Test procedures ... 20
4.13.3 Result determination ... 21
4.14 Maurer universal statistical test method ... 21
4.14.1 Overview ... 21
4.14.2 Test procedures ... 21
4.14.3 Result determination ... 22
4.15 Discrete Fourier test method ... 22
4.15.1 Overview ... 22
4.15.2 Test procedures ... 22
4.15.3 Result determination ... 23
5 Random number generator test ... 23
5.1 Overview of random number generator test ... 23
5.2 Collection ... 23
5.3 Testing ... 23
5.4 Judgment ... 24
Appendix A (Informative) Random test principle ... 25
Appendix B (Informative) Randomness test parameter setting table ... 35
Information security technology 
Randomness test methods for binary sequence
1 Scope
This standard specifies the randomness test indicators and test methods in
commercial password applications.
This standard applies to the randomness test of binary sequences generated
by random number generators.
2 Terms and definitions
The following terms and definitions apply to this document.
2.1
Binary sequence
A bit string consisting of “0” and “1”.
2.2
Random number generator
A device or program that produces a random binary sequence.
2.3
Randomness hypothesis
When performing randomness test on a binary sequence, first assume that
the sequence is random. This assumption is called the original hypothesis
or null hypothesis and is recorded as H0. The hypothesis opposite to the null
hypothesis, that this sequence is not random, is called the alternative
hypothesis, which is denoted as Hα.
2.4
Randomness test
A function or process used for binary sequence test to determine whether to
accept the randomness null hypothesis.
2.5
Significance level
The probability of erroneously determining a random sequence as a non
random sequence in randomness test, which is represented by α.
2.6
Sample
A binary sequence for randomness test, which is called a sample.
2.7
Sample length
The number of bits in a sample.
2.8
Sample size
The number of samples that are randomly tested.
2.9
Test parameter
Parameters that are required to be set for randomness test.
2.10
Run
A selfsequence consisting of consecutive “0” or “1” in a sequence, and the
preamble and successor elements of the subsequence are different from
their own elements.
3 Symbol
The following symbols apply to this document.
α. Significance level
H0. Original hypothesis (null hypothesis)
Hα. Alternative hypothesis
ε. Sequence to be tested
n. Bit length of the sequence to be tested
εi. A bit in the sequence to be tested, εi = (0, 1)
ε'. A new sequence generated in accordance with certain rules on the basis of
Xi. 2εi  1
m. Bit length of the subsequence
Σ. AND symbols
*. Multiplication, sometimes omitted
ln(x). Natural logarithm of x
Log2(x). Logarithm of x with base 2
. The largest integer not greater than x
max. Taking the maximum value from several elements
Φ(x). Standard normal distribution function
V. Statistic value
P_value. Complementary error function
erfc. A measure of the quality of the sample randomness.
igamc. Incomplete gamma function
π. The ratio of 1 in the sequence to be tested
Vn(obs). Total number of runs in the sequence to be tested
ApEn(m). Approximate entropy of sequence to be tested
K. Number of Lbit subsequences in the sequence to be tested in universal
statistical test
L. Length of subsequence in general statistics
Li. Linear complexity of subsequences in linear complexity test
M. Number of matrixes in matrix rank test
1.5 < Ti ≤ 2.5, v5 plus 1;
Ti > 2.5, v6 plus 1.
Step 6. Calculate the statistical value . Where πi values
are. π0 = 0.010417, π1 = 0.03125, π2 = 0.12500, π3 = 0.5000, π4 = 0.25000, π5
= 0.06250, π6 = 0.020833.
Step 7. Calculate
4.13.3 Result determination
The P_value result calculated in 4.13.2 is compared to the significance level α.
If P_value ≥ α, the sequence to be tested is deemed to pass the linear
complexity test.
4.14 Maurer universal statistical test method
4.14.1 Overview
The Maurer universal statistical test is used to test whether the sequence to be
tested can be losslessly compressed. Since a random sequence cannot be
significantly compressed, if the sequence to be tested can be significantly
compressed, the sequence is deemed not to be random.
4.14.2 Test procedures
The Maurer universal statistical test procedures are as follows.
Step 1. Divide the sequence ε to be tested into two parts. the initial sequence
and the test sequence. The initial sequence consists of Q Lbit nonoverlapping
subsequences. The test sequence consists of K Lbit nonoverlapping
subsequences, discard the extra bits (not enough to form a complete Lbit
subsequence), .
Step 2. For the initial sequence, create a table with the Lbit value as the index
value in the table, Tj (1 ≤ j ≤ 2L) represents the value of the jth element in the
table, calculate Tj = i(1 ≤ i ≤ Q), where j is the decimal representation of the ith
Lbit subsequence in the initial sequence.
Appendix A
(Informative)
Random test principle
A.1 Single bit frequency test
Singlebit frequency test is the most basic test used to test whether the number
of 0 and 1 in a binary sequence are similar. That is, if a binary sequence of
length n is known, it tests whether the sequence has a good 0, 1 balance. Let
n0, n1 denote the number of 0 and 1 in the sequence, respectively. For a random
sequence, when its length is sufficiently large, its statistical value V shall obey
the standard normal distribution.
A.2 Intrablock frequency test
The intrablock frequency test is used to test whether the number of 1 in the m
bit subsequence of the sequence to be tested is close to m/2. For a random
sequence, the number of 1 in an mbit subsequence of any length shall be close
to m/2.
The intrablock frequency test divides the sequence to be tested into N
subsequences, each of which has a length of m and n = N × m. Of course, if n
cannot be divisible by m, there will be extra bits, and the extra bits will be
discarded at this time. Calculate the ratio of 1 in each subsequence, set it to
, 1 ≤ i ≤ N . The cumulative sum of the ratios of 1 of all N
subsequences is taken as a statistical value.
This statistic shall obey the χ2 distribution with a degree of freedom of N.
A.3 Poker test
For any positive integer m, the binary sequence of length m has 2m types. The
sequence to be tested is divided into nonsuperimposed
the sequence to be tested obeys the randomness requirement.
Let Vn(obs) denote the total number of runs of the sequence to be tested, π
denotes the proportion of 1 in the sequence, and Φ(z) is the standard normal
distribution, then.
obeys the standard normal distribution.
A.6 Run distribution test
A run of consecutive 1 (or 0) is called a block (or a discontinuity). If the binary
sequence to be tested is random, the number of runs of the same length is
nearly identical. The expected value of the number of runs of length i in a
random binary sequence of length n is . Let k be the largest
integer that satisfies ei ≥ 5. Let bi, gi denote the number of “1” runs and “0” runs
of length i in a binary sequence, respectively, for each i, 1 ≤ i ≤ k. The statistical
value V approximately obeys the χ2 distribution with a degree of freedom of 2k
 2.
A.7 Maximum “1” run test in the block
The sequence to be tested is divided into N equallength subsequences, and
the randomness of the sequence to be tested is evaluated in accordance with
the distribution of the largest 1 run in each subsequence.
The sequence to be tested is divided into N subsequences of length m, where
n = N × m. In accordance with the size of m, corresponding to (K + 1) sets
(related to the size of m), then calculate the length of the largest “1” run of each
subsequence and classify it into the corresponding set. Let the number of
elements in the (K + 1) sets be v0, v1, v2, ..., vk (v0 + v1 + v2 +...+ vk = N), and
the statistical value V shall obey the χ2 distribution with a degree of freedom K.
The values of K and πi are related to m. Table A.1, Table A.2 and Table A.3
respectively show the corresponding K value, vi definition and πi value when m
takes 8, 128 and 10000 respectively.
πl represents the relative frequency of the mode l = (i1, i2, ..., im) appearing in
the sequence to be tested;
φ(m) represents the entropy of the relative frequency distribution of all 2m mbit
subsequence modes.
The approximate entropy ApEn(m) is defined as. ApEn(m) = φ(m)  φ(m +1), where
ApEn(0) = φ(1).
The approximate entropy gives the difference between the frequency between
the mbit overlappable subsequence mode and the (m + 1)bit overlappable
subsequence mode when the subsequence length m is increased by one.
Therefore, a small ApEn(m) value indicates that the sequence to be tested is
regular and continuous; and a large ApEn(m) value indicates that the sequence
to be tested is irregular and discontinuous.
For any m, the approximate entropy of the random sequence (irregular
sequence) ApEn(m) shall be approximately equal to ln2. Therefore, the
statistical value V = 2n[ln2  ApEn(m)] shall obey the χ2 distribution with a
degree of freedom of 2m.
A.13 Linear complexity test
The sequence to be tested is divided into N subsequences of length M, where
n = N × M, then the linear complexity Li of each subsequence is calculated by
the BerlekampMassey algorithm, and Ti = (1)M (Li  μ) + 2/9, where μ = M/2 +
[9 + (1) M+1]/36  1/2M (M/3 + 2/9).
Select (K + 1) disjoint independent sets, then classify the TM of each
subsequence in accordance with the set, count the number of TM appearing in
each set, which are respectively recorded as v0, v1, ..., vK, obviously v0 + v1 + ...
+ vK =N.
Statistical value shall obey the χ2 distribution with a
degree of freedom of K.
This standard selects K = 6, set 7 positive integers v0, v1, ..., v6, set the initial
values of these 7 positive integers to 0, for all i ∈ [1, N].
If. Ti ≤ 2.5, v0 plus 1;
2.5 < Ti ≤ 1.5, v1 plus 1;
1.5 < Ti ≤ 0.5, v2 plus 1;
0.5 < Ti ≤ 0.5, v3 plus 1;
0.5 < Ti ≤ 1.5, v4 plus 1;
1.5 < Ti ≤ 2.5, v5 plus 1;
T > 2.5, v6 plus 1.
Wherein, the corresponding πi values are. π0 = 0.010417, π1 = 0.03125, π2 =
0.12500, π3 = 0.5000, π4 = 0.25000, π5 = 0.06250, π6 = 0.020833.
A.14 Maurer universal statistical test
Maurer general statistics (referred to as general statistics) test mainly tests
whether the sequence to be tested can be losslessly compressed. If the
sequence to be tested can be significantly compressed, the sequence is
considered to be nonrandom because the random sequence cannot be
significantly compressed.
Universal statistical testing can be used to test various aspects of the sequence
to be tested, but this does not mean that the universal statistical test is the
assembly of the previous tests, but the universal statistical test completely
adopts a different method from other tests. A sequence can be tested by
universal statistical test if and only if the sequence is incompressible. The
purpose of universal statistical testing is to test any statistical defects in the
sequence to be tested.
The universal statistical test requires a large amount of data, which divides the
sequence into subsequences of length L, then divides the sequence to be
tested into two parts. initial sequence and test sequence. The initial sequence
includes Q subsequences, Q shall be greater than or equal to 10 × 2L; the test
sequence includes K subsequences, K shall be greater than or equal to 1000
× 2L. Therefore, the sequence length n shall be 10 x 2L + 1000 x 2L, and L shall
be in the range of 1 ≤ L ≤ 16, it is recommended that L take a value not less
than 6. Obviously, when L = 6, there is n = 387840. When the sequence length
n is constant, it should select , Q shall ensure that all 2L modes of
the Lbit subsequence appear at least once in the initial sequence.
First, traverse the initial sequence (in the unit of blocks) from the beginning, find
the position (block number) where each Lbit mode last appears in the initial
sequence. If an Lbit mode does not appear in the initial sequence, set its
position to 0; thereafter, traversing the test sequence from the beginning, each
time will get an Lbit subsequence, calculate the position of the subsequence
and the position difference of the last occurrence of the subsequence, that is,
the block number is subtracted, and the result of the subtraction is the distance.
Then calculate the base 2 logarithm of the distance; finally, add all the results
of the logarithm. In this way, it can get the statistical value.
...... Source: Above contents are excerpted from the PDF  translated/reviewed by: www.chinesestandard.net / Wayne Zheng et al.
