Шифр Хилла

Шифр Хилла — полиграммный шифр подстановки, основанный на линейной алгебре. Лестер С. Хилл изобрел этот шифр в 1929, и это был первый шифр, который позволял на практике (хотя и с трудом) оперировать более чем с тремя символами за раз. Последующее обсуждение шифра предполагает начальные знания матриц.

Шифрование

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

В следующих примерах используются латинские буквы от 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

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

$\begin{pmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \end{pmatrix}$

Так как букве 'D' соответствует число 3, 'O' — 14, 'G' — 6, то сообщение — это вектор

$\begin{pmatrix} 3 \\ 14 \\ 6 \end{pmatrix}$

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

$\begin{pmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \end{pmatrix} \begin{pmatrix} 3 \\ 14 \\ 6 \end{pmatrix} = \begin{pmatrix} 360 \\ 323 \\ 388 \end{pmatrix} \equiv \begin{pmatrix} 22 \\ 11 \\ 24 \end{pmatrix} \pmod{26}$

что соответствует шифротексту 'WLY'. Теперь предположим, что наше сообщение было 'GOD' или

$\begin{pmatrix} 6 \\ 14 \\ 3 \end{pmatrix}$

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

$\begin{pmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \end{pmatrix} \begin{pmatrix} 6 \\ 14 \\ 3 \end{pmatrix} \equiv \begin{pmatrix} 375 \\ 332 \\ 403 \end{pmatrix} \equiv \begin{pmatrix} 11 \\ 20 \\ 13 \end{pmatrix} \pmod{26}$

что соответствует шифротексту 'LUN'. Видно, что каждая буква шифротекста сменилась. Шифр Хилла достиг диффузии по Шеннону, и n-размерный шифр Хилла может достигать диффузии n символов за раз.

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

Для того, чтобы расшифровать сообщение, необходимо обратить шифротекст обратно в вектор и затем просто умножить на обратную матрицу ключа (IFKVIVVMI в буквенном виде). (Существуют стандартные методы вычисления обратных матриц, смотрите способы нахождения обратной матрицы для подробностей.) В $\mathbb{Z}_{26}^n$ обратная матрица к использованной в примере шифрования будет

$\begin{pmatrix} 8 & 5 & 10 \\ 21 & 8 & 21 \\ 21 & 12 & 8 \end{pmatrix}$

Возьмем шифротекст из предыдущего примера 'WLY'. Тогда мы получим

$\begin{pmatrix} 8 & 5 & 10 \\ 21 & 8 & 21 \\ 21 & 12 & 8 \end{pmatrix} \begin{pmatrix} 22 \\ 11 \\ 24 \end{pmatrix} \equiv \begin{pmatrix} 471 \\ 1054 \\ 786 \end{pmatrix} \equiv \begin{pmatrix} 3 \\ 14 \\ 6 \end{pmatrix} \pmod{26}$

что возвращает нас к сообщению 'DOG', как мы и рассчитывали.

Необходимо обсудить некоторые сложности, связанные с выбором шифрующей матрицы. Не все матрицы имеют обратную (см. обратная матрица). Матрица будет иметь обратную в том и только в том случае, когда ее детерминант не равен нулю и не имеет общих делителей с основанием модуля. Таким образом, если мы работаем с основанием модуля 26 как в примерах выше, то детерминант должен быть ненулевым и не делиться на 2 и 13. Если детерминант матрицы равен нулю или имеет общие делители с основанием модуля, то такая матрица не может использоваться в шифре Хилла, и должна быть выбрана другая матрица (в противном случае шифротекст будет невозможно расшифровать). Тем не менее, матрицы, которые удовлетворяют вышеприведенным условиям, существуют в изобилии.

Детерминант матрицы из примера:

$\begin{vmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \end{vmatrix} \equiv 6(16\cdot15-10\cdot17)-24(13\cdot15-10\cdot20)+1(13\cdot17-16\cdot20) \equiv 441 \equiv 25 \pmod{26}$

Итак, детерминант равен 25 по модулю 26. Так число 25 не имеет общих делителей с числом 26, то матрица с таким детерминантом может использоваться в шифре Хилла.

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

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

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

Длина ключа

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

$2^{n^2}(1-1/2)(1-1/2^2)\cdots(1-1/2^n).$

Аналогично, количество обратимых по модулю 13 матриц (т. е. порядок GL(n,Z₁₃)) равно

$13^{n^2}(1-1/13)(1-1/13^2)\cdots(1-1/13^n).$

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

$26^{n^2}(1-1/2)(1-1/2^2)\cdots(1-1/2^n)(1-1/13)(1-1/13^2)\cdots(1-1/13^n).$

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

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

При работе с двумя символами за раз, шифр Хилла не предоставляет никаких конкретных преимуществ перед шифром Плэйфера, и даже уступает ему по криптостойкости и простоте вычислений на бумаге. По мере увеличения размерности ключа шифр быстро становится недоступным для расчетов на бумаге человеком. Шифр Хилла размерности 6 был реализован механически. Хилл с партнером получили патент на это устройство (U.S. Patent 1 845 947), которое выполняло умножение матрицы 6 × 6 по модулю 26 при помощи системы шестеренок и цепей. Расположение шестеренок (а значит и ключ) нельзя было изменять для конкретного устройства, поэтому в целях безопасности рекомендовалось тройное шифрование. Такая комбинация была очень сильной для 1929 года, и она показывает, что Хилл несомненно понимал концепции конфузии и диффузии. Его машина не пользовалась успехом.

Примечания

Для улучшения этой статьи желательно?: Викифицировать статью. Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.