MODIFICATIONS OF KNUTH RANDOMNESS TESTS FOR INTEGER AND BINARY SEQUENCES

Abstract

Generating random numbers and random sequences that are indistinguishable from truly random sequences is an important task for cryptography. To measure the randomness, statistical randomness tests are applied tothe generated numbers and sequences. Knuth test suite is the one of the …rststatistical randomness suites. This suite, however, is mostly for real numbersequences and the parameters of the tests are not given explicitly.In this work, we review the tests in Knuth Test Suite. We give test parameters in order for the tests to be applicable to integer and binary sequencesand make suggestions on the choice of these parameters. We clarify how theprobabilities used in the tests are calculated according to the parameters andprovide formulas to calculate the probabilities.Also, some tests, like Permutation Test and Max-of-t-test, are modi…ed so that the test can be usedto test integer sequences. Finally, we apply the suite on some widely usedcryptographic random number sources and present the results

Keywords

• Knuth test suite, Statistical randomness testing

References

1. P. K. A. Freier, P. Kocher, The secure sockets layer (ssl) protocol version 3.0 (2011). doi: 10.17487/RFC6101. URL
2. Intel Corporation, Intel Digital Random Number Generator (DRNG): Software Implementa- tion Guide, Revision 1.1 (2012).
3. Comscire quantum number generators. URL http://comscire.com/cart/
4. M. Matsumoto, T. Nishimura, Mersenne twister: A 623-dimensionally equidistributed uni- form pseudo-random number generator, ACM Trans. Model. Comput. Simul. 8 (1) (1998) 3–30. doi:10.1145/272991.272995. URL http://doi.acm.org/10.1145/272991.272995
5. L. Blum, M. Blum, M. Shub, A simple unpredictable pseudo random number generator, SIAM J. Comput. 15 (2) (1986) 364–383. doi:10.1137/0215025. URL http://dx.doi.org/10.1137/0215025
6. A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, S. Leigh, M. Levenson, M. Vangel, D. Banks, A. Heckert, J. Dray, S. Vo, A statistical test suite for random and pseudorandom number generators for cryptographic applications, Tech. rep., NIST (2001). URL http://www.nist.gov
7. D. E. Knuth, The Art of Computer Programming, Volume 2 (3rd Ed.): Seminumerical Al- gorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1997.
8. G. Marsaglia, The Marsaglia random number CDROM including the DIEHARD battery of tests of randomness (1996). URL http://stat.fsu.edu/pub/diehard

9. R. G. Brown, Dieharder: A random number test suite (2013). URL http://www.phy.duke.edu/~rgb/General/dieharder.php
10. P. L’Ecuyer, R. Simard, Testu01: A c library for empirical testing of random number genera
11. tors, ACM Trans. Math. Softw. 33 (4) (2007) 22. doi:http://doi.acm.org/10.1145/1268776. 1268777.
12. Q. H. Dang, Fips 180-4, secure hash standard, Tech. rep., NIST (2012).
13. E-mail address : [e-mail]
14. ORCID: http://orcid.org/0000-0003-2344-503X