Введение 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 приведен листинг программы.
В результате работы были проанализированы имеющиеся на данный момент времени способы генерации истинно случайных и псевдослучайных последовательностей. Было установлено, что генераторы случайных последовательностей являются криптографически стойкими, потому что они используют случайность окружающего мира: радиоактивный распад, шумы в атмосфере, радиоволны - эти процессы являются непредсказуемыми и неповторимыми. Генераторы псевдослучайных чисел являются надежными, если они основаны на трудно вычислимых задачах: факторизация числа, дискретный логарифм.
Были проанализированы и методы определения качеств случайных последовательностей. Сделан вывод, что серия тестов NIST лучше всего подходит для тестирования двоичных последовательностей произвольной длины: большинство тестов требует последовательность длиной всего 100 бит.
В результате работы был реализован собственный генератор случайных чисел - генератор «Курсор», использующий перемещения курсора мыши в качестве источника случайности. В работе показано, что процесс перемещения курсора можно считать случайным. Были проанализированы различные способы перевода координат на траектории в двоичную последовательность и выбран вариант, который дает наилучшие результаты, - сложение координат по модулю 256.
Исследованы способы последующей обработки последовательностей, получаемых с помощью генератора «Курсор» и показано, что после обработки хеш-функцией MD5 последовательности стали сравнимы с последовательностями, генерируемыми с помощью генераторов истинно случайных последовательностей, например с генератором Random.org. Но была выявлена проблема: генерация длинных случайных последовательностей требует больших усилий пользователя, что делает этот метод малопригодным для генерации длинных последовательностей.
Для генерации длинных последовательностей были реализованы криптографически стойкие генераторы Blum-Micali, Blum-Blum- Shub(BBS). Генератор Blum-Micali показал не очень хорошие статистические свойства, чего нельзя сказать о генераторе BBS, что позволяет рекомендовать его для генерации длинных последовательностей псевдослучайных чисел. Для работы генераторов использованы созданные в рамках работы функции модульной арифметики: быстрое возведение в степень, проверка чисел на простоту и поиск наибольшего общего делителя.
Таким образом, результатом работы является программа - генератор случайных последовательностей. Для генерации коротких случайных последовательностей используется генератор «Курсор», переводящий перемещение курсора мыши в двоичную последовательность. Для генерации же длинных последовательностей рекомендуется использовать генератор BBS. Для инициализации генератора применяются последовательности, полученные с помощью генератора «Курсор». Оба генератора: генератор «Курсор» и BBS показывают результаты сравнимые с истинно случайным генератором.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
