Шифр Хилла

Хилл Сандерс Лестер

Шифр Хилла — полиграммный шифр подстановки, основанный на линейной алгебре и модульной арифметике. Изобретён американским математиком Лестером Хиллом в 1929 году. Это был первый шифр, который позволил на практике (хотя и с трудом) одновременно оперировать более чем с тремя символами. Шифр Хилла не нашёл практического применения в криптографии из-за слабой устойчивости ко взлому и отсутствия описания алгоритмов генерации прямых и обратных матриц большого размера.

История

Впервые шифр Хилла был описан в статье «Cryptography in an Algebraic Alphabet», опубликованной в журнале «The American Mathematical Monthly» в июне-июле 1929 года. В августе того же года Хилл расширил тему и выступил с речью о криптографии перед Американским математическим обществом в Боулдере, штат Колорадо. Позднее его лекция привела ко второй статье «Concerning Certain Linear Transformation Apparatus of Cryptography», которая была опубликована в журнале «The American Mathematical Monthly» в марте 1931 года. Дэвид Кан в своем труде «Взломщики кодов» так описал шифр Хилла и его место в истории криптографии: Шаблон:Начало цитаты Хилл был одним из тех, кто разработал общий и мощный метод. К тому же шифр Хилла впервые перевёл криптографию с использованием полиграмм в разряд практических дисциплин. Шаблон:Oq Шаблон:Конец цитаты

Описание шифра Хилла

Шифр Хилла является полиграммным шифром, который может использовать большие блоки с помощью линейной алгебры. Каждой букве алфавита сопоставляется число по модулю 26. Для латинского алфавита часто используется простейшая схема: A = 0, B = 1, …, Z = 25, но это не является существенным свойством шифра. Блок из n букв рассматривается как n-мерный вектор и умножается по модулю 26 на матрицу размера n × n. Если в качестве основания модуля используется число больше чем 26, то можно использовать другую числовую схему для сопоставления буквам чисел и добавить пробелы и знаки пунктуации. Элементы матрицы являются ключом. Матрица должна быть обратима в ${\mathbb{Z}}_{26}^n$, чтобы была возможна операция расшифрования.

Для n = 3 система может быть описана так:

