bbs_generator.tex

\subsection{Генератор BBS}
\selectlanguage{russian}

Имеются примеры <<хороших>> генераторов, вырабатывающих криптографически стойкие последовательности, например генератор Blum-Blum-Shub (BBS). Алгоритм работы состоит в следующем: выбирают большие (длиной не менее 512 бит) простые числа\index{число!простое} $p, q$, которые при делении на $4$ дают в остатке $3$. Вычисляют $n = p q$, с помощью генератора случайных чисел вырабатывают число $x_{0}$, где $1 \leq x_0 \leq n-1$ и $\gcd(x_0, n) = 1$. Далее проводят следующие вычисления:
\[ \begin{array}{l}
        x_{1} = x_{0}^{2} \mod n,\\
        x_{2} = x_{1}^{2} \mod n,\\
        \dots,\\
        x_{N} = x_{N-1}^{2} \mod n.
\end{array} \]

Для каждого вычисленного значения оставляют один младший разряд. Вычисляют двоичную псевдослучайную последовательность $k_1, k_2, k_3, \dots$ :
\[ \begin{array}{l}
        k_{1} = x_{1} \mod 2,\\
        k_{2} = x_{2} \mod 2,\\
        \dots,\\
        k_{N} = x_{N} \mod 2.
\end{array} \]

Число $a$ называется \emph{квадратичным вычетом} по модулю $n$, если для него существует квадратный корень $b$ (или два корня): $a = b^2 \mod n$. Для $p,q ~=~ 3 \mod 4$ верно утверждение, что квадратичный вычет имеет единственный корень, и операция $x \rightarrow x^2 \mod n$, применённая к элементам множества всех квадратичных вычетов $\set{QR}_n$ по модулю $n$, является перестановкой множества $\set{QR}_n$.

Полученная последовательность $x_1, x_2, x_3, \dots$ квадратичных вычетов -- периодическая ($T < |\set{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 является малая скорость генерирования битов.