bbs_generator.tex

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

Имеются примеры <<хороших>> генераторов, вырабатывающих криптографически стойкие последовательности, например, генератор \textbf{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$. Далее проводят следующие вычисления:
\[ \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(\phi(p-1), \phi(q-1))$, где $\phi(n)$ -- функция Эйлера.

Полученная последовательность ключей является криптографически стойкой. Доказано, что для <<взлома>> (т.е. определения следующего символа с вероятностью отличной от $\frac{1}{2}$), требуется разложить число $n=pq$ на множители. Разложение числа на множители считается трудной задачей, все известные алгоритмы не являются полиномиальными по $\log_2 n$.

Оказывается, что если вместо одного последнего бита $k_i = x_i \mod 2$ брать $O(\log_2 \log_2 n)$ последних битов рассмотренного выше генератора $x_i$, то полученная последовательность останется криптостойкой.

Большой недостаток генератора BBS -- малая скорость генерирования бит.