СИСТЕМА СТАТИСТИЧЕСКОГО ТЕСТИРОВАНИЯ СЛУЧАЙНЫХ ЧИСЕЛ НА ОСНОВЕ МЕТОДОВ МОНТЕ-КАРЛО

Анна В. Епишкина, Пётр А. Тихонов

Аннотация


Генерация случайных чисел в криптографических системах – один из важнейших элементов информационной безопасности. Для оценки качества случайных последовательностей широко применяются пакеты статистических тестов. Методы Монте-Карло, представляющие собой инструмент статистического моделирования, основываются на предположении о случайности входных данных, но в рамках задачи тестирования случайных последовательностей не нашли своей реализации в виде пакета статистических тестов. Основной гипотезой исследования стала возможность применения методов Монте-Карло как подхода к оценке последовательностей чисел на соответствие свойствам случайности. Рассматривается ряд методов («игла Бюффона», простейший метод для вычисления интегралов, цепи Маркова и другие), на базе которых был разработан пакет, содержащий 18 статистических тестов. Определены основные идеи и принципы проведения статистического тестирования с использованием методов Монте-Карло. Сформированы требования и архитектура системы статистического тестирования, определяющая структуру компонентов, их функциональные обязанности и последовательность выполнения операций – от конфигурирования и инициализации до вывода результатов. Предложена гибкая система конфигурации через файл в формате JSON. Программная версия пакета статистических тестов на основе методов Монте-Карло выполнена на языке C++ и организована в виде статической библиотеки, содержащей основные классы тестов и вспомогательный инструментарий. Дополнительно разработаны и реализованы механизмы для упрощения конфигурации пакета на основе заранее размеченной выборки последовательностей. Разработанный пакет тестов на основе методов Монте-Карло был протестирован на примере нескольких последовательностей, а результаты были сопоставлены с получившими известность программными пакетами (NIST STS, Dieharder и TestU01).

Ключевые слова


методы Монте-Карло, статистические тесты, случайные последовательности, тестирование случайных последовательностей, программный пакет

Полный текст:

PDF

Литература


