Экспериментальное исследование эффективности адаптивного теста при проверке генераторов случайных чисел, используемых в криптографии
ВВЕДЕНИЕ
В современном мире случайные числа широко используются в криптографии, компьютерном моделировании, статистике и численных методах Монте-Карло, а также в теории игр и различных других областях.
На практике применяются случайные числа, созданные устройствами, которые генерируют последовательность чисел или символов. Такие устройства называются генераторами случайных чисел (ГСЧ) и генераторами псевдослучайных чисел (ГПСЧ). ГСЧ основываются на физических источниках, а псевдослучайные числа генерируются с помощью компьютерных программ. Целью ГСЧ и ГПСЧ является генерация последовательности двоичных цифр, которые подчиняются распределению Бернулли с параметрами (½, ½). Для практически используемых генераторов данное свойство проверяется экспериментально с помощью разработанных для этой цели статистических тестов.
Неформально идеальный ГСЧ должен генерировать последовательности, которые проходят все тесты.
Введение 3
Глава 1. Анализ предметной области 6
1.1. Генераторы случайных и псевдослучайных чисел 6
1.2. Статистические тесты 7
1.3. Батареи статистических тестов 9
1.3.1. Тесты Д. Кнута 10
1.3.2. Тесты Diehard 10
1.3.3. Тесты Crypt-X 11
1.3.4. NIST STS 11
1.3.5. Библиотека TestU01 12
1. 4. Адаптивное во времени тестирование 13
1.4.1. Схема адаптивного во времени тестирования………………………………………..15
Список используемых источников 15
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. Рябко Б.Я., Фионов А.Н. Криптография в информационном мире. - М: Горячая линия – Телеком, 2018. - 300 с..
2. Перов А.А. Универсальный метод построения решающих правил с использованием сверточных нейронных сетей для анализа генераторов псевдослучайных последовательностей на основе итеративных блочных шифров: дис. ... канд. техн. наук : 05.13.17 / Перов Артём Андреевич ; г. Красноярск. — Новосибирск, 2020. — 153 c. — Режим доступа: https://research.sfu-kras.ru/sites/research.sfu-kras.ru/files/Dissertaciya_Perov_A.A..pdf (дата обращения: 22.03.2022).
3. Григорьев А.Ю. Методы тестирования генераторов случайных и псевдослучайных последовательностей / А.Ю. Григорьев // Ученые записки УлГУ. Сер. Математика и информационные технологии. УлГУ. Электрон.. — 2017. — № 1. — C.22-28.
4. Кнут Д. Искусство программирования, том 2. Получисленные методы / Д. Кнут. — Москва: Вильяме, 2007. — 832 с.
5. Alani A.A. Testing randomness in ciphertext of block-ciphers using DieHard tests / A.A. Alani // International Journal of Computer Science and Network Security. — 2010. — № 10 (4). — P.53-57.
6. NIST SP 800-22 Rev. 1a. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications / [A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, S. Leigh, M. Levenson, M. Vangel, D. Banks, A. Heckert, J. Dray, S. Vo]. National Institute of Standards and Technology, 2010.
7. Перов А.А. Применение статистических тестов NIST для анализа выходных последовательностей блочных шифров // Научный вестник НГТУ. – 2019. – № 3 (76). – С. 87–96.
8. Pierre, L., Simard, R. TestU01 A Software Library in ANSI C for Empirical Testing of Random Number Generators / L. Pierre., R. Simard. — Monreal: 2013. — 219 p.
9. Ryabko B., Zhuravlev V. The time-adaptive statistical testing for random number generators. 2020 International Symposium on Information Theory and Its Applications (Kapolei, HI, USA, 24.10-27.10.2020): Proceedings. - 2020: IEEE. - P.344-347.
10. Cover T.M. Elements of Information Theory / T.M. Cover, J.A. Thomas. — New York, NY, USA: Wiley-Interscience, 2006. — 748 с.
11. Li M. An Introduction to Kolmogorov Complexity and Its Applications / M. Li, P. Vitányi. — New York, NY, USA: Springer, 2008. — 792 с.
12. Монарев В.А. Построение новых статистических тестов и их применение в криптографии : автореф. дис. на соиск. учен. степ. канд. физ.-мат. наук : 05.13.18 "Математическое моделирование, численные методы и комплексы программ" / Монарев В А. — Новосибирск, 2005. — 20 c.
13. Рябко Б. Я., Фионов А. Н. Криптографические методы защиты информации: учебное пособие. — М.: Горячая линия—Телеком, 2005. — 229 с.
14. L’Ecuyer P. History of uniform random number generation. / P. L’Ecuyer // Winter Simulation Conference / USA. — Las Vegas, 2017. — C.202-231.
Последовательность случайна (гипотеза H0 верна) Нет ошибки, предположение верно Ошибка 1-ого рода
Последовательность неслучайна (гипотеза Ha верна) Ошибка 2-ого рода Нет ошибки, предположение верно
Для теста введено понятие уровня значимости – это вероятность ошибки первого рода. Эта вероятность может быть установлена до проведения эксперимента и обозначаться как . Для теста – это вероятность того, что тест укажет, что последовательность неслучайна, когда на самом деле она случайна. Для вероятности ошибки второго рода используется обозначение . Для теста – вероятность того, что тест укажет на то, что последовательность случайна в ситуации, когда действительно это не так, то есть «плохой» генератор создал последовательность, которая имеет случайные свойства. , в отличие от , не является фиксированным значением.