Криптосистемы с открытым ключом, как правило, построены в модульной арифметике с длиной модуля от сотни до нескольких тысяч разрядов. Сложность алгоритмов оценивают как количество битовых операций в зависимости от длины. В таблице[tab:mod-binary-complexity] приведены оценки (с точностью до порядка) сложности модульных операций для простых (или «школьных») алгоритмов вычислений. На самом деле для реализации арифметики длинных чисел (сотни или тысячи двоичных разрядов) следует применять существенно более эффективные (более «хитрые») алгоритмы вычислений, использующие, например, специальный вид быстрого преобразования Фурье и другие приёмы.
Таблица 16.5 — Битовая сложность операций по модулю $n$ длиной $k= \log n$ бит
16.5.2. Возведение в степень по модулю
Рассмотрим два алгоритма возведения числа $a$ в степень $b$ по модулю $n$ (см.[127]). Оба этих алгоритма основываются на разложении показателя $b$ в двоичное представление:
algorithmhtПростая двоичная схема возведения в степень типа «слева направо»algorithmic$c := a$;
$i := k-1$$1$$c := c^2 \mod n$;
$\left( b_i == 1 \right)$$c := c \cdot a \mod n$;
$c$;
Алгоритм требует $k-1$ возведений в квадрат и $t-1$ умножений, где $t$ – количество единиц в двоичном представлении показателя степени. Так как возведение в квадрат можно сделать примерно в два раза быстрее, чем умножение на произвольное число, то, например, в криптосистеме RSA показатель степени стараются выбрать таким образом, чтобы в его двоичной записи было мало бит, отличных от нуля: $3_{10} = 11_{2}$ или $65537_{10} = 10000000000000001_{2}$.
Пример. Посчитаем с помощью простой двоичной схемы возведения в степень типа «слева направо» значение $175^{235} \mod 257$. Представим число $235$ в двоичном виде:
Ответ: 3. Потребовалось 7 возведений в квадрат и 5 умножений.
Алгоритм можно обобщить на использование произвольного основания разложения степени. Например, использование основания, представляющего собой степень двойки, будет являться методом улучшения описанной выше схемы под названием «просматривание» (англ. windowing, см.[127]). Если в качестве основания выбрать $s = 4$, то формула из примера выше для вычисления $175^{235} \mod 257$ принимает вид:
Для вычисления уже потребуется $3 \times 2 = 6$ возведений в квадрат и $3$ умножения. Но сначала потребуется вычислить значения $175^2 \mod 257$ и $175^3 \mod 257$. Для больших показателей степени $n$ выгода в количестве умножений будет очевидна.
Схема «справа налево»
Другим вариантом является схема типа «справа налево» (см. алгоритм[alg:power-mod-right-to-left]). Она также основывается на разложении показателя степени по степеням двойки[eq:power-mod-b]. Её можно представить следующей формулой:
algorithmhtПростая двоичная схема возведения в степень типа «справа налево»algorithmic$c := 1$;
$t := a$;
$i := 1$$k$$\left( b_i == 1 \right)$$c := c \cdot t \mod n$;
$t := t^2 \mod n$;
$c$.
Пример. Посчитаем с помощью простой двоичной схемы возведения в степень типа «справа налево» значение $175^{235} \mod 257$. Представим число $235$ в двоичном виде:
Пример.
В таблице[tab:extended-euclid] приведён числовой пример алгоритма для $a=136, b=36$.
$i$
$g_i$
$r_i$
$x_i$
$y_i$
$-1$
—
$136$
$1$
$0$
$136 =$
$ 1 \cdot 136$
$ + 0 \cdot 36$
$0$
—
$36$
$0$
$1$
$36 =$
$ 0 \cdot 136$
$ + 1 \cdot 36$
$1$
$3$
$28$
$+1$
$-3$
$28 =$
$+1 \cdot 136$
$ - 3 \cdot 36$
$2$
$1$
$8$
$-1$
$+4$
$8 =$
$-1 \cdot 136$
$ + 4 \cdot 36$
$3$
$3$
$4$
$+4$
$-15$
$4 =$
$+4 \cdot 136$
$ -15 \cdot 36$
$4$
$2$
$0$
—
—
—
Таблица 16.6 — Пример расширенного алгоритма Евклида для $a=136, b=36$
Найдено $x = 4, ~ y = -15, ~ d = 4$.
16.5.5. Нахождение мультипликативного обратного по модулю
Расширенный алгоритм Евклида можно использовать для вычисления обратного элемента: для заданных $a$ и $n$ найти $x, y, d = \gcd(a,n): ax + ny = d$. Пусть $a,n$ – взаимно простые, тогда:
$$\begin{array}{l}
ax + ny = 1, \\
ax \equiv 1 \mod n, \\
x \equiv a^{-1} \mod n. \\
\end{array}$$
Пример.
В таблице[tab:extended-euclid-inverse] приведён числовой пример вычисления расширенным алгоритмом Евклида для $a=142, b=33$ обратных элементов $33^{-1} \equiv -43 \mod 142$ и $142^{-1} \equiv 10 \mod 33$.
$i$
$g_i$
$r_i$
$x_i$
$y_i$
$-1$
—
$142$
$1$
$0$
$142 =$
$ 1 \cdot 142$
$ + 0 \cdot 33$
$0$
—
$33$
$0$
$1$
$33 =$
$ 0 \cdot 142$
$ + 1 \cdot 33$
$1$
$4$
$10$
$+1$
$-4$
$10 =$
$ +1 \cdot 142$
$ - 4 \cdot 33$
$2$
$3$
$3$
$-3$
$+13$
$3 =$
$ -3 \cdot 142$
$+ 13 \cdot 33$
$3$
$3$
$1$
$+10$
$-43$
$1 =$
$+10 \cdot 142$
$- 43 \cdot 33$
$4$
$3$
$0$
—
—
—
Таблица 16.7 — Пример вычисления обратных элементов $33^{-1} \equiv -43 \mod 142$ и $142^{-1} \equiv 10 \mod 33$ из уравнения $142 x + 33 y = 1$ расширенным алгоритмом Евклида
Для $k$-битового числа $n$-битовая сложность вычисления обратного элемента имеет порядок $O(k^2)$. Если известно разложение числа $n$ на множители, то по теореме Эйлера
$$ a^{-1} = a^{\varphi(n) - 1} \mod n, $$
и вычисление обратного элемента реализуется с битовой сложностью $O(k^3),~ k = \lceil \log_2 n \rceil$. Сложность вычислений по этому алгоритму можно уменьшить, если известно разложение на сомножители числа $\varphi(n) - 1$.
16.5.6. Китайская теорема об остатках
Китайская теорема об остатках (англ. Chinese Remainder Theorem, CRT), приписываемая китайскому математику Сунь Цзы (пиньинь: S
=un Z
i
, примерно IIIвекдон.э.), утверждает о существовании и единственности (с точностью до некоторого модуля) числа $x$, заданного по множеству остатков от деления на попарно взаимно простые числа $n_1, n_2, n_3, \dots, n_k$.
theorem Если натуральные числа $n_1, n_2, n_3, \dots, n_k$ попарно взаимно просты, то для любых целых $r_1, r_2, r_3, \dots, r_k$ таких, что $0 \leq r_i < n_i$, найдётся число $x$, которое при делении на $n_i$ даёт остаток $r_i$ для всех $1 \leq i \leq k$. Более того, любые два таких числа $x_1$ и $x_2$, имеющие одинаковые остатки $r_1, r_2, \dots, r_k$, удовлетворяют сравнению:
$$ \begin{array}{l}
x_1 \equiv x_2 \mod n, \\
n = n_1 \times n_2 \times \dots \times n_k.
\end{array} $$
Формула, приведённая в труде другого китайского математика Циня Цзюшао (пиньинь: Q́in Ji
u
sh́ao, XIIIвекн.э.), позволяет найти искомое число:
$$ \begin{array}{l}
x = \sum\limits_{i=1}^k r_i \cdot e_i, \\
e_i = \frac{n}{n_i} \cdot \left( \left(\frac{n}{n_i}\right)^{-1} \mod n_i \right), i = 1, \dots, k.
\end{array} $$
Китайская теорема об остатках позволяет рассматривать набор попарно взаимно простых чисел $n_1, n_2, n_3, \dots, n_k$ как некоторый «базис», в котором число $0 \leq x < n$ можно задать с помощью «координат» $r_1, r_2, r_3, \dots, r_k$. При этом операции сложения и умножения чисел можно выразить через операции сложения и умножения соответствующих остатков:
$$ \begin{array}{l}
\forall a, b, c, \begin{array}{l}
a_i = a \mod n_i, \\
b_i = b \mod n_i, \\
c_i = c \mod n_i
\end{array} \Rightarrow \\
\left( c \equiv a + b \mod n \right) \Leftrightarrow \left( c_i \equiv a_i + b_i \mod n_i, i = 1, \dots, k \right), \\
\left( c \equiv a \times b \mod n \right) \Leftrightarrow \left( c_i \equiv a_i \times b_i \mod n_i, i = 1, \dots, k \right).
\end{array} $$
Сложность перехода в векторную форму имеет порядок
$$ O( \lceil \log_2 n \rceil ^2). $$
Теорема используется для решения систем линейных модульных уравнений и для ускорения вычислений.
Пусть битовая длина $n$ равна $l$, и пусть все $n_i$ имеют одинаковую битовую длину $k / r$. Тогда операция умножения в векторном виде будет в
$$ \frac{l^2}{r \left( l \middle/ r \right)^2 } = r $$
раз быстрее.
Операция $c = m^e \mod n$ занимает $O(l^3)$ битовых операций. Если перейти к вычислениям по модулям $n_i$, то возведение в степень можно вычислить в
$$ \frac{l^3}{r \left( l \middle/ r \right)^3 } = r^2 $$
раз быстрее, коэффициенты результирующего вектора равны
$$ c_i ~=~ \left( m \mod n_i \right)^{e \mod \varphi(n_i)} \mod n_i, ~ i = 1, \dots, k. $$
16.5.7. Решение систем линейных уравнений
Пример.
Решим, для примера, систему линейных уравнений. Применим CRT и а) для разложения одного уравнения по составному модулю на систему по взаимно простым модулям, и б) для нахождения конечного решения системы уравнений:
$$
\begin{cases}
9 x \equiv 8 \mod 11, \\
5 x \equiv 7 \mod 12, \\
x \equiv 5 \mod 6, \\
122 x \equiv 118 \mod 240; \\
\end{cases}
\Rightarrow ~~
\begin{cases}
x \equiv 8 \cdot 9^{-1} \mod 11, \\
x \equiv 7 \cdot 5^{-1} \mod 12, \\
x \equiv 5 \mod 6, \\
x \equiv 59 \cdot 61^{-1} \mod 120; \\
\end{cases}
\Rightarrow
$$
$$
\Rightarrow ~~
\begin{cases}
x \equiv -4 \mod 11, \\
x \equiv -1 \mod 12, \\
x \equiv -1 \mod 6, \\
x \equiv -1 \mod 120; \\
\end{cases}
\Rightarrow ~~
\begin{cases}
x \equiv -4 \mod 11, \\
\begin{cases}
x \equiv -1 \mod 3, \\
x \equiv -1 \mod 4, \\
\end{cases} \\
\begin{cases}
x \equiv -1 \mod 3, \\
x \equiv -1 \mod 2, \\
\end{cases} \\
\begin{cases}
x \equiv -1 \mod 8, \\
x \equiv -1 \mod 3, \\
x \equiv -1 \mod 5; \\
\end{cases} \\
\end{cases}
\Rightarrow
$$
$$
\Rightarrow ~~
\begin{cases}
x \equiv -4 \mod 11, \\
x \equiv -1 \mod 3, \\
x \equiv -1 \mod 8, \\
x \equiv -1 \mod 5. \\
\end{cases}
$$
Все модули попарно взаимно простые, поэтому применима китайская теорема об остатках: