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

Abstract

Rastgele sayılar birçok uygulamada kullanılmaktadır. Örneğin, cep telefonu bir baz istasyonuna bağlanacağı zaman, baz istasyonu telefonunuzu doğrulamak için bir rastgele sayı gönderir. Güvenilir internet sitelerine giriş yaparken bilgisayarınız ve sunucu el sıkışması sırasında aralarında rastgele sayılar gönderirler. Kriptografi, bilgi teorisi gibi alanlarda benzer örneklerin sayısı artırılabilir. Rastgele sayı dizileri rastgele sayı üreteçleri(RSÜ) tarafından üretilirler. Belirsizlikleri düşük olan RSÜlerin çıktılarının rastgele dizilerden ayırt edilemez olduğundan emin olmak için test edilmeleri gerekmektedir. Ancak bu testler deneysel olarak gerçekleştirilmektedir. Bu sebeple, testler çıktılar üzerine istatistiksel rastgellik testleri uygulanarak yapılır ve sonuçları değerlendirilir. Sonucun güvenilir olması için birden çok test içeren test paketleri kullanılmaktadır. Neredeyse bütün test paketleri testlerin dağılım fonksiyonları için yaklaşımlar kullanırlar. Ancak, yaklaşımlar uzun diziler için doğru sonuç verdikleri için testler de uzun diziler üzerinde çalışmakta ve kısa dizilerin test edilmesi mümkün olmamaktadır. Bununla birlikte, testler arasındaki ilişkiler hiçbir pakette ölçülmemiştir. Bu tezde literatürdeki istatistiksel rastgelelelik testleri incelenmiş, istatistiki olarak anlamlı olan testler seçilmiştir. Seçilen testlerin dağılım fonksiyonları incelendikten sonra yaklaşım değerleri yerine gerçek değerlerden oluşan olasılık değerleri elde edilmiştir. Bu değerlerden uzun diziler için hesaplanması uygulanabilir olmayanlar için tekrarlamalı formüller verilmiştir. Testler arasındaki ilişkiler incelenmiş ve buna göre testlerin sınıflandırılması yapılmıştır. Son olarak test paketi oluşturulurken takip edilmesi gereken kurallar belirtilerek seçilen testlerden bir test paketi oluşturulmuştur.

Random numbers are used in many applications. 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. The number of examples can be increased from many fields including cryptography, information theory and so on. Random number sequences are generated by the random number generators (RNG). 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.