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


Tezin Türü: Doktora

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Fen Edebiyat Fakültesi, Matematik Bölümü, Türkiye

Tezin Onay Tarihi: 2016

Öğrenci: ONUR KOÇAK

Danışman: ALİ DOĞANAKSOY

Özet:

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.