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

Download
2014
Şeker, Okan
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.

Suggestions

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...
A Survey on the provable security using indistinguishability notion on cryptographic encryption schemes
Ayar, Emre; Doğanaksoy, Ali; Koçak, Onur; Department of Cryptography (2018)
For an encryption scheme, instead of Shannon's perfect security definition, Goldwasser and Micali defined a realistic provable security called semantic security. Using indistinguishability notion, one can define security levels according to the polynomial time adversaries' capabilities such as chosen plaintext attacks (CPA) and chosen ciphertext attacks (CCA) for both symmetric and asymmetric encryption schemes in addition to the hard mathematical problems the algorithms based on. Precautions to prevent the...
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...
Modular exponentiation methods in cryptography
Yünüak, Hasan Bartu; Cenk, Murat; Department of Cryptography (2017)
Modular exponentiation has an important role in many cryptographic algorithms. These exponentiation methods differ in the bases used and their representations, the repeating aspect, and for which algorithms they are used for: fixed or variable base. Our research aims to compare the efficiencies and implementation timings for some selected algorithms. Also, we look at the options for using a dedicated cubing algorithm, and compare them with the current algorithms.
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
O. Şeker, “A Randomness test based on postulate r-2 on the number of runs,” M.S. - Master of Science, Middle East Technical University, 2014.