Псевдослучайные последовательности и методы их генерации

Введение
Следует начать с того, что большинство явлений, процессов и объектов, с которыми человек сталкивается в жизни, носят случайный характер. Для их адекватного описания, изучения и моделирования недостаточно использовать детерминированные методы (полностью определенные каким-либо алгоритмом), поэтому последовательности случайных чисел и их генерирующие устройства и алгоритмы (генераторы случайных последовательностей) широко используются в науке, технике, связи и информационных технологиях.
Актуальность работы состоит в том, что случайные последовательности играют особую роль в области информационной безопасности. Одним из наиболее эффективных и перспективных подходов к решению проблемы информационной безопасности является использование криптографических методов, в которых генераторы случайных последовательностей часто являются ключевыми компонентами, во многом определяющими их надежность.
Целью данной работы является изучение псевдослучайных последовательностей и методов их генерации. Поставленная цель предполагает решение следующих задач:
рассмотреть понятие и особенности псевдослучайных последовательностей;
исследовать методы генерации псевдослучайных последовательностей.
При написании работы использовались такие методы, как теоретическое обоснование темы, изучение научных источников, а также их сравнительный анализ.
1 Понятие и особенности псевдослучайных последовательностей
Случайное число - это число, порожденное процессом, результат которого непредсказуем и который не может быть достоверно воспроизведен позже. Это определение хорошо работает при условии, что существует «черный ящик» - обычно называемый генератором случайных чисел – который выполняет эту задачу [1, с. 111].
Если есть одно число, то невозможно проверить, является ли оно случайным или нет. Для того чтобы изучить случайность на выходе генератора случайных чисел, необходимо рассмотреть последовательности чисел. Довольно просто определить, является ли последовательность бесконечной длины случайной или нет. Последовательность случайна, если количество содержащейся в ней информации - в смысле информационной теории Шеннона - также бесконечно. Интересно, что бесконечная случайная последовательность содержит все возможные конечные последовательности.
Довольно часто специалисты в области информационной безопасности и защиты информации в своей работе сталкиваются с необходимостью генерирования случайных последовательностей и чисел [3, с. 200].
Необходимость использования случайных чисел в научных исследованиях и технических приложениях существует уже давно. Задачи формирования последовательности случайных чисел часто нуждаются в решении в таких приложениях, как имитационное моделирование, статистическое моделирование, информационная безопасность и телекоммуникации.
Долгое время урны с шариками и игральными костями широко использовались в азартных играх. До сих пор они считаются простейшими истинными генераторами случайных чисел. Позже был реализован ряд механических генераторов случайных чисел (ГСЧ), состоящих из барабана, который смешивает шары с числами, и устройства, которое поочередно извлекает шары из барабана.
В связи с тем, что аппаратные методы генерации случайных чисел не могут быть использованы для проведения ряда вычислительных экспериментов из-за невозможности переформулировать последовательность и подтвердить полученный результат. В связи с этим внимание исследователей было обращено на алгоритмические методы генерации псевдослучайных чисел.
В 1946 году Джон фон Нейман создал метод генерации чисел, «похожих на случайные числа». Суть метода заключалась во введении рекуррентной процедуры формирования следующего псевдослучайного числа на основе предыдущего путем возведения его в квадрат и выбора средних цифр. Понятно, что полученная последовательность не является случайной, но справедлива для ряда приложений. Такие последовательности, сформированные алгоритмически, назывались псевдослучайными последовательностями, а процедуры, которые их формировали, - генераторами псевдослучайных чисел.
2 Методы генерации псевдослучайных последовательностей
Известно, что методы воздействия можно условно разделить на 2 большие группы: воздействие через каналы приема и передачи информации, а также воздействие на каналы связи, приемно-передающую аппаратуру и носители при непосредственном контакте [5, с. 6].
Генератор случайных чисел - это устройство, которое создает последовательности чисел, описанные выше. Существует два основных типа генераторов: программные и физические генераторы. С точки зрения общего программного обеспечения генераторы производят так называемые псевдослучайные числа