1. Небезопасная генерация случайности. CQR Company. URL: https://cqr.company/ru/web-vulnerabilities/insecure-randomness-generation (дата обращения: 07.04.2026).
Insecure randomness generation. CQR Company. URL: https://cqr.company/ru/web-vulnerabilities/insecure-randomness-generation (accessed: 07.04.2026) (in Russian).
2. Иванов, М. (2024). Стохастические методы защиты информации. Безопасность информационных технологий, 31(3), 83-93. DOI: http://dx.doi.org/10.26583/bit.2024.3.03.
Ivanov, М. (2024). Stochastic methods of information security. IT Security (Russia), 31(3), 83-93. DOI: http://dx.doi.org/10.26583/bit.2024.3.03 (in Russian).
3. Орлов, М., Нечаев, К., Резниченко, С. (2023). Оценка статистических свойств и криптографической стойкости случайных последовательностей, полученных квантовым компьютером IBM. Безопасность информационных технологий, 30(1), 14-26. DOI: http://dx.doi.org/10.26583/bit.2023.1.01.
Orlov, M., Nechaev, K., Reznichenko, S. (2023). Evaluation of statistical properties and cryptographic strength of random sequences obtained by an IBM quantum computer. IT Security (Russia), 30(1), 14-26. DOI: http://dx.doi.org/10.26583/bit.2023.1.01 (in Russian).
4. Соболь И.М. Численные методы Монте-Карло. Москва: Наука, 1973. URL: https://ikfia.ysn.ru/wp-content/uploads/2018/01/Sobol1973ru.pdf (дата обращения: 07.04.2026).
Sobol' I.M. Numerical Monte Carlo methods. Moscow: Nauka, 1973. URL: https://ikfia.ysn.ru/wp-content/uploads/2018/01/Sobol1973ru.pdf (accessed: 07.04.2026) (in Russian).
5. Rukhin A., Soto J., Nechvatal J., Smid M., Barker E. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. NIST Special Publication 800-22 Revision 1a. Gaithersburg, MD: National Institute of Standards and Technology, 2010. URL: https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-22r1a.pdf (accessed: 07.04.2026).
6. Brown R.G., Bau D. DieHarder: A GNU Public License Random Number Tester. URL: https://rurban.github.io/dieharder/manual/dieharder.pdf (accessed: 07.04.2026).
7. Schuemie M.J., Ryan P.B., DuMouchel W., Suchard M.A., Madigan D. Empirical calibration of p-values. OHDSI. URL: https://ohdsi.github.io/EmpiricalCalibration/articles/EmpiricalPCalibrationVignette.html (accessed: 16.11.2025).
8. Robles E., Zaidouni F., Mavromoustaki A., Refael P. Threshold Optimization in Multiple Binary Classifiers for Extreme Rare Events using Predicted Positive Data. CEUR Workshop Proceedings. V. 2600, 2020. URL: https://ceur-ws.org/Vol-2600/paper19.pdf (accessed: 16.11.2025).
9. Maximum number of overlapping intervals. GeeksforGeeks. 2025. URL: https://www.geeksforgeeks.org/dsa/maximum-number-of-overlapping-intervals/ (accessed: 29.03.2026).
10. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ: учеб. пособие. Пер. с англ. 3-е изд. Москва: Вильямс, 2013. – 1328 с.
Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to Algorithms. 3rd ed. Cambridge, MA: MIT Press, 2009. 1328 p. (in Russian).
11. Гринев Д.В. Игла Бюффона: история одной задачи и развитие интегральной геометрии. URL: https://matematika76.ru/cis/minicourse_slides_II.pdf (дата обращения: 07.04.2026).
Grinev D.V. Buffon's needle: the history of a problem and the development of integral geometry [Electronic resource]. – URL: https://matematika76.ru/cis/minicourse_slides_II.pdf (accessed: 07.04.2026) (in Russian).
12. Badger, L. (1994). Lazzarini’s Lucky Approximation of π. Mathematics Magazine, 67(2), 83–91. DOI: https://doi.org/10.1080/0025570X.1994.11996194.
13. Жданов Э.Р., Маликов Р.Ф., Хисматуллин Р.К. Компьютерное моделирование физических явлений и процессов методом Монте-Карло: учеб. пособие. URL: http://simulation.su/uploads/files/default/2005-uch-posob-gdanov-malikov-hismatullin-1.pdf (дата обращения: 07.04.2026).
Zhdanov E.R., Malikov R.F., Khismatullin R.K. Computer modeling of physical phenomena and processes by the Monte Carlo method: textbook.URL: http://simulation.su/uploads/files/default/2005-uch-posob-gdanov-malikov-hismatullin-1.pdf (accessed: 07.04.2026) (in Russian).
14. Gleich D.F. Multi-way Monte Carlo Method for Linear Systems. arXiv preprint arXiv:1608.04361. 2016. URL: https://arxiv.org/pdf/1608.04361 (accessed: 20.04.2025).
15. Martinez-Otzeta J.M., Rodriguez-Moreno I., Mendialdua I., Sierra B. RANSAC for Robotic Applications: A Survey. URL: https://www.researchgate.net/publication/366662416_RANSAC_for_Robotic_Applications_A_Survey (accessed: 26.04.2025).
16. Марковская цепь. Информатика: учебно-методические материалы. Санкт-Петербург: ИТМО. URL: https://neerc.ifmo.ru/wiki/index.php?title=Марковская_цепь (дата обращения: 15.04.2025).
Markov chain. Informatics: educational and methodological materials. St. Petersburg: ITMO University. URL: https://neerc.ifmo.ru/wiki/index.php?title=Markov_chain (accessed: 15.04.2025) (in Russian).
17. Biswas S. Various proofs of the Fundamental Theorem of Markov Chains. arXiv preprint arXiv:2204.00784. 2022. URL: https://arxiv.org/pdf/2204.00784 (accessed: 17.04.2025).
18. Ревотюк М.П. Объектно-ориентированное программирование и проектирование. Часть 1. Технологии объектного программирования: учеб.-метод. пособие. Минск: БГУИР, 2015. URL: https://libeldoc.bsuir.by/bitstream/123456789/1088/2/Revotyuk_Ch1.pdf (дата обращения: 07.04.2026).
Revotyuk M.P. Object-oriented programming and design. Part 1. Object programming technologies: educational and methodological guide. Minsk: BGUIR, 2015. URL: https://libeldoc.bsuir.by/bitstream/123456789/1088/2/Revotyuk_Ch1.pdf (accessed: 07.04.2026) (in Russian).
19. RAND_bytes(3ssl): OpenSSL 3.0 documentation. OpenSUSE Tumbleweed. URL: https://manpages.opensuse.org/Tumbleweed/openssl-3-doc/RAND_bytes.3ssl.en.html (accessed: 29.03.2026).
20. Gutterman Z., Pinkas B., Reinman T. Analysis of the Linux Random Number Generator. Astec information security blog. 2017. URL: https://atsec-information-security.blogspot.com/2017/09/linux-devrandom-study-published.html (accessed: 29.03.2026).




DOI: http://dx.doi.org/10.26583/bit.2026.3.10

Ссылки

  • На текущий момент ссылки отсутствуют.


Лицензия Creative Commons
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.