$\{\begin{array}{c}{c}_1=k_{11}{p}_1+k_{12}{p}_2+k_{13}{p}_3(\mathrm{mod}26),\\ c_2=k_{21}{p}_1+k_{22}{p}_2+k_{23}{p}_3(\mathrm{mod}26),\\ c_3=k_{31}{p}_1+k_{32}{p}_2+k_{33}{p}_3(\mathrm{mod}26),\end{array}$

или в матричной форме:

$\left[\begin{array}{c}{c}_1\\ c_2\\ c_3\end{array}\right]=\left[\begin{array}{ccc}{k}_{11}& k_{12}& k_{13}\\ k_{21}& k_{22}& k_{23}\\ k_{31}& k_{32}& k_{33}\end{array}\right]\left[\begin{array}{c}{p}_1\\ p_2\\ p_3\end{array}\right](\mathrm{mod}26),$

или

$C=KP(\mathrm{mod}26),$

где $P$ и $C$ — векторы-столбцы высоты 3, представляющие открытый и зашифрованный текст соответственно, $K$ — матрица 3 × 3, представляющая ключ шифрования. Операции выполняются по модулю 26.

Для того, чтобы расшифровать сообщение, требуется получить обратную матрицу ключа $K^{-1}$. Существуют стандартные методы вычисления обратных матриц (см. способы нахождения обратной матрицы), но не все матрицы имеют обратную (см. обратная матрица). Матрица будет иметь обратную в том и только в том случае, когда её детерминант не равен нулю и не имеет общих делителей с основанием модуля. Если детерминант матрицы равен нулю или имеет общие делители с основанием модуля, то такая матрица не может использоваться в шифре Хилла, и должна быть выбрана другая матрица (в противном случае шифротекст будет невозможно расшифровать). Тем не менее, матрицы, которые удовлетворяют вышеприведенным условиям, существуют в изобилии.

В общем случае, алгоритм шифрования может быть выражен в следующем виде:

Шифрование: $C=E(K,P)=KP(\mathrm{mod}26)$.

Расшифрование: $P=D(K,C)=K^{-1}C(\mathrm{mod}26)=K^{-1}KP(\mathrm{mod}26)=P$.

Пример

В следующем примере используются латинские буквы от A до Z, соответствующие им численные значения приведены в таблице.

A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

Шифрование

Рассмотрим сообщение «ACT» и представленный ниже ключ (GYBNQKURP в буквенном виде):

$K=\left[\begin{array}{ccc}6& 24& 1\\ 13& 16& 10\\ 20& 17& 15\end{array}\right].$

Данная матрица обратима, так как её детерминант не равен нулю и не имеет общих делителей с основанием модуля. Опасность того, что детерминант матрицы ключа будет иметь общие делители с основанием модуля, может быть устранена путём выбора простого числа в качестве основания модуля. Например, в более удобном варианте шифра Хилла в алфавит добавляют 3 дополнительных символа (пробел, точка и знак вопроса), чтобы увеличить основание модуля до 29.

Так как букве «A» соответствует число 0, «C» — 2, «T» — 19, то сообщение — это вектор

$P_1=\left[\begin{array}{c}0\\ 2\\ 19\end{array}\right].$

Тогда зашифрованный вектор будет

$C_1=K{P}_1(\mathrm{mod}26)=\left[\begin{array}{ccc}6& 24& 1\\ 13& 16& 10\\ 20& 17& 15\end{array}\right]\left[\begin{array}{c}0\\ 2\\ 19\end{array}\right](\mathrm{mod}26)=\left[\begin{array}{c}15\\ 14\\ 7\end{array}\right].$

Вектор соответствует зашифрованному тексту «POH». Теперь предположим, что наше сообщение было «CAT»:

$P_2=\left[\begin{array}{c}2\\ 0\\ 19\end{array}\right].$

Теперь зашифрованный вектор будет

$C_2=K{P}_2(\mathrm{mod}26)=\left[\begin{array}{ccc}6& 24& 1\\ 13& 16& 10\\ 20& 17& 15\end{array}\right]\left[\begin{array}{c}2\\ 0\\ 19\end{array}\right](\mathrm{mod}26)=\left[\begin{array}{c}5\\ 8\\ 13\end{array}\right].$

Этот вектор соответствует зашифрованному тексту «FIN». Видно, что каждая буква шифротекста сменилась. Шифр Хилла достиг Шаблон:Не переведено 5 по Шеннону, и n-размерный шифр Хилла может достигать диффузии n символов за раз.

Расшифрование

Обратная матрица ключа:

$K^{-1}(\mathrm{mod}26)=\left[\begin{array}{ccc}8& 5& 10\\ 21& 8& 21\\ 21& 12& 8\end{array}\right].$

Возьмём зашифрованный текст из предыдущего примера «POH»:

$P_1=K^{-1}{C}_1(\mathrm{mod}26)=\left[\begin{array}{ccc}8& 5& 10\\ 21& 8& 21\\ 21& 12& 8\end{array}\right]\left[\begin{array}{c}15\\ 14\\ 7\end{array}\right](\mathrm{mod}26)=\left[\begin{array}{c}0\\ 2\\ 19\end{array}\right].$

Этот вектор соответствует сообщению «ACT».

Криптостойкость

Стандартный шифр Хилла уязвим для атаки по выбранному открытому тексту, потому что в нём используются линейные операции. Криптоаналитик, который перехватит $n^2$ пар символ сообщения/символ шифротекста сможет составить систему линейных уравнений, которую обычно несложно решить. Если окажется, что система не решаема, то необходимо всего лишь добавить ещё несколько пар символ сообщения/символ шифротекста. Такого рода расчёты средствами обычных алгоритмов линейной алгебры требует совсем немного времени. В связи с этим для увеличения криптостойкости в него должны быть добавлены какие-либо нелинейные операции. Комбинирование линейных операций, как в шифре Хилла, и нелинейных шагов привело к созданию подстановочно-перестановочной сети (например, сеть Фейстеля). Поэтому с определённой точки зрения можно рассматривать современные блочные шифры как вид полиграммных шифров.

Длина ключа

Длина ключа — это двоичный логарифм от количества всех возможных ключей. Существует $26^{n^2}$ матриц размера n × n. Значит, ${\log }_2(26^{n^2})\approx 4,7n^2$ — верхняя грань длины ключа для шифра Хилла, использующего матрицы n × n. Это только верхняя грань, поскольку не каждая матрица обратима, а только такие матрицы могут быть ключом. Количество обратимых матриц может быть рассчитано при помощи Китайской теоремы об остатках. Матрица обратима по модулю 26 тогда и только тогда, когда она обратима и по модулю 2 и по модулю 13.

Количество обратимых по модулю 2 и 13 матриц размера n × n равно порядку линейной группы GL(n, Z₂) и GL(n, Z₁₃) соответственно:

$|K_1|=2^{n^2}(1-1/2)(1-1/2^2)\dots (1-1/2^n),$

$|K_2|=13^{n^2}(1-1/13)(1-1/13^2)\dots (1-1/13^n).$

Количество обратимых по модулю 26 матриц равно произведению этих чисел:

$|K|=26^{n^2}(1-1/2)(1-1/2^2)\dots (1-1/2^n)(1-1/13)(1-1/13^2)\dots (1-1/13^n).$

Кроме того, будет разумно избегать слишком большого количества нулей в матрице-ключе, так как они уменьшают диффузию. В итоге получается, что эффективное пространство ключей стандартного шифра Хилла составляет около $4,64n^2-1,7$. Для шифра Хилла 5 × 5 это составит приблизительно 114 бит. Очевидно, полный перебор — не самая эффективная атака на шифр Хилла.

Механическая реализация

Шифровальная машина Хилла

При работе с двумя символами за раз шифр Хилла не предоставляет никаких конкретных преимуществ перед шифром Плэйфера и даже уступает ему по криптостойкости и простоте вычислений на бумаге. По мере увеличения размерности ключа шифр быстро становится недоступным для расчётов на бумаге человеком. Шифр Хилла размерности 6 был реализован механически. Хилл с партнёром получили патент на устройство (Шаблон:US patent), которое выполняло умножение матрицы 6 × 6 по модулю 26 при помощи системы шестерёнок и цепей. Расположение шестерёнок (а значит, и ключ) нельзя было изменять для конкретного устройства, поэтому в целях безопасности рекомендовалось тройное шифрование. Такая комбинация была очень сильной для 1929 года, и она показывает, что Хилл несомненно понимал концепции конфузии и диффузии. Однако устройство было довольно медленное, поэтому во Второй мировой войне машины Хилла были использованы только для шифрования трёхсимвольного кода радиосигналов.

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга