GB/T 32915-2016 PDF English

GB/T32915-2016 (GBT32915-2016): PDF in English

GB/T 32915-2016 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 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 la.......
Source: https://www.ChineseStandard.net/PDF.aspx/GBT32915-2016