micalis_generator.tex

\subsection{Генератор Микали}\index{генератор!Микали}

Другой пример -- генератор Микали.

Так же выбирают большие простые числа $p,q$ с битовой длиной не менее 512, вычисляют число $n = pq$. Находят функцию Эйлера $\varphi(n) = (p-1) (q-1)$ и задают целое число $e$ такое, что наибольший общий делитель $\gcd(e, \varphi(n)) = 1$. С помощью генератора случайных чисел выбирают $0 \leq x_{0} \leq n-1$. Вычисляют
\[ \begin{array}{l}
    x_1 = x_0^e \mod n, \\
    x_2 = x_1^e \mod n, \\
    \dots \\
    x_N = x_{N-1}^e \mod n.
\end{array} \]
Чтобы уменьшить сложность вычислений, в значениях $x_i$ оставляют $l$ младших разрядов, причём $l \leq \log_2 \log_2 N$. Последовательность ключей получают в виде
\[ \begin{array}{l}
    k_1 = x_1^2 \mod 2, \\
    k_2 = x_2^2 \mod 2, \\
    \dots \\
    k_N = x_N^2 \mod 2. \\
\end{array} \]

Как и генератор BBS, генератор Микали -- криптостойкий, для его взлома требуется разложить число $n$ на множители. Недостаток -- маленькая скорость.