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

Введение 3
Глава 1. Предварительные сведения 6
Генераторы случайных чисел 6
Генераторы псевдослучайных чисел 9
Определение свойств случайных последовательностей 11
Глава 2. Генератор «Курсор» 15
Обоснование случайности 15
Извлечение случайной последовательности из траектории 17
Глава 3. Постобработка 24
Хеш-функции 25
Улучшение свойств случайных последовательностей при помощи хеш-функции MD5 27
Увеличение длины случайной последовательности при помощи хеш-функции MD5 28
Использование случайных последовательностей в качестве зерна для ГПСЧ 29
Заключение 35
Список использованной литературы и интернет - ресурсов 37
Приложение 1. Методика тестирования 40
Приложение 2. Листинг программы
Купить

Данная работа посвящена генерации и исследованию свойств случайных последовательностей. Объектом исследования являются случайные последовательности, а предметом - способы их генерации и свойства, получаемых последовательностей.
Несмотря на то, что первые приспособления для генерации случайных чисел (игральные кости) появились несколько тысяч лет назад, на сегодняшний день задача генерации случайных чисел, а особенно применимых в криптографии, все еще остается открытым вопросом: не существует единого подхода для создания генераторов случайных чисел, каждый день создаются новые генераторы или открываются новые свойства уже известных.
Целью данной работы является создание собственного криптографически стойкого генератора случайных чисел: программная реализация генератора, анализ получаемых случайных
последовательностей и поиск способов улучшения их качества. Для достижения этой цели были поставлен и ряд задач: проанализировать уже имеющиеся генераторы случайных чисел, изучить методы определения свойств случайных последовательностей и улучшения качества последовательностей. В качестве источника случайности было выбрано перемещение курсора мыши, поэтому среди задач был и поиск способа извлечения случайности из вышеназванного процесса.
Случайная последовательность - набор независимых друг от друга элементов, подчиняющихся заданному распределению (чаще всего равномерному). На сегодняшний день случайные последовательности нашли широкое применение в информатике и информационных технологиях: они используются в математическом моделировании, при проведении игр, например онлайн-лотерей, для вычисление вероятностных алгоритмов. Но особую роль случайные последовательности играют в криптографии: генерация паролей, ключей шифрования, простых чисел и многое другое. Если для некоторых задач достаточно, чтобы последовательность подчинялась заданному распределению, то для нужд криптографии необходимо, чтобы последовательности были истинно случайными или криптографически стойкими: задача предсказать следующий бит должна быть трудно разрешимой или неразрешимой вовсе.
В рамках данной работы был реализован генератор случайных чисел, использующий перемещение курсора мыши в качестве источника случайности. В дальнейшем разработанный генератор называется генератором «Курсор». Были проанализированы способы улучшения качеств полученных с помощью генератора «Курсор» последовательностей. Показано, что последующая обработка с помощью хеш-функции MD5 улучшает свойства последовательности. Так же были реализованы и проанализированы криптографически стойкие генераторы Blum-Blum-Shub (BBS) и Blum-Micali. Для инициализации генераторов использовались последовательности, полученные при помощи генератора «Курсор». Показано, что наилучшими свойствами обладает генератор Blum-Blum-Shub. Для работы с генераторами так же были реализованы методы модульной арифметики: быстрое возведение в степень, поиск наибольшего общего делителя, проверка чисел на простоту.
Рассматриваемые в работы методы генерации случайных последовательностей были реализованы в рамках одного приложения на языке C# с использованием платформы UWP (Universal Windows Platform). Выбор в пользу языка C# и платформы UWP был сделан исходя из того, что итоговый продукт предполагается использовать на персональных компьютерах, где ведущей операционной системой является Windows. Язык C# является нативным языком для Windows, то есть лучше всего подходит для разработки приложений для этой ОС. Платформа UWP же позволяет создавать приложение с удобным графическим интерфейсом и обеспечивает возможность запуска приложения на любом устройстве, где установлено ядро Windows10: персональные компьютеры, планшетные компьютеры, смартфоны.
Работа состоит из трех глав. В первой главе рассматриваются способы генерации истинно случайных и псевдослучайных последовательностей, проводится анализ положительных и отрицательных свойств каждого генератора. Во второй главе рассмотрен процесс создания генератора «Курсор» на основе перемещения курсора мыши. Приводятся способы перевода случайной траектории в двоичную последовательность. Третья глава посвящена постобработке полученных последовательностей с целью улучшения их свойств. Также в третьей главе представлено описание криптографически стойких генераторов, которые используют случайные последовательности для инициализации. В приложении 1 описан способ тестирования генератора «Курсор», а в приложении 2 приведен листинг программы.
Купить