. Хотя они могут быть полезны в некоторых случаях, они не должны использоваться в большинстве приложений, где требуется истинная случайность.
Полученная последовательность может иметь некоторые свойства случайных последовательностей и, таким образом, пройти несколько статистических тестов случайности, но она всегда может быть воспроизведена. Ни один детерминированный алгоритм не может генерировать полностью случайные числа, он может лишь приблизить некоторые их свойства. Такие генераторы называются генераторами псевдослучайных чисел (ГПСЧ) [1, с. 112].
Генераторы псевдослучайных последовательностей относятся к числу наиболее важных криптографических примитивов. Во многом именно они определяют надежность используемых систем информационной безопасности. Это делает выбор генераторов очень ответственным шагом. Как уже упоминалось выше, в настоящее время разрабатывается множество различных генераторов псевдослучайных последовательностей. Они основаны на различных принципах работы и заметно отличаются по качеству производимых последовательностей, производительности и сложности реализации.
Существуют различные подходы к классификации генераторов псевдослучайных последовательностей [2, с. 27]. Один из возможных вариантов классификации показан на рисунке 1.
Рисунок 1 – Классификация ГПСП
Как уже отмечалось, псевдослучайные последовательности (ПСП) являются результатом некоторого детерминированного алгоритма, но они используются для тех же целей, что и случайные последовательности. По этой причине ПСП должны быть близки по своим статистическим свойствам к истинно случайным последовательностям. Как правило, алгоритмы генерации таких последовательностей используют специальное случайное начальное значение (seed).
В связи с особенностями генераторов истинных случайных последовательностей, которые серьезно усложняют их использование в условиях ограниченных вычислительных ресурсов и необходимости работы в режиме, близком к реальному времени, возникает необходимость разработки и использования генераторов псевдослучайных последовательностей, производящих последовательности, максимально приближенные по своим свойствам к истинным случайным.
Общая структура генераторов псевдослучайных последовательностей включает следующие основные компоненты:
Источник энтропии.
Блок хранения внутреннего состояния генератора.
Блок генерации очередного значения.
Блок перехода генератора на следующий шаг.
Любой генератор псевдослучайных последовательностей обладает следующими основными признаками:
тип нелинейного преобразования;
структура генератора;
наличие внешних источников энтропии.
На основе анализа уровня устойчивости к взлому нелинейного преобразования, определяющего степень и характер изменения входных данных, выделяются так называемые криптостойкие генераторы, созданные на основе криптографических алгоритмов (блочные и потоковые шифры, а также хэш-функции). Этот класс генераторов будет подробно рассмотрен в соответствующем разделе. С точки зрения реализации существуют также программные, аппаратные и комбинированные генераторы ПСП.
Аппаратные генераторы псевдослучайных чисел реализуют различные алгоритмы генерации ПСП, например, на основе ПЛИС (программируемых логических интегральных схем). Аппаратные и комбинированные ГПСП используются для шифрования данных и помехоустойчивого кодирования. Они также входят в состав оборудования для статистического и имитационного моделирования, испытаний на помехоустойчивость и надежность, в специальные измерительные, идентификационные и испытательные средства, радио-и гидроакустические системы.
В настоящее время существует большое количество способов генерации последовательностей с различной степенью случайности. Однако на практике большинство этих генераторов производят последовательности, свойства которых не отвечают требованиям случайности. Одним из наиболее распространенных примеров этого являются генераторы псевдослучайных чисел, встроенные в стандартные библиотеки многих языков программирования (например, стандартная библиотечная функция языка С rand()). Известно, что все современные языки программирования имеют случайную функцию или ее аналоги [4, с. 31]. Эти функции чаще всего дают действительно хорошие псевдослучайные числа.
Часто существуют четкие закономерности в числах, генерируемых с помощью таких функций. Например, полученные числа в одном сеансе монотонно увеличиваются с течением времени, что прямо противоречит требованиям к свойствам случайных (и псевдослучайных) последовательностей. Для широко известных и распространенных линейных конгруэнтных генераторов дальнейшие значения также могут быть предсказаны из четырех известных сгенерированных чисел.
Большинство криптографических приложений используют генераторы случайных чисел для создания ключей, которые шифруют и расшифровывают необходимую информацию