Генераторы псевдослучайных чисел и методы их тестирования

Оглавление 1 Введение. 3  2 Генератор псевдослучайных чисел. 4  3 Методы получение псевдослучайных чисел. 6  3.1 Линейный конгруэнтный метод. 7  3.2 Метод Фибоначчи. 8 3.3 Линейный регистр сдвига с обратной связью.. 10 3.4 Вихрь Мерсенна. 11 4 Тестирование псевдослучайных последовательностей. 12 4.1 Графические тесты.. 12 4.2 Статистические тесты.. 13 4.2.1 Основные принципы.. 14 4.2.2 Тесты Д. Кнута. 14 4.2.3 Пакет статистических тестов NIST. 15 4.2.4

Тесты Diehard. 22 5 Вывод. 24 6 Список используемой литературы.. 25 Приложение А.. Ошибка! Закладка не определена.     1 Введение   Генерирование случайных последовательностей с заданным вероят­ностным законом и проверка их адекватности — одни из важнейших проблем современной криптологии. Генераторы случайных последова­тельностей используются в существующих криптосистемах для генера­ции ключевой информации и задания

ряда параметров криптосистем. Научная и практическая значимость этой проблемы настолько велика, что ей посвящены отдельные монографии в области криптологии, орга­низуются разделы в научных журналах "Journal of Cryptology", "Cryptologia" и специальные заседания на международных научных конфе­ренциях "Eurocrypt", "Asiacrypt", "Crypto" и др. В начале XX века случайные последовательности имитировались с помощью простейших случайных экспериментов: бросание

монеты или игральной кости, извлечение шаров из урны, раскладывание карт, рулетка и т. д. В 1927 г. Л. Типпетом впервые были опубликованы та­блицы, содержащие свыше 40000 случайных цифр, "произвольно из­влечённых из отчётов о переписи населения". В 1939 г. с помощью специально сконструированного механического устройства — генера­тора случайных чисел, М. Дж. Кендалл и Б. Бэбингтон-Смит создали таблицу, включающую 105 случайных цифр.

В 1946 г. американский математик Джон фон Нейман впервые предложил компьютерный алго­ритм генерации случайных чисел. В 1955 г. компания RAND Corpora­tion опубликовала получившие широкую популярность таблицы, содер­жащие 106 случайных цифр, сгенерированных на ЭВМ. В настоящее время спрос на генераторы случайных последователь­ностей с заданными вероятностными распределениями, а также на сами случайные последовательности настолько