Шифр Хилла

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Шифр Хилла — полиграммный шифр подстановки, основанный на линейной алгебре. Лестер С. Хилл изобрел этот шифр в 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,Z2). Это

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

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

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 года, и она показывает, что Хилл несомненно понимал концепции конфузии и диффузии. Его машина не пользовалась успехом.

Примечания[править | править вики-текст]