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

Как мы видели в предыдущей лекции, стойкость криптосистемы прямо зависит от информационной энтропии ключа, а максимум информационной энтропии получается при идеально случайном равновероятном выборе ключа из всего пространства ключей. На самом деле, на практике находят применение распределения вероятности, отличные от равномерного, но как мы видели при анализе арифметического кодирования, задачу получения случайного значения с заданным распределением можно свести к задаче получения случайного значения с равномерным распределением.

Равномерно распределённая случайная последовательность

РРСП

случайная последовательность \(\{x_1, x_2, \ldots, x_t, x_{t+1}, \ldots\}\) со значениями \(x_i \in \mathcal A = \{a_1, a_2, \ldots, a_N\}\), удовлетворяющая двум свойствам:

  1. \(\forall n \in \mathbb N,\) \(\forall 1 \le t_1 < t_2 < \ldots < t_n, t_i \in \mathbb N\), случайные величины \(x_{t_1}, x_{t_2}, \ldots, x_{t_n}\) независимы в совокупности, т.е. \[P(x_{t_1} x_{t_2} \ldots x_{t_n}) = P(x_{t_1}) P(x_{t_2}) \ldots P(x_{t_n}).\]

  2. \(\forall t \in \mathbb N\), случайная величина \(x_t\) имеет дискретное равномерное распределение вероятностей на \(\mathcal A\), т.е. \[\forall a\in \mathcal A: P(x_t \equiv a) = \frac{1}{|\mathcal A|}= \frac{1}{N}.\]

Из определения прямо вытекают следующие свойства:

  1. Распределение величины случайного вектора, составленного из произвольных фиксированных элементов РРСП является равномерным.
  2. Воспроизводимость при прореживании. При исключении произвольных элементов из РРСП, получается новая РРСП.
  3. Воспроизводимость при суммировании. Если \(\{x_i\}\) – РРСП, \(x_i\in\mathcal A\), и \(\{\xi_i\}\) – произвольная последовательность, не зависящая от \(\{x_i\}\), то \(\{x_i+\xi_i\mod |\mathcal A|\},\) – РРСП.
  4. Если \(\{x_i\}\) – РРСП, \(x_i \in \mathcal A\), то \(\forall n \in \mathbb N\) и \(X_n = \{x_1, x_2, \ldots, x_n\}\) – конечной подпоследовательности \(\{x_i\}\), взаимная информация \(I(x_{n+1}; X_n) = 0\), т.е. для любого алгоритма прогнозирования \(f: \mathcal A^n \to \mathcal A,\) вероятность “угадывания” следующего элемента последовательности по предыдущим не лучше случая, \(P(f(X_n) \equiv x_{n+1} | X_n) \le |\mathcal A|^{-1}.\)

Генераторы РРСП

Генератор РРСП
устройство, позволяющее по запросу получить \(n\) элементов РРСП \(\{x_1,\ldots,x_n\}\), \(x_i \in \mathcal A\), \(n\in \mathbb N\). Элементы \(x_i\) называются случайными числами.

Существует три типа генераторов РРСП:

  • Физический
  • Табличный
  • Программный

Физические генераторы – это устройства, генерирующие РРСП на основе некого истинно случайного процесса. Например, радиоактивного распада, теплового шума и тп. Трудность заключается в том, что такие генераторы достаточно медленные и дорогостоящие.

Табличные генераторы используют большие заранее рассчитанные таблицы случайных значений. Понятно, что табличные генераторы после исчерпания таблицы становятся бесполезны.

Программные генераторы лишены вышеописанных недостатков, однако в основе своей являются детерминированными. Соответственно программный генератор РРСП генерирует не истинную РРСП, а некоторую другую последовательность, аппроксимирующую свойства РРСП. Такая имитация РРСП называется псевдослучайной, а генераторы – генераторами псевдослучайных чисел (ГПСЧ). Некоторые программные генераторы, однако, оказываются “достаточно хорошими” для повседневных криптографических применений.

Точнее, для криптографических применений ГПСЧ должен удовлетворять следующим требованиям:

  1. Не должно существовать полиномиального по времени алгоритма, который по первым \(k\) битам последовательности может предсказать \(k+1\)-й бит с вероятностью, значительно отличной от ½. Доказано1, что это является достаточным условием для прохождения любых других полиномиальных статистических тестов на случайность.
  2. Даже если внутреннее состояние генератора скомпрометировано частично или полностью, это не должно давать возможности восстановить предшествующую компрометации последовательность. Дополнительно, если при работе используется внешний источник энтропии, предсказание будущих состояний генератора на основе известного должно быть маловероятно.

