3.3. Полиграммный шифр замены Хилла

Если при шифровании преобразуются более двух букв открытого текста, то шифр называется полиграммным. Первый полиграммный шифр предложил Лестер Хилл в 1929 году (англ. Lester Sanders Hill, [46, 47]). Это был первый шифр, который позволял оперировать более чем тремя символами за один такт.

В шифре Хилла текст предварительно преобразуют в цифровую форму и разбивают на последовательности (блоки) по $n$ последовательных цифр. Такие последовательности называются $n$-граммами. Выбирают обратимую по модулю $m$ $(n \times n)$-матрицу $\mathbf{A} = (a_{ij})$, где $m$ – число букв в алфавите. Выбирают случайный $n$-вектор $\mathbf{f} = (f_1, \dots, f_n)$. После чего $n$-грамма открытого текста $\mathbf{x} = (x_1, x_2, \dots, x_n)$ заменяется $n$-граммой шифрованного текста $\mathbf{y} = (y_1, y_2, \dots, y_n)$ по формуле:

$$ \mathbf{y} = \mathbf{x} \mathbf{A} + \mathbf{f} \mod m. $$

Расшифрование проводится по правилу:

$$ \mathbf{x} = (\mathbf{y} - \mathbf{f}) \mathbf{A}^{-1} \mod m. $$

Пример. Приведём пример шифрования с помощью шифра Хилла. Преобразуем английский алфавит в числовую форму (m = 26) следующим образом:

$$ \text{a} \rightarrow 0, ~ \text{b} \rightarrow 1, ~ \text{c} \rightarrow 2, ~ \dots, ~ \text{z} \rightarrow 25. $$

Выберем для примера $n = 2$. Запишем фразу «Wheatstone was the inventor» из предыдущего примера (первая строка таблицы). Каждой букве поставим в соответствие её номер в алфавите (вторая строка):

w, he,at,st,on,ew,as,th,ei,nv,en,to,r
22, 74,019,1819,1413,422,018,197,48,1321,413,1914,17

Выберем матрицу шифрования $A$ в виде:

$$ \mathbf{A} = \left( \begin{array}{cc} 5 & 8 \\ 3 & 5 \\ \end{array} \right). $$

Эта матрица обратима по ${\operatorname{mod}}26$, так как её определитель равен $1$ и взаимно прост с числом букв английского алфавита $m=26$. Обратная матрица равна:

$$ \mathbf{A}^{-1} = \left( \begin{array}{cc} 5 & 18 \\ 23 & 5 \end{array} \right) \mod 26. $$

Выберем вектор $\mathbf{f} = (4, 2)$. Первая числовая пара открытого текста $\mathbf{x} = (\text{w}, \text{h}) = (22, 7)$ зашифрована в виде:

$$ \mathbf{y} = \mathbf{x} \mathbf{A} + \mathbf{f} = (22, 7) \left( \begin{array}{cc} 5 & 8 \\ 3 & 5 \end{array} \right) + (4, 2) = (14, 3) \mod 26 $$

или в буквенном виде $(\text{o}, \text{d})$.

Повторяя вычисления для всех пар, получим полный шифрованный текст в числовом виде (третья строка) или в буквенном виде (четвёртая строка):

w, he, at, st, on, ew, as, th, ei, nv, en, to, r
22, 74, 019, 1819, 1413, 422, 018, 197, 48, 1321, 413, 1914, 17
14, 324, 229, 213, 923, 110, 812, 1919, 2318, 311, 1513, 202, 19
o, dy, wj, vd, jx, bk, im, tt, xs, dl, pn, uc, t

Криптосистема Хилла уязвима к частотному криптоанализу, который основан на вычислении частот последовательностей символов. Рассмотрим пример «взлома» простого варианта криптосистемы Хилла.

Пример. В английском языке $m = 26$,

$$ a \rightarrow 0, ~ b \rightarrow 1, ~ \dots, ~ z \rightarrow 25. $$

При шифровании использована криптосистема Хилла с матрицей второго порядка c нулевым вектором $\mathbf{f}$. Наиболее часто встречающиеся в шифртексте биграммы – RH и NI, в то время как в исходном языке – TH и HE (артикль THE). Найдём матрицу секретного ключа, составив уравнения

$$ \begin{array}{l} R = 17 = -9 \mod 26, ~~ H = 7 \mod 26, ~~ N = 13 \mod 26, \\ I = 8 \mod 26, ~~ T = 19 = -7 \mod 26, ~~ E=4 \mod 26; \\ \end{array} $$
$$ \left( \begin{array}{cc} \text{R} & \text{H} \\ \text{N} & \text{I} \end{array} \right) = \left( \begin{array}{cc} \text{T} & \text{H} \\ \text{H} & \text{E} \end{array} \right) \cdot \left( \begin{array}{cc} k_{1,1} & k_{1,2} \\ k_{2,1} & k_{2,2} \end{array} \right) \mod 26; $$
$$ \left( \begin{array}{cc} -9 & 7 \\ 13 & 8 \end{array} \right) = \left( \begin{array}{cc} -7 & 7 \\ 7 & 4 \end{array} \right) \cdot \left( \begin{array}{cc} k_{1,1} & k_{1,2} \\ k_{2,1} & k_{2,2} \end{array} \right) \mod 26. $$

Стоит обратить внимание на то, что числа 4, 8, 13 не имеют обратных элементов по модулю 26.

$$ D = \det \left( \begin{array}{cc} -7 & 7 \\ 7 & 4 \end{array} \right) = -7 \cdot 4 - 7 \cdot 7 = 1 \mod 26. $$
$$ \left( \begin{array}{cc} -7 & 7 \\ 7 & 4 \end{array} \right)^{-1} = D^{-1} \left( \begin{array}{cc} 4 & -7 \\ -7 & -7 \end{array} \right) = \left( \begin{array}{cc} 4 & -7 \\ -7 & -7 \end{array} \right) \mod 26. $$
$$ \left( \begin{array}{cc} k_{1,1} & k_{1,2} \\ k_{2,1} & k_{2,2} \end{array} \right) = \left( \begin{array}{cc} 4 & -7 \\ -7 & -7 \end{array} \right) \cdot \left( \begin{array}{cc} -9 & 7 \\ 13 & 8 \end{array} \right) = $$
$$ = \left( \begin{array}{cc} 3 & -2 \\ -2 & -1 \end{array} \right) \mod 26. $$

Найденный секретный ключ

$$ \left( \begin{array}{cc} \text{D} & \text{Y} \\ \text{Y} & \text{Z} \end{array} \right). $$