On the independence of statistical randomness tests included in the NIST test suite

Date

2017-01-01

Author

SULAK, FATİH
Uğuz, Muhiddin
Koçak, Onur Ozan
Doğanaksoy, Ali

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

337
views

0
downloads

Random numbers and random sequences are used to produce vital parts of cryptographic algorithms such as encryption keys and therefore the generation and evaluation of random sequences in terms of randomness are vital. Test suites consisting of a number of statistical randomness tests are used to detect the nonrandom characteristics of the sequences. Construction of a test suite is not an easy task. On one hand, the coverage of a suite should be wide; that is, it should compare the sequence under consideration from many different points of view with true random sequences. On the other hand, an overpopulated suite is expensive in terms of running time and computing power. Unfortunately, this trade-off is not addressed in detail in most of the suites in use. An efficient suite should avoid use of similar tests, while still containing sufficiently many. A single statistical test gives a measure for the randomness of the data. A collection of tests in a suite give a collection of measures. Obtaining a single value from this collection of measures is a difficult task and so far there is no conventional or strongly recommended method for this purpose. This work focuses on the evaluation of the randomness of data to give a unified result that considers all statistical information obtained from different tests in the suite. A natural starting point of research in this direction is to investigate correlations between test results and to study the independences of each from others. It is started with the concept of independence. As it is complicated enough to work even with one test function, theoretical investigation of dependence between many of them in terms of conditional probabilities is a much more difficult task. With this motivation, in this work it is tried to get some experimental results that may lead to theoretical results in future works. As experimental results may reflect properties of the data set under consideration, work is done on various types of large data sets hoping to get results that give clues about the theoretical results. For a collection of statistical randomness tests, the tests in the NIST test suite are considered. Tests in the NIST suite that can be applied to sequences shorter than 38,912 bits are analyzed. Based on the correlation of the tests at extreme values, the dependencies of the tests are found. Depending on the coverage of a test suite, a new concept, the coverage efficiency of a test suite, is defined, and using this concept, the most efficient, the least efficient, and the optimal subsuites of the NIST suite are determined. Moreover, the marginal benefit of each test, which also helps one to understand the contribution of each individual test to the coverage efficiency of the NIST suite, is found. Furthermore, an efficient subsuite that contains five statistical randomness tests is proposed.

Subject Keywords

Cryptography, Random sequences, Statistical randomness tests, NIST test suite, Coverage, Independence, Correlation

URI

https://hdl.handle.net/11511/35532

Journal

TURKISH JOURNAL OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCES

DOI

https://doi.org/10.3906/elk-1605-212

Collections

Department of Mathematics, Article

Suggestions

OpenMETU
Core

MODIFICATIONS OF KNUTH RANDOMNESS TESTS FOR INTEGER AND BINARY SEQUENCES Koçak, Onur Ozan; SULAK, FATİH; Doğanaksoy, Ali; Uğuz, Muhiddin (2018-01-01) 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 to the generated numbers and sequences. Knuth test suite is the one of the first statistical randomness suites. This suite, however, is mostly for real number sequences and the parameters of the tests are not given explicitly.
Mutual correlation of NIST statistical randomness tests and comparison of their sensitivities on transformed sequences Doğanaksoy, Ali; Uğuz, Muhiddin; Akcengiz, Ziya (2017-01-01) Random sequences are widely used in many cryptographic applications and hence their generation is one of the main research areas in cryptography. Statistical randomness tests are introduced to detect the weaknesses or nonrandom characteristics that a sequence under consideration may have. In the literature, there exist various statistical randomness tests and test suites, defined as a collection of tests. An efficient test suite should consist of a number of uncorrelated statistical tests each of which meas...
Alternative Approach to Maurer's Universal Statistical Test Tezcan, Cihangir; Doğanaksoy, Ali (null; 2008-12-01) Statistical tests for randomness play an important role in cryptography since many cryptographic applications require random or pseudorandom numbers. In this study, we introduce an alternative approach to Maurer’s Universal Test. This approach allows us to test short binary sequences as small as 66 bits and to choose slightly larger block sizes. Moreover, it does not have an initialization part and requires less time to test a binary sequence.
On Independence and Sensitivity of Statistical Randomness Tests Turan, Meltem Soenmez; Doğanaksoy, Ali; Boztas, Serdar (2008-09-18) Statistical randomness testing has significant importance in analyzing the quality of random number generators. In this study, we focus on the independence of randomness tests and its effect on the coverage of test suites. We experimentally observe that frequency, overlapping template, longest run of ones, random walk height and maximum order complexity tests are correlated for short sequences. We also proposed the concept of sensitivity, where we analyze the effect of simple transformations on output p-val...
On the efficient implementation of RSA Güner, Hatice Kübra; Cenk, Murat; Department of Cryptography (2015) Modular exponentiation is an essential operation for many asymmetric key cryptosystems such as RSA in which encryption and decryption are based on modular exponentiation. Therefore, efficiency of the system is effected with running time of the modular exponentiation algorithm. At the same time, key sizes also influence the efficiency of the algorithm. Over the years key sizes had to be increased to provide security. To make RSA practical, one of usable choices is acceleration of the modular exponentiation a...

Citation Formats

F. SULAK, M. Uğuz, O. O. Koçak, and A. Doğanaksoy, “On the independence of statistical randomness tests included in the NIST test suite,” TURKISH JOURNAL OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCES, pp. 3673–3683, 2017, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/35532.