crypto-random.tex

\section[КСГПСЧ]{Криптографически стойкие генераторы псевдослучайных чисел}\label{section-crypto-random}\index{генератор!криптографически-стойкий}
\selectlanguage{russian}

Итак, просто генератором псевдослучайных чисел мы называем функцию $g$ вида
	\[g: \left\{0, 1\right\}^{n} \to \left\{0, 1\right\}^{q\left(n\right)},\]
вычислимую за полиномиальное время, результатом работы которой является последовательность чисел, обладающая свойствами случайной.

Были рассмотрены два генератора (линейный конгруэнтный генератор в разделе~\ref{section-linear-congruential-generator} и генератор на основе РСЛОС в разделе~\ref{section-lfsr}). Однако они обладают фундаментальными недостатками, которые не дают использовать их в криптографии. Зная определённое число предыдущих значений выхода генератора (и его внутреннее устройство), криптоаналитик имеет возможность предсказать следующие элементы последовательности. Избежать этого можно только увеличением размера внутреннего состояния.

Пусть $b \left( g \right)$ -- число предыдущих бит, которые необходимо знать криптоаналитику для восстановления внутреннего состояния и параметров генератора (и, следовательно, для предсказания дальнейшей последовательности). И для линейного конгруэнтного генератора\footnote{Для получения параметров \texttt{a} и \texttt{c}.}, и для генератора на основе РСЛОС функция $b (g)$ является линейной функцией от размера внутреннего состояния $size\left( g \right)$ в битах:
\[\begin{array}{l}
	b \left( LCG \right) = 3 \cdot size\left( g \right), \\
	b \left( LFSR \right) = 2 \cdot size\left( g \right). \\
\end{array}\]

То есть, если мы решим увеличить размер внутреннего состояния для защиты от криптоаналитика, это приведёт не более чем к линейному росту затрат последнего на необходимые вычисления (сравните это с экспоненциальным ростом затрат криптоаналитика при увеличении размера ключа для блочных шифров). Поэтому для использования в криптографии к генераторам псевдослучайных чисел предъявляются дополнительные требования.

\emph{Криптографически стойким генератором псевдослучайных чисел} будем называть функцию $g$ вида
	\[g: \left\{0, 1\right\}^{n} \to \left\{0, 1\right\}^{q\left(n\right)},\] 
вычислимую за полиномиальное время, результатом работы которой является последовательность чисел, удовлетворяющая тесту на следующий бит: не должно существовать полиномиального алгоритма, который по $k$ битам последовательности будет предсказывать следующий с вероятностью более $1/2$.

В 1982 году Эндрю Яо (\langen{Andrew Chi-Chih Yao},~\cite{Yao:1982}) доказал, что любой генератор, проходящий тест на следующий бит, сможет пройти и любые другие статистические полиномиальные тесты на случайность.

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