On the correlation and sensitivity of so far statistical randomness tests based on runs
DOI:
https://doi.org/10.54654/isj.v2i14.212Tóm tắt
Abstract—Random numbers play a very important role in cryptography. More precisely, almost cryptographic primitives are ensured their security based on random values such as random key, nonces, salts... Therefore, the assessment of randomness according to statistical tests is really essential for measuring the security of cryptographic algorithms. In this paper, we focus on so far randomness tests based on runs in the literature. First, we have proved in detail that the expected number of gaps (or blocks) of length in a random sequence of length is . Secondly, we have evaluated correlation of some tests based on runs so far using Pearson coefficient method [5, 6] and Fail-Fail ratio one [7, 8]. Surprisingly, the Pearson coefficient method do not show any strong linear correlation of these runs-based tests but the Fail-Fail ratio do. Then, we have considered the sensitivity of these runs tests with some basic transformations. Finally, we have proposed some new runs tests based on the sensitivity results and applied evaluations to some random sources.
Tóm tắt—Số ngẫu nhiên đóng một vai trò quan trọng trong mật mã. Cụ thể, độ an toàn của hầu hết các nguyên thủy mật mã đều được đảm bảo dựa trên các giá trị ngẫu nhiên như khóa, nonce, salt… Do đó, việc đánh giá tính ngẫu nhiên dựa trên các kiểm tra thống kê là thực sự cần thiết để đo độ an toàn cho các thuật toán mật mã. Trong bài báo này, chúng tôi tập trung vào các kiểm tra ngẫu nhiên dựa vào run trong các tài liệu. Đầu tiên, chúng tôi chứng minh chi tiết rằng kỳ vọng số các gap (khối) độ dài trong một chuỗi ngẫu nhiên độ dài là . Sau đó, chúng tôi đánh giá mối tương quan của một số kiểm tra dựa vào run bằng phương pháp hệ số Pearson [5, 6] và tỷ số Fail-Fail [7, 8]. Đáng ngạc nhiên là phương pháp hệ số Pearson không cho thấy bất kỳ mối tương quan tuyến tính mạnh nào của các kiểm tra dựa vào run, trong khi đó tỷ số Fail-Fail lại chỉ ra. Tiếp theo, chúng tôi xem xét độ nhạy của các kiểm tra run này với một số phép biến đổi cơ bản. Cuối cùng, chúng tôi đề xuất một số kiểm tra run mới dựa trên các kết quả độ nhạy và đánh giá áp dụng chúng cho một số nguồn ngẫu nhiên.
Downloads
References
MacLaren, M.D., The art of computer programming. Volume 2: Seminumerical algorithms (Donald E. Knuth). SIAM Review, 1970. 12(2): p. 306-308.
Marsaglia, G., The marsaglia random number cdrom including the diehard battery of tests of randomness, 1995. 2008.
Caelli, W., Crypt x package documentation. Information Security Research Centre School of Mathematics, Queensland University of Technology, 1992.
Rukhin, A., et al., Statistical test suite for random and pseudorandom number generators for cryptographic applications, NIST special publication. 2010.
Doğanaksoy, A., et al., New statistical randomness tests based on length of runs. Mathematical Problems in Engineering, 2015. 2015.
Golomb, S.W., Shift register sequences. 1982: Aegean Park Press.
L'Ecuyer, P. and R. Simard, TestU01: AC library for empirical testing of random number generators. ACM Transactions on Mathematical Software (TOMS), 2007. 33(4): p. 22.
Menezes, A.J., P.C. Van Oorschot, and S.A. Vanstone, Handbook of applied cryptography. 2018: CRC press.
Linh, H.Đ., Some results on new statistical randomness tests based on length of runs. Journal of Science Technology on Information security, 2018. 8(2): p. 10-18.
Turan, M.S., A. DoĞanaksoy, and S. Boztaş. On independence and sensitivity of statistical randomness tests. in International Conference on Sequences and Their Applications. 2008. Springer.
Mood, A.M., The distribution theory of runs. The Annals of Mathematical Statistics, 1940. 11(4): p. 367-392.
Downloads
Published
How to Cite
Issue
Section
License
Proposed Policy for Journals That Offer Open Access
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
Proposed Policy for Journals That Offer Delayed Open Access
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication, with the work [SPECIFY PERIOD OF TIME] after publication simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
