A unified evaluation of statistical randomness tests and experimental analysis of their relations

Download

index.pdf

Date

2016

Author

Koçak, Onur

Metadata

Show full item record

Item Usage Stats

64
views

109
downloads

Random numbers are used in many applications in our daily life. For instance, when your mobile phone is registering a base station, base station sends a random number for authenticating your phone. Moreover, when logging in your e-mail or bank account your browser and the server exchange random numbers while establishing a handshake. Besides, encryption keys and IVs should be random so that no one can predict them without trying all possible values. The number of examples can be increased from many fields including cryptography, information theory, simulation and quantum theory. Random number sequences are generated by the random number generators (RNG)1 . Deterministic RNGs should be tested to make sure that the output sequences are indistinguishable from random sequences. Unfortunately, theoretic testing is not possible if the output sequences have very obvious relations which is not a usual case. Therefore, testing process is done statistically by applying randomness tests on the sequences and the results are evaluated to conclude the non-randomness of the generator. For the decision to be more reliable a set of tests called test suites are applied on the sequences. Nearly all test suites uses the probabilities derived from the approximations of the distribution functions of the tests. As the approximations work for longer sequences, testing short sequences like keys or IVs becomes infeasible. Moreover, the relations among the tests, which affect the decision on the sequence or the generator, are not measured in any suite. In this thesis, we examine the statistical randomness tests in the literature. We select the tests which are based on mathematical background and are important measures for randomness. Then, we review the distribution functions of these tests to compute the actual probability values. Moreover, we give recursions for the tests whose probability values cannot be computed for longer sequences. Afterwards we find the correlations between the tests and make a classification accordingly. Then, we give some rule of thumbs for designing a test suite and build a test suite consisting of the examined tests.

Subject Keywords

Numbers, Random., Random data (Statistics)., Sequences (Mathematics)., Distribution (Probability theory).

URI

http://etd.lib.metu.edu.tr/upload/12620341/index.pdf
https://hdl.handle.net/11511/26147

Collections

Graduate School of Applied Mathematics, Thesis

Suggestions

OpenMETU
Core

On the independence of statistical randomness tests included in the NIST test suite SULAK, FATİH; Uğuz, Muhiddin; Koçak, Onur Ozan; Doğanaksoy, Ali (2017-01-01) 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 considerati...
Secure password generation through statistical randomness tests Uslu, Aycan; Doğanaksoy, Ali; Department of Cryptography (2017) Both symmetric and asymmetric cryptographic algorithms must firstly be robust against brute force. The key needs to be choosen uniformly and randomly from the key space. It is possible to assure randomness by using statistical randomness tests which are also critical for other cryptographic issues as well. There is still an issue to be elaborated: the most well-known tool for attacking againts passwords namely dictionary attacks. These attacks are based on trying all keys from a particular subspace of the k...
A Randomness test based on postulate r-2 on the number of runs Şeker, Okan; Doğanaksoy, Ali; Department of Cryptography (2014) Random values are considered as an indispensable part of cryptography, since they are necessary for almost all cryptographic protocols. Most importantly, key generation is done by random values and key itself should behave like a random value. Randomness is tested by statistical tests and hence, security evaluation of a cryptographic algorithm deeply depends on statistical randomness tests. In this thesis we focus on randomness postulates of Solomon W. Golomb in particular, second postulate which is about r...
A PHD Filter for Tracking Multiple Extended Targets Using Random Matrices Granstrom, Karl; Orguner, Umut (2012-11-01) This paper presents a random set based approach to tracking of an unknown number of extended targets, in the presence of clutter measurements and missed detections, where the targets' extensions are modeled as random matrices. For this purpose, the random matrix framework developed recently by Koch et al. is adapted into the extended target PHD framework, resulting in the Gaussian inverse Wishart PHD (GIW-PHD) filter. A suitable multiple target likelihood is derived, and the main filter recursion is present...
Mutual correlation of randomness test and analysis of test outputs of transformed and biased sequences Akcengiz, Ziya; Doğanaksoy, Ali; Department of Cryptography (2014) Randomness is one of the most important parts of the cryptography because key generation and key itself depend on random values. In literature, there exist statistical randomness tests and test suites to evaluate randomness of the cryptographic algorithm. Although there exist randomness tests, there is no mathematical evidence to prove that a sequence or a number is random. Therefore, it is vital to choose tests in the test suites due to independency and coverage of the tests used in the suites. Sensitivity...

Citation Formats

O. Koçak, “A unified evaluation of statistical randomness tests and experimental analysis of their relations,” Ph.D. - Doctoral Program, Middle East Technical University, 2016.