A randomness test based on postulate r-2 on the number of runs

Abstract

Rastgele değerler neredeyse bütün kriptografik protokollerde ihtiyaç¸ duyulduğu için kriptografinin ayrılmaz bir parçası olarak görülmektedir. En önemlisi, anahtar üretimi rastgele değerler ile sağlanmaktadır ve anahtarın kendisi de bir rastgele değer gibi davranmalıdır. Rastgelelik testleri istatistiksel testleri ile yapılmaktadır, bu yüzden kriptografik algoritmaların güvenliği derin bir şekilde istatistiksel rastgelelik testlerine bağlıdır. Bu tezde Solomon W. Golomb tarafından tanımlanan rasgelelik postülalarına odaklanılmıştır, özellikle öbek sayıları ve dağılımları üzerine olan ikinci postülası üzerine çalışılmıştır. Postülada geçen öbek terimi, bir seride geçen kesintisiz ve aynı bitlerden oluşan en uzun alt-seriler olarak tanımlanmıştır. Birlik, ikilik ve üçlük öbek sayılarının dağılımı vurgulanmış ve bu dağılımlar ile yeni istatistiksel rastgelelik testlerini tanımlanmıştır. Yeni testler chi-kare dağılımını kullandıkları için, gerçek olasılıklara ihtiyaç duyulmuştur. Bu olasılıkları kombinatorik bir yaklaşım ile hesaplanmıştır. Testlerde kullanmak üzere bu olasılıkları alt-aralık denilen beş aralığa bölünmüştür. Alt-aralıklar neredeyse eşit olasılıklara sahip olacak şekilde seçilmiştir. Son olarak da testler tanımlanmış¸ ve kodları verilmiştir. Yeni tanımlanan testler farklı uzunluktaki öbek sayılarının dağılımındaki sapmaları ortaya çıkarmak üzere tasarlanmıştır. Diğer testler farklı uzunluktaki öbek sayıları ile ilgilenmedikleri için bu sapma belirlenememektedir. Yeni testler bazı tanınmış algoritmalar ve irrasyonel sayıların ikili açılımları üzerinde uygulanmıştır. Bu deneyler testleri performansını ve hassasiyetini göstermiştir

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 runs of a sequence and their distributions. The distributions of runs of length one, two and three are underlined. And by these distributions we state three new statistical randomness tests. New tests use chi-square distribution therefore, exact probabilities are needed. We calculate the probabilities in a combinatorial approach. In order to using in the tests, probabilities are divided into five intervals, which are called as subintervals. Subintverval are selected in such a manner that each interval has nearly equal probabilities. Finally, three new statistical tests are defined and pseudocodes for new statistical tests are given. New statistical tests are designed to detect deviations of number of different length from a random sequence. Since other tests are not interested in runs of different length, they cannot be detected this deviation. The tests are implemented with some other statistical tests, on some well-known algorithms and binary expansion of irrational numbers. Experiment results show the performance and sensitivity of our tests.