Псевдослучайные последовательности — это последовательности чисел, компоненты которых практически независимы друг от друга и подчиняются заданному распределению.
Введение
Главная проблема стандартной криптографии длительное время состояла в трудности генерации непредсказуемых двоичных последовательностей значительной длины с использованием короткого случайного ключа. Значительный прогресс в проектировании и анализе таких генераторов произошел только в начале шестидесятых годов прошлого века.
Формируемые программными средствами из ключа случайные или псевдослучайные наборы чисел именуются на жаргоне специалистов криптографии гаммой. Это название происходит от буквы у греческого алфавита, которой в математических формулировках принято обозначать случайные величины.
Необходимо отметить, что заслуга формирования длинных псевдослучайных рядов, обладающих отличными статистическими свойствами, целиком принадлежит криптографии. Однако не нужно полагать, что они необходимы только специалистам в сфере криптографии. Например, процесс картографирования Венеры стал возможным, когда длина периода случайного ряда импульсов стала больше десяти. Осуществление фотосъемки Венеры невозможно было реализовать, поскольку она почти всегда покрыта плотным слоем облаков.
Локация же ее с Земли затрудняется обилием помех и повышенными требованиями к разрешению. По этой причине зондирование исполнялось случайной последовательностью импульсов вышеназванного периода. После реализации трехсот зондирований, на что потребовалось больше шести месяцев работы, была сформирована карта, где можно было различить объекты размером примерно с километр, а по высоте было достигнуто такое разрешение, какое даже на Земле не везде может быть достигнуто.
Генераторы псевдослучайных чисел применяются в большом количестве программных приложений, начиная от конструирования ядерных реакторов и радиолокационных систем раннего обнаружения, и заканчивая поиском нефти и системой многоканальной связи.
Псевдослучайные последовательности и методы их генерации
Следует выделить следующие основные общие требования, которым должны соответствовать криптографически стойкие генераторы псевдослучайных последовательностей и формируемые с их помощью гаммы:
- Период гаммы обязан являться достаточно большим для того, чтобы можно было шифровать сообщения разной длины.
- Гамма обязана выступать как трудно предсказуемая величина. Это означает, что когда являются известными тип генератора и кусок гаммы, то отсутствует возможность предсказания следующего за этим куском бита гаммы или предшествующего этому куску бита гаммы.
- Генерация гаммы не должна быть связана с большими техническими и организационными проблемами.
Наиболее важной характеристикой генератора псевдослучайных чисел является информационная длина его периода, после которого числа могут или просто повторяться, или станут предсказуемыми. Данная длина фактически должна определять возможное число ключей криптосистемы, то есть, чем эта длина больше, тем более сложно осуществить подбор ключа.
Однако здесь возникают некоторые вопросы, в частности, на основании каких характеристик может быть сделано заключение, что гамма конкретного генератора псевдослучайных последовательностей действительно может считаться непредсказуемой? На текущий момент в мире не выработано универсального и практически достоверного критерия, предоставляющего возможность проверки данного свойства.
Для того чтобы гамму можно было считать случайной и непредсказуемой, необходимо, по крайней мере, чтобы ее период был достаточно большим, а разные комбинации битов определенной длины были равномерно распределены по всей ее длине. Данное требование статистически может быть истолковано и как сложность закона генерации псевдослучайной последовательности чисел. Если по достаточно длинному отрезку этой последовательности невозможно ни статистическим, ни аналитическим путем вычислить этот закон генерации, то практически это может считаться отличным результатом.
А третье требование обязано предоставить гарантию возможности практической реализации генераторов псевдослучайных последовательностей при учете необходимого быстродействия и удобства практичного применения.
Задача генерации псевдослучайных последовательностей известна уже почти триста лет. Одним из первых стало предложение формировать их в качестве значений дробной части многочлена первой степени:
$Yn = Ent (a • n + b)$, где: $a. b = const$
Когда «п» проходит через значения натурального ряда чисел, то значения Y(ri) будут выглядеть достаточно хаотично. Еще Карл Якоби сумел доказать, что при рациональном коэффициенте «а» множество {Y(n)} является конечным, а при иррациональном коэффициенте «а» будет бесконечным и всюду плотно в интервале от нуля до единицы.
Для многочленов с большими степенями подобную задачу смог решить в 1916-ом году известный математик двадцатого века Герман Вейль. Помимо этого, он определил критерий равномерности распределения любых функций от натурального ряда чисел. Приведем этот критерий в краткой формулировке.
Для того чтобы ряд $Х_1, X_2, Х_3, ...$ был равномерно распределен в интервале от нуля до единицы, является необходимым и достаточным, чтобы для любой интегрируемой по Риману функции Дх) было справедливо соотношение:
Р{ДМ(х)) = МДх)} = 1.
Данное соотношение отображает свойство, именуемое эргодичностью и состоящее в том, что среднее по реализациям псевдослучайных чисел равняется среднему по всему их множеству с вероятностью, равной единице. Это означает, что Вейль сумел доказать, что эргодичность является гарантией отсутствия экзотичности в поведении последовательности $Х_п.$
Но данные результаты являются далекими от практики получения псевдослучайных рядов чисел. Попытки замены настоящего иррационального числа его приближением на компьютере для генерации псевдослучайной последовательности могут быть опасными, поскольку формируемые последовательности оканчиваются циклами с коротким периодом.
