Свойства:

1. \(\forall n \in \mathbb N, 1 \le t_1 < t_2 < \ldots < t_n \in \mathbb N, \vect x = \{x_{t_1}, x_{t_2}, \ldots, x_{t_n}\}:\) \(P(\vect x) = \frac{1}{|\mathcal A|^n}\)
2. Воспроизводимость при прореживании. При исключении произвольных элементов из РРСП, получается новая РРСП.
3. Воспроизводимость при суммировании. Для произвольной последовательности \(\{\xi_i\}\), не зависящей от \(\{x_i\}\), \(\{x_i+\xi_i\mod |\mathcal A|\}\) образует РРСП.
4. \(\forall n \in \mathbb N, 1 \le t_1 < t_2 < \ldots < t_n \in \mathbb N,:\) \(I(x_{t_n}; x_{t_1} \ldots x_{t_{n-1}}) = 0\)
5. (следствие 4) \(\forall f: \mathcal A^n \to \mathcal A,\) \(a = f(x_{t_1} \ldots x_{t_{n-1}}),\) \(P(x_{t_n} = a | x_{t_1} \ldots x_{t_{n-1}}) \le P(x_{t_n} = a) = |\mathcal A|^{-1}.\)

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

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

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

Три типа:

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

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

Требования к ГПСЧ для криптографии:

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

Принцип:

• \(S\) – конечное множество всех возможных состояний ГПСЧ
• внутреннее состояние \(s_i \in S\)
• следующее состояние \(s_{i+1} \in S\), \(s_{i+1}=f(s_i, \ldots)\)
• очередное значение \(x_i = g(s_i)\)

Математически, ГПСЧ есть \((S, \mu, f, U, g)\)

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

• Поскольку \(s_{i+1} = f(s_i),\) \(\exists i \le |S|: \forall j \ge i: s_j = s_{j-i}\)
• ПСП – периодическая
• Сложность: длина периода может быть неожиданно мала

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

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

Специализированные алгоритмы на основе теории чисел:

• алгоритм Блюм-Блюма-Шуба – на основе факторизации больших чисел
• алгоритм Блюма-Микали – на основе дискретного логарифма

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

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

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

• \(s_0 = \overline {a^{(0)}_n \ldots a^{(0)}_1}\) – число \(n\) цифр, \(n\) – чётное
• \(q_i=s_i^2 = \overline {b^{(i)}_{2n} \ldots b^{(i)}_1}\)
• \(s_{i+1} = \overline {b^{(i)}_{3n/2} \ldots b^{(i)}_{n/2}}\)