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


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