vestifmИзвестия Национальной академии наук Беларуси. Серия физико-математических наукProceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series1561-24302524-2415The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"vestifm-234Research ArticleМАТЕМАТИКАMATHEMATICSСТАТИСТИЧЕСКИЕ ТЕСТЫ НА ОСНОВЕ ОЦЕНОК ЭНТРОПИИ ДЛЯ ПРОВЕРКИ ГИПОТЕЗ О РАВНОМЕРНОМ РАСПРЕДЕЛЕНИИ СЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИSTATISTICAL TESTS BASED ON ENTROPY ESTIMATES FOR CHECKING THE HYPOTHESES OF THE UNIFORM DISTRIBUTION OF A RANDOM SEQUENCEПалухаВ. Ю.PalukhaU. Yu.

аспирант кафедры математического моделирования и анализа данных факультета прикладной математики и информатики, Белорусский государственный университет; младший научный сотрудник НИИ прикладных проблем математики и информатики БГУ

Postgraduate of the Department of Mathematical Modeling and Data Analysis, Faculty of Applied Mathematics and Computer Science, Belarusian State University; Junior Researcher of the Research Institute for Applied Problems of Mathematics and Informatics

palukha@bsu.byБелорусский государственный университет, МинскBelarusian State University, Minsk201730042017017988Copyright © Палуха В.Ю., 20172017Палуха В.Ю.Palukha U.Y.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestifm.belnauka.by/jour/article/view/234

Рассматривается актуальная в области защиты информации задача построения статистических тестов для проверки гипотезы о дискретном равномерном распределении («чистой случайности») выходных последовательностей криптографических генераторов. Для функционалов энтропии Шеннона, Реньи и Тсаллиса построены точечные статистические оценки на основе подстановочного принципа с использованием частотных статистик. Найдено асимптотическое распределение вероятностей полученных точечных оценок при справедливости гипотезы о «чистой случайности» в асимптотике, означающей, что количество наблюдаемых данных сравнимо с числом оцениваемых параметров. С использованием распределений вероятностей точечных оценок построены интервальные статистические оценки рассматриваемых функционалов информационной энтропии. На основе интервальных оценок разработаны решающие правила для статистической проверки гипотез о «чистой случайности» наблюдаемой дискретной последовательности. Представлены результаты компьютерных экспериментов, в которых разработанные статистические тесты применяются к выходной последовательности криптографического генератора. Выходная двоичная последовательность в этих экспериментах преобразовывалась к последовательности с алфавитом большей размерности путем объединения соседних s элементов в s-граммы.

 

The actual information security problem of developing statistical tests of the hypothesis about a discrete uniform distribution (‘pure randomness’) of output sequences of cryptographic generators is considered. For the entropy functionals of Shannon, Renyi and Tsallis, the point statistical estimators based on the principle of ‘plug-in’ frequency statistics are constructed. The asymptotic probability distribution of the constructed point estimators is found when the ‘pure randomness’ hypothesis in asymptotics is valid, meaning that the number of observed data is comparable with the number of estimated parameters. With the use of the probability distributions of point estimators, the interval statistical estimators of considered information entropy functionals are constructed. On the basis of interval estimators, the decision rules for statistical testing of the hypothesis about the ‘pure randomness’ of the observed discrete sequence are developed. The results of computer experiments, in which the developed statistical tests are applied to the output sequence of cryptographic generators, are given. In these experiments, the output binary sequence was transformed to the sequence of alphabet with a larger dimension by combining the s neighboring elements in the s-grams.

 

