Итак, просто генератором псевдослучайных чисел мы называем функцию $g$ вида
вычислимую за полиномиальное время, результатом работы которой является последовательность чисел, обладающая свойствами случайной.
Были рассмотрены два генератора (линейный конгруэнтный генератор в разделе 6.1 и генератор на основе РСЛОС в разделе 6.2). Однако они обладают фундаментальными недостатками, которые не дают использовать их в криптографии. Зная определённое число предыдущих значений выхода генератора (и его внутреннее устройство), криптоаналитик имеет возможность предсказать следующие элементы последовательности. Избежать этого можно только увеличением размера внутреннего состояния.
Пусть $b \left( g \right)$ – число предыдущих бит, которые необходимо знать криптоаналитику для восстановления внутреннего состояния и параметров генератора (и, следовательно, для предсказания дальнейшей последовательности). И для линейного конгруэнтного генератора
, и для генератора на основе РСЛОС функция $b (g)$ является линейной функцией от размера внутреннего состояния $size\left( g \right)$ в битах:
То есть, если мы решим увеличить размер внутреннего состояния для защиты от криптоаналитика, это приведёт не более чем к линейному росту затрат последнего на необходимые вычисления (сравните это с экспоненциальным ростом затрат криптоаналитика при увеличении размера ключа для блочных шифров). Поэтому для использования в криптографии к генераторам псевдослучайных чисел предъявляются дополнительные требования.
Криптографически стойким генератором псевдослучайных чисел будем называть функцию $g$ вида
вычислимую за полиномиальное время, результатом работы которой является последовательность чисел, удовлетворяющая тесту на следующий бит: не должно существовать полиномиального алгоритма, который по $k$ битам последовательности будет предсказывать следующий с вероятностью более $1/2$.
В 1982 году Эндрю Яо (англ. Andrew Chi-Chih Yao, [111]) доказал, что любой генератор, проходящий тест на следующий бит, сможет пройти и любые другие статистические полиномиальные тесты на случайность.
Как и в случае с блочными шифрами, да и с криптографией вообще, под криптографической стойкостью конкретных алгоритмов в 99 случаев стоит понимать не принципиальное отсутствие, а неизвестность конкретных алгоритмов, которые могут предсказать выход генератора за полиномиальное время. Для тех генераторов, которые считались криптографически стойкими 20 лет назад, сегодня могут уже существовать алгоритмы для предсказания следующего элемента последовательности.
Имеются примеры «хороших» генераторов, вырабатывающих криптографически стойкие последовательности, например генератор Blum-Blum-Shub (BBS). Алгоритм работы состоит в следующем: выбирают большие (длиной не менее 512 бит) простые числа $p, q$, которые при делении на $4$ дают в остатке $3$. Вычисляют $n = p q$, с помощью генератора случайных чисел вырабатывают число $x_{0}$, где $1 \leq x_0 \leq n-1$ и $\gcd(x_0, n) = 1$. Далее проводят следующие вычисления:
Для каждого вычисленного значения оставляют один младший разряд. Вычисляют двоичную псевдослучайную последовательность $k_1, k_2, k_3, \dots$ :
Число $a$ называется квадратичным вычетом по модулю $n$, если для него существует квадратный корень $b$ (или два корня): $a = b^2 \mod n$. Для $p,q ~=~ 3 \mod 4$ верно утверждение, что квадратичный вычет имеет единственный корень, и операция $x \rightarrow x^2 \mod n$, применённая к элементам множества всех квадратичных вычетов ${\mathbb{QR}}_n$ по модулю $n$, является перестановкой множества ${\mathbb{QR}}_n$.
Полученная последовательность $x_1, x_2, x_3, \dots$ квадратичных вычетов – периодическая ($T < |{\mathbb{QR}}_n|$). Чтобы её период для случайного $x_0$ с большой вероятностью оказался большим, числа $p,q$ выбирают с условием малого $\gcd(\varphi(p-1), \varphi(q-1))$, где $\varphi(n)$ – функция Эйлера.
Полученная последовательность ключей является криптографически стойкой. Доказано, что для «взлома» (то есть определения следующего символа с вероятностью, большей $\frac{1}{2}$) требуется разложить число $n=pq$ на множители. Разложение числа на множители считается трудной задачей, все известные алгоритмы не являются полиномиальными по $\log_2 n$.
Оказывается, что если вместо одного последнего бита $k_i = x_i \mod 2$ брать $O(\log_2 \log_2 n)$ последних битов рассмотренного выше генератора $x_i$, то полученная последовательность останется криптостойкой.
Большим недостатком генератора BBS является малая скорость генерирования битов.