Вообще, практически все ГПСЧ работают по одному принципу: на основе некоторого внутреннего состояния \(s_i \in S\), где \(S\) – конечное множество всех возможных состояний ГПСЧ, по некоторому алгоритму генерируется следующее состояние \(s_{i+1} \in S\) и очередное значение псевдослучайной последовательности \(x_i\), причём \(x_i\) однозначно определяются текущим внутренним состоянием \(s_i\).

Математически, такие ГПСЧ можно представить в виде совокупности \((S, \mu, f, U, g)\), где \(S\) – множество состояний, \(\mu\) – распределение вероятностей над \(S\), используемое для выбора начального состояния \(s_0\), \(f:S \to S\) – функция получения нового состояния на основе текущего, \(U\) – множество выходных значений, \(g : S \to U\) – функция получения очередного значения выходной последовательности.

Как правило, новое состояние получается из текущего по рекуррентной формуле \(s_{i+1} = f(s_i)\). Понятно, что если число внутренних состояний конечно, то найдётся такое число \(i\), что \(\forall j \ge i: s_j = s_{j-i}\), поэтому любая псевдослучайная последовательность такого рода будет периодической. Одной из сложностей разработки ГПСЧ является то, что при некоторых значениях начального состояния \(s_0\) длина периода может быть неожиданно мала.

Некоторые известные ГПСЧ

Назовём некоторые широко известные генераторы псевдослучайных чисел.

  • Метод середины квадрата – 1946

    Один из первых, если не первый, ГПСЧ. Разработан Джоном фон Нейманом. Представляет исключительно исторический интерес.

  • Генератор Лемера – 1951

    Один из наиболее широко известных ранних ГПСЧ. Сильно повлиял на развитие ГПСЧ.

  • Линейный конгруэнтный генератор – 1958

    Обобщение генератора Лемера. Один из наиболее известных и полно изученных генераторов.

  • Регистр сдвига с линейной обратной связью (LFSR) – 1965

    Широко известный и сильно повлиявший на развитие ГПСЧ метод.

  • Инверсный конгруэнтный метод – 1986

    Так же известен как Генератор Эйхенауэра-Лена. Модифицированный LFSR, имеющий лучшие характеристики, но значительно более медленный.

  • Генератор Парка-Миллера – 1988

    Реализация генератора Лемера. Широко используется, поскольку входит в стандартную библиотеку C.

  • Вихрь Мерсена – 1998

    Метод тесно связан с методом LFSR. В версии MT19937, вероятно, наиболее широко используемый современный генератор.

  • Xorshift – 2003

    Крайне быстрый тип LFSR.

  • Семейство алгоримтов Xoroshiro – 2018

    Модификация Xorshift. Один из самых быстрых современных алгоритмов.

Ни один из перечисленных алгоритмов, вообще говоря, не является пригодным для криптографии.

Некоторые криптографически безопасные ГПСЧ

Вообще говоря, любой криптографический блочный шифр можно превратить в ГПСЧ. Пусть длина блока составляет \(n\) бит. Тогда шифруя последовательно сообщения “0”, “1”, “2” и т.д., можно получить последовательность псевдослучайных чисел размера \(n\) бит каждое.

Аналогично возможно использовать криптографически стойкие хэш-функции (такие как, например, SHA). В таком случае “секретом” является начальное число входной последовательности.

Последовательность таких чисел в среднем можно отличить от РРСП после \(2^{n/2}\) значений, поскольку вероятность совпадения значений в РРСП становится высока, в то время как криптографический алгоритм никогда не выдаст совпадающих блоков для разных сообщений. На практике, при длине блока 128 бит, это ограничение на практике незначительно.

Существуют несколько алгоритмов, основанных на теории чисел, в частности алгоритм Блюм-Блюма- Шуба (основанный на сложности факторизации больших чисел) и алгоритм Блюма-Микали (основанный на сложности дискретного логарифма). Они, увы, крайне медленные, и поэтому редко используются на практике.

Широкое распространение имеют специально сконструированные алгоритмы, в частности:

  • Алгоритм Ярроу
  • Алгоритм ChaCha20

Метод середины квадрата

В качестве состояния берётся число из \(n\) цифр (\(n\)–чётное), и возводится в квадрат. Получается число из \(2n\) цифр. Средние \(n\) цифр используются в качестве нового состояния. Значение на выводе совпадает с состоянием (возможно по модулю).

Основные проблемы этого алгоритма заключаются в низком периоде (не более \(8^n\) для десятичных цифр). Если половина старших разрядов состояния = 0, то после некоторого количества итераций, все разряды станут равны нулю, и период будет 0. Подобная ситуация нередка.

  1. Andrew Chi-Chih Yao. Theory and applications of trapdoor functions. In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, 1982.↩︎