Разработка и исследование генераторов псевдослучайных чисел

Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования
«САНКТ-ПЕТЕРБУРГСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
МЕХАНИКИ И ОПТИКИ»

Лабораторная работа №1
Тема: Разработка и исследование генераторов псевдослучайных чисел

Дисциплина: Моделирование систем защиты информации

Выполнил:
студент группы N3354
Сорокин Борислав

Санкт-Петербург
2017г.

Роль и место ГСЧ (ГПСЧ) в задачах обеспечения безопасности информационных технологий.

ГСЧ и ГПСЧ имеют огромную роль в обеспечении информационной безопасности. Без них невозможно было бы реализовать быстрые и, самое главное, безопасные алгоритмы создания ключей шифрования и паролей, на которых держится сейчас практически весь интернет. ГСЧ и ГПСЧ используются не только в создании ключей, но и в создании различных идентификаторов. Без их использования идентификация работала как серийные номера и происходила постоянную проверку на валидность, например, как серия и номер паспорта гражданина, что заметно увеличивает время на проверку и на генерацию нового идентификатора, а с увеличением устройств такая процедура требовала огромных технических мощностей.

Варианты программной реализации ГСЧ

1. Линейный конгруэнтный генератор

, где a, c, и  – случайные константы, удовлетворяющие условиям быть больше нуля и не больше m, которое тоже является случайным числом.[pic 1][pic 2]

Линейный конгруэнтный генератор является ГПСЧ, в котором используется один из самых простых алгоритмов, основанном на использовании предыдущего числа и вычислении остатка от деления. Что дает очень высокую скорость генерации, однако он совершенно не подходит для использования его в информационной безопасности. Причина тому, повторение генерируемых блоков. Для частичного решения этой проблемы можно использовать большой делитель, но это заметно увеличивает ресурсы, требуемые на вычисление такой последовательности. На практике алгоритм был реализован в некоторых компиляторах Watcom C/C++, в которых число m было равно , где n разрядность процессора^[1]. [pic 3]

1. Генератор Фибоначчи с запаздыванием

 , где C – случайное число равное 2m, m – четное число,  Xi-n – предыдущее число. Числа, которые используются для вычисления последовательности от 0 до q являются целыми и произвольными.[pic 4]

Генератор Фибоначчи с запаздыванием пришел на смену линейного конгруэнтного генератора. Он работает быстрее так как в нем не обязательно использовать операцию умножения.

Числа p и q формирую запаздывание, что приводит к очень большим периодам. Чем больше они будут, тем случайна будет последовательность.

1. Вихрь Мерсенна

Вихрь Мерсенна основывается на свойствах простых чисел Марсенна (2n-1), что обеспечивает быструю и качественную генерацию псевдослучайных чисел. Сравнивая его с другими ГПСЧ, он имеет большой период, непредсказуемость, нет статических закономерностей. Однако он не обладает криптографической стойкостью, что ограничивает его использование в криптографии.

Разработка ГСЧ

        Рассматриваться в данной лабораторной работе будут два алгоритма генерации случайных и псевдослучайных значений из определенного диапазона, используемых в языке PHP 7.1 версии. Исследовать я буду функцию rand(), которая в 7.1 версиях стала синонимом функции mt_rand(), основанная на базе Вихря Мерсена и функцию random_int(), которая только появилась в 7+ версиях.  

        Функция rand() является ГПСЧ и не генерирует криптографически безопасные значения и не должна использоваться в криптографических целях^[2]. Исходный код доступен по адресу: https://github.com/php/php-src/blob/PHP-7.1.0/ext/standard/mt_rand.c