функционалы энтропии ШеннонаРеньи и Тсаллисаасимптотически нормальное распределение вероятностейточечные и интервальные статистические оценкипроверка гипотезкриптографические генераторы случайных и псевдослучайных последовательностейShannonRenyi and Tsallis entropyasymptotically normal probability distributionstatistical estimatorshypotheses testingcryptographic generators of random and pseudo-random sequencesReferencesКриптология / Ю. С. Харин [и др.]. – Минск: БГУ, 2013. – 512 с.Kharin Yu.S., Agievich S.V., Vasil’ev D.V., Matveev G.V. Cryptology. Minsk, Belarusian State University, 2013. 512 p. (In Russian).Esteban, M. D. A summary on entropy statistics / M. D. Esteban, D. Morales // Kybernetika. – 1995. – Vol. 31, № 4. – P. 337–346.Esteban M.D., Morales D.A summary on entropy statistics. Kybernetika, 1995, vol. 31, no. 4, pp. 337–346.Bromiley, P. A. Shannon Entropy, Renyi Entropy, and Information [Electronic resource] / P. A. Bromiley, N. A. Thacker, E. Bouhova-Thacker. – Mode of access: http://www.tina-vision.net/docs/memos/2004-004.pdf. – Date of access: 08.04.2016.Bromiley P.A., Thacker N.A., Bouhova-Thacker E. Shannon Entropy, Renyi Entropy, and Information. Available at: http://www.tina-vision.net/docs/memos/2004-004.pdf. (accessed 8 April 2016).Holst, L. Asymptotic normality and efficiency for certain goodness-of-fit tests / L. Holst // Biometrika. – 1972. – Vol. 59, № 1. – P. 137–145.Holst L. Asymptotic normality and efficiency for certain goodness-of-fit tests. Biometrika, 1972, vol. 59, no. 1, pp. 137–145. Doi: 10.2307/2334624Харин, Ю. С. Теория вероятностей, математическая и прикладная статистика / Ю. С. Харин, Н. М. Зуев, Е. Е. Жук. – Минск: БГУ, 2011. – 463 с.Kharin Yu.S., Zuev N.M., Zhuk E.E. Probability Theory, Mathematical and Applied Statistics. Minsk, Belarusian State University, 2011. 463 p. (In Russian).Палуха, В. Ю. Вероятностные свойства статистической оценки многомерной энтропии в задачах защиты информации / В. Ю. Палуха // XVII Респ. науч.-практ. конф. молодых ученых: сб. материалов, Брест, 15 мая 2015 г.: в 2 ч. – Брест: БрГУ, 2015. – Ч. 1. – С. 57–59.Palukha V.Yu. The probability properties of the multivariate entropy estimator in information security tasks. XVII Respublikanskaya nauchno-prakticheskaya konferentsiya molodykh uchenykh. Sbornik materialov. Ch. 1 [Proceedings of XVII Republican Young Scientists Scientific and Practical Conference. Part 1]. Brest, Brest State University, 2015, pp. 57–59. (In Russian).Палуха, В. Ю. Энтропийные характеристики двоичных последовательностей в криптографии / В. Ю. Палуха, Ю. С. Харин // Комплексная защита информации: материалы XX науч.-практ. конф., Минск, 19–21 мая 2015 г. – Минск: РИВШ, 2015. – С. 99–102.Palukha V.Yu., Kharin Yu.S. Entropy characteristics of binary sequences in cryptography. Kompleksnaya zashchita informatsii: materialy XX nauchno-prakticheskoi konferentsii [Complex Information Protection. Proceedings of XX Scientific and Practical Conference]. Minsk, Republican Institute for Higher Education, 2015, pp. 99–102. (In Russian).Estimating Renyi Entropy of Discrete Distributions [Electronic resource] / J. Acharya, [et al.]. – Mode of access: http:// arxiv.org/pdf/1408.1000v3.pdf. – Date of access: 08.04.2016.Acharya J., Orlitsky A., Suresh A.T., Tyagi H. Estimating Renyi Entropy of Discrete Distributions. Available at http:// arxiv.org/pdf/1408.1000v3.pdf. (accessed 8 April 2016).Энвин, А. Ю. Дискретная математика / А. Ю. Энвин. – Челябинск: Изд-во ЮУрГУ, 1998. – 176 с.Envin A.Yu. Discrete Mathematics. Cheliabinsk, South Ural State University, 1998. 176 p. (In Russian).Харин, Ю. С. Статистические оценки энтропии Реньи и Тсаллиса и их использование для проверки гипотез о «чистой случайности» / Ю. С. Харин, В. Ю. Палуха // Вес. Нац. акад. навук Беларусі. Сер. фіз.-мат. навук. – 2016. – № 2. – С. 37–47.Kharin Yu.S., Palukha U.Yu. Statistical estimates of Rényi and Tsallis entropy and their use for testing the ‘pure randomness hypotheses. Vestsі Natsyyanalnai akademіі navuk Belarusі. Seryya fіzіka-matematychnykh navuk [Proceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series], 2016, no. 2, pp. 37–47. (In Russian).Speedtest-500MB.bin [Electronic resource] // Humboldt Berlin University, Faculty of Mathematics and Natural Sciences, Department of Physics. – Mode of access: http://qrng.physik.hu-berlin.de/files/speedtest-500MB.bin. – Date of access: 08.04.2016.Speedtest-500MB.bin. Humboldt Berlin University, Faculty of Mathematics and Natural Sciences, Department of Physics. Available at http://qrng.physik.hu-berlin.de/files/speedtest-500MB.bin. (accessed 8 April 2016).

The authors declare that there are no conflicts of interest present.