Skip to product information
1 of 12

PayPal, credit cards. Download editable-PDF and invoice in 1 second!

GB/T 32915-2016 English PDF (GBT32915-2016)

GB/T 32915-2016 English PDF (GBT32915-2016)

Regular price $145.00 USD
Regular price Sale price $145.00 USD
Sale Sold out
Shipping calculated at checkout.
Quotation: In 1-minute, 24-hr self-service. Click here GB/T 32915-2016 to get it for Purchase Approval, Bank TT...

GB/T 32915-2016: Information security technology -- Randomness test methods for binary sequence

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.
GB/T 32915-2016
GB
NATIONAL STANDARD OF THE
PEOPLE 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 self-sequence 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 L-bit 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 L-bit non-overlapping subsequences. The test sequence consists of K L-bit non-overlapping
subsequences, discard the extra bits (not enough to form a complete L-bit subsequence), .
Step 2. For the initial sequence, create a table with the L-bit 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 L-bit subsequence in the initial sequence.
Appendix A
(Informative)
Random test principle
A.1 Single bit frequency test
Single-bit 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 Intra-block frequency test
The intra-block 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 m-bit subsequence of any length shall be close to m/2.
The intra-block 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 non-superimposed
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 equal-length 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 m-bit 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 m-bit 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 Berlekamp-Massey 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 non-random 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 L-bit 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 L-bit mode last appears in the initial sequence. If an L-bit 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 L-bit 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.

View full details