logo

SCIENCE CHINA Information Sciences, Volume 62, Issue 3: 032107(2019) https://doi.org/10.1007/s11432-018-9489-x

A new discrete Fourier transform randomness test

More info
  • ReceivedMar 13, 2018
  • AcceptedJun 15, 2018
  • PublishedJan 25, 2019

Abstract

The randomness of random number generators (RNGs) is important for the reliability of cryptographic systems since the outputs of RNGs are usually utilized to construct cryptographic parameters. Statistical tests are employed to evaluate the randomness of the RNG outputs. The discrete Fourier transform (DFT) test is an important test item of the most popular statistical test suite NIST SP800-22. In the standard NIST DFT test and related improved studies, there exist accuracy and efficiency issues. First, the bit sequences generated by known good RNGs have a high probability to be rejected when the sequences are long or the sequence number is large, due to the deviation between the actual distribution of the test statistic values and the assumed normal distribution. Second, the long test time and high memory consumptions of the complex DFT test algorithm also affect its practicability. To solve these problems, we propose a new DFT test method for long sequences ($10^6$ or more bits). Different from the previous DFT test methods focusing on making the distribution of the test statistic values closer to the normal distribution, we reconstruct the statistic to follow the chi-square distribution. Our experiment result shows that our method has higher reliability in the two-level test, and could effectively reduce the test time and the memory consumptions. When applying our method on randomness test, the test efficiency has been increased to about 4 times for $10^6$-bit sequences and 7 times for $10^7$-bit sequences. In conclusion, our method has lower probability of making errors, and is more suitable for practical application scenarios.


Acknowledgment

This work was supported by National Key RD Program of China (Grant No. 2018YFB- 0904900), National Cryptography Development Fund (Grant Nos. MMJJ20170214, MMJJ20170211).


References

[1] Sowmya S, Sathyanarayana S V. Symmetric key image encryption scheme with key sequences derived from random sequence of cyclic elliptic curve points over GF(p). In: Proceedings of International Conference on Contemporary Computing and Informatics, 2015, 1345--1350. Google Scholar

[2] Sulak F, Doanaksoy A, Ege B, et al. Evaluation of randomness test results for short sequences. In: Sequences and Their Applications-SETA 2010. Berlin: Springer, 2010. Google Scholar

[3] Hellekalek P, Wegenkittl S. Empirical evidence concerning AES. ACM Trans Model Comput Simul, 2003, 13: 322-333 CrossRef Google Scholar

[4] Yin R M, Wang J, Yuan J. Weak key analysis for chaotic cipher based on randomness properties. Sci China Inf Sci, 2012, 55: 1162-1171 CrossRef Google Scholar

[5] Rukhin A, Soto J, Nechvatal J, et al. SP 800-22 Rev. 1a. A statistical test suite for random and pseudorandom number generators for cryptographic applications. Appl Phys Lett, 2010, 22: 1645--179. Google Scholar

[6] Pareschi F, Rovatti R, Setti G. On Statistical Tests for Randomness Included in the NIST SP800-22 Test Suite and Based on the Binomial Distribution. IEEE TransInformForensic Secur, 2012, 7: 491-505 CrossRef Google Scholar

[7] Pareschi F, Rovatti R, Setti G. Second-level NIST randomness tests for improving test reliability. In: Proceedings of IEEE International Symposium on Circuits and Systems, 2007. 1437--1440. Google Scholar

[8] Hamano K, Kaneko T. Correction of Overlapping Template Matching Test Included in NIST Randomness Test Suite. IEICE Trans Fundamentals Electron Commun Comput Sci, 2007, E90-A: 1788-1792 CrossRef ADS Google Scholar

[9] Hamano K. Correction of “test for the longest run of ones in a block" included in NIST randomness test suite. IEICE Tech Rep, 2007, 107: 17--21. Google Scholar

[10] Chen M, Fan L, Gao S. Corrected runs distribution test for pseudorandom number generators. Electron Lett, 2016, 52: 281-283 CrossRef Google Scholar

[11] Chen M, Chen H, Fan L. Templates selection in non-overlapping template matching test. Electron Lett, 2016, 52: 1533-1535 CrossRef Google Scholar

[12] Sys M, ?íha Z, Matyá? V. Algorithm 970. ACM Trans Math Softw, 2017, 43: 1-11 CrossRef Google Scholar

[13] Huang J L, Lai X J. Measuring random tests by conditional entropy and optimal execution order. In: Proceedings of International Conference on Trusted Systems, 2010. 148--159. Google Scholar

[14] Fan L M, Chen H, Gao S. A general method to evaluate the correlation of randomness tests. In: Proceedings of International Workshop on Information Security Applications, 2013. 52--62. Google Scholar

[15] Sulak F, U?uz M, Ko?ak O. On the independence of statistical randomness tests included in the NIST test suite. Turk J Elec Eng Comp Sci, 2017, 25: 3673-3683 CrossRef Google Scholar

[16] Pareschi F, Rovatti R, Setti G. Second-level testing revisited and applications to NIST SP800-22. In: Proceedings of the 18th European Conference on Circuit Theory and Design, 2007. 627--630. Google Scholar

[17] Zhu S Y, Ma Y, Lin J Q, et al. More powerful and reliable second-level statistical randomness tests for NIST SP 800-22. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, 2016. Google Scholar

[18] Hamano K, Satoh F, Ishikawa M. Randomness Test Using Discrete Fourier Transform. Technical Report 6841, 2003. Google Scholar

[19] Hamano K. The Distribution of the Spectrum for the Discrete Fourier Transform Test Included in SP800-22. IEICE Trans Fundamentals Electron Commun Comput Sci, 2005, E88-A: 67-73 CrossRef ADS Google Scholar

[20] Kim S J, Umeno K, Hasegawa A. Corrections of the NIST statistical test suite for randomness. 2004. https://eprint.iacr.org/2004/018.pdf. Google Scholar

[21] Daemen J, Rijmen V. The Design of Rijndael: AES -- the Advanced Encryption Standard. Berlin: Springer, 2002. Google Scholar

[22] U.S. Department of Commerce. Secure Hash Standard - SHS: Federal Information Processing Standards Publication 180-4. Charlestone: CreateSpace Independent Publishing Platform, 2012. Google Scholar

  • Figure 1

    (Color online) Comparisons of theoretical and experimental distribution. (a) Probability distribution of normal distribution; (b) experimental probability distribution of ${N_1}$.

  • Figure 2

    (Color online) Comparisons of probability in each sub-interval ($K=10$, $n=10^6$).

  • Table 1   The upper threshold values of sequence number
    Length Passing proportion testUniformity test
    DFT ($c=4$) DFT ($c=3.8$) DFT ($c=4$) DFT ($c=3.8$)
    10000000 123126228 2878 4134
    1000000 58499 345191
    10000032 13 2535
    1000023 2.47 2.84
    10000.160.15 0.260.26
  •   

    Algorithm 1 The new DFT test procedure for long sequences

    Require:A binary sequence $\varepsilon$; the length of the input sequence $n$; the length of a sub-sequence $m$, $m~\in~\{~1000,10000,$ $100000\}$; $K+1$ specific ratio intervals of ${N_{i1}}/m$ for different subsequence lengths; the expected probabilities of each interval, ${\pi~_r}$, $0~\le~r~\le~K$.

    Output: P-value, $p$.

    $M=n/m$;

    if $M~<~200$ then

    return The choice value of $m$ is too big;

    else

    Let ${S_i}$ be the $i$-th subsequence, $0~\le~i~\le~M~-~1$ and ${s_{ij}}$ is the $j$-th bit of the subsequence ${S_i}$, $0~\le~j~\le~m~-~1$;

    for $i=0$ to $M-1$

    for $j=0$ to $m-1$

    ${z_{ij}}~=~2{s_{ij}}~-~1$;

    Apply the discrete Fourier transform on ${z_{ij}}$, ${\rm~i}~\equiv~\sqrt~{~-~1}~$;

    ${f_{ij}}~=~\sum\nolimits_{t~=~1}^m~{{z_{it}}{{\rm~e}^{2\pi~{\rm~i}(t~-~1)j/m}}}$;

    end for

    for $j=0$ to $m/2-1$

    Compute the modulus of ${f_{ij}}$;

    end for

    ${T_h}~=~\sqrt~{(\log~\frac{1}{{0.05}})m}~$;

    Let ${N_{i1}}$ be the number of $|~{{f_{ij}}}~|$ less than ${T_h}$;

    end for

    for $r=0$ to $M-1$

    Count the number of ${N_{i1}}/m$ belonging to the $r$-th interval, ${v_r}$;

    end for

    Compute a test statistic: ${X^2}~=~\sum\nolimits_{r~=~0}^K~{\frac{{{{({v_r}~-~M{\pi~_r})}^2}}}{{M{\pi~_r}}}}$;

    Compute the P-value: $p~=~{\rm~igamc}(\frac{K}{2},\frac{{{X^2}({\rm~obs})}}{2})$;

    return $p$;

    end if

  • Table 2   The expected proportions in each intervals for sequences of different lengths
    Sub-sequence length $m$ Interval Probability ${\pi~_r}$
    [0,~0.468] 0.034601
    [0.469,~0.471] 0.126173
    [0.472,~0.474] 0.278188
    1000 0.475 0.112357
    [0.476,~0.478] 0.287042
    [0.479,~0.481] 0.130616
    [0.482,~0.5] 0.031023
    [0,~0.4728] 0.027910
    [0.4729,~0.4739] 0.145946
    [0.4740,~0.4749] 0.306825
    10000 0.4750 0.035620
    [0.4751,~0.4760] 0.309415
    [0.4761,~0.4771] 0.147452
    [0.4772,~0.5] 0.026832
    [0,~0.47432] 0.028502
    [0.47433,~0.47465] 0.136399
    [0.47466,~0.47497] 0.306491
    100000 [0.47498,~0.47502] 0.056363
    [0.47503,~0.47534] 0.307504
    [0.47535,~0.47567] 0.136647
    [0.47568,~0.5] 0.028094
  • Table 3   Symbols of new DFT test
    Symbol Description
    $n$ The test sequence length, $n~\ge~10^6$
    $N$ The test sequence number
    $m$The sub-sequence length, $m~\in~\{~1000,10000,100000\}$
    $M$The sub-sequence number, $M~\ge~200$
    ${S_i}$The $i$-th subsequence, $0~\le~i~\le~M~-~1$
    ${s_{ij}}$The $j$-th bit of the subsequence ${S_i}$, $0~\le~j~\le~m~-~1$
    ${f_{i}}$The complex sequence after applying the discrete Fourier transform on ${S_i}$
    ${f_{ij}}$The $j$-th bit of sequence ${f_{i}}$
    ${N_{i1}}$The number of $|~{{f_{ij}}}~|$ less than ${T_h}$
    ${v_r}$The number of ${N_{i1}}/m$ belonging to the $i$-th interval
    ${\pi~_r}$The expected probability of each interval for different subsequence lengths
  • Table 4   Detail information of sequences
    PRNG Length Number
    AES-256 1000000 100000
    10000000 30000
    SHA-512 1000000 100000
    10000000 30000
  • Table 5   Comparisons of passing proportion
    Sequence length Number Lower limit PRNGDFT test Passing ratio
    1000000100000 0.98906 NIST ($c=4$) [5] 0.98790
    AES-256 NIST ($c=3.8$) [6] 0.99010
    Ours ($m=1000$) 0.98990
    NIST ($c=4$) [5] 0.98810
    SHA-512NIST ($c=3.8$) [6] 0.98990
    Ours ($m=1000$) 0.98997
    10000000 30000 0.98828 NIST ($c=4$)[5] 0.98760
    AES-256NIST ($c=3.8$) [6] 0.99000
    Ours ($m=1000$) 0.99010
    Ours ($m=10000$) 0.98960
    SHA-512 NIST ($c=4$)[5] 0.98863
    NIST ($c=3.8$) [6] 0.99050
    Ours ($m=1000$) 0.98990
    Ours ($m=10000$) 0.98950
  • Table 6   Comparisons of uniformity ($n=10^6,~N=10^5$)
    PRNGDFT test P/Q P-value ${p_T}$
    AES-256 NIST ($c=4$) [5] P-value 0.000000
    Q-value [17] 0.000000
    NIST ($c=3.8$) [6] P-value 0.000000
    Q-value [17]0.012646
    Ours ($m=1000$)0.659908
    SHA-512 NIST ($c=4$) [5] P-value 0.000000
    Q-value [17] 0.000000
    NIST ($c=3.8$) [6] P-value 0.000000
    Q-value [17] 0.043125
    Ours ($m=1000$)0.250616
  • Table 7   Comparisons to detect type II errors for periodic sequences
    Sequence length Sequence periodSequence number Lower limit DFT test methodPassing ratio
    NIST ($c=4$)0.00000
    100000010000010000.98056NIST ($c=3.8$)0.00000
    Ours ($m=1000$)0.00000
  • Table 8   Comparisons to detect type II errors for linear congruence generator rand()
    Sequence length Sequence number Lower limitDFT test methodPassing ratio
    NIST ($c=4$)0.00000
    100000010000.98056NIST ($c=3.8$)0.00000
    Ours ($m=1000$)0.00000
  • Table 9   Comparisons to detect type II errors for inappropriate AES encryption
    Sequence length Sequence number Lower limitDFT test methodPassing ratio
    NIST ($c=4$)0.86600
    100000010000.98056NIST ($c=3.8$)0.86800
    Ours ($m=1000$)0.85900
  • Table 10   Comparisons of test time
    Sequence length DFT test Test time (s)
    1000000 NIST SP800-22 [5] 1.95
    Ours ($m=1000$) 0.48
    NIST SP800-22[5] 16.88
    10000000 Ours ($m=1000$) 2.278
    Ours ($m=10000$) 2.424
  • Table 11   Experiment results for long sequences
    PRNG Sequence length Number Lower limit$m$ Passing ratio P-value ${p_T}$ Test time (s)
    AES-2561000 0.99400 0.026948 20.14
    100000000 1000 0.98056100000.98900 0.841226 22.515
    1000000.98800 0.189625 25.74
    10000.98500 0.176657 230.7
    1000000000200 0.96889 100000.99000 0.554420 234.4
    100000 0.98000 0.911413271.5
    SHA-5121000 0.99200 0.191687 20.14
    100000000 1000 0.98056 10000 0.98200 0.686955 22.515
    100000 0.98900 0.340858 25.74
    1000 0.98500 0.605916230.7
    1000000000 200 0.96889 10000 0.99500 0.025193 234.4
    1000000.99000 0.930026 271.5

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1