Русская Википедия:Шифр Хилла
Шифр Хилла — полиграммный шифр подстановки, основанный на линейной алгебре и модульной арифметике. Изобретён американским математиком Лестером Хиллом в 1929 году. Это был первый шифр, который позволил на практике (хотя и с трудом) одновременно оперировать более чем с тремя символами. Шифр Хилла не нашёл практического применения в криптографии из-за слабой устойчивости ко взлому и отсутствия описания алгоритмов генерации прямых и обратных матриц большого размера.
История
Впервые шифр Хилла был описан в статье «Cryptography in an Algebraic Alphabet»[1], опубликованной в журнале «The American Mathematical Monthly» в июне-июле 1929 года. В августе того же года Хилл расширил тему и выступил с речью о криптографии перед Американским математическим обществом в Боулдере, штат Колорадо[2]. Позднее его лекция привела ко второй статье «Concerning Certain Linear Transformation Apparatus of Cryptography»[3], которая была опубликована в журнале «The American Mathematical Monthly» в марте 1931 года. Дэвид Кан в своем труде «Взломщики кодов» так описал шифр Хилла и его место в истории криптографии[4]: Шаблон:Начало цитаты Хилл был одним из тех, кто разработал общий и мощный метод. К тому же шифр Хилла впервые перевёл криптографию с использованием полиграмм в разряд практических дисциплин. Шаблон:Oq Шаблон:Конец цитаты
Описание шифра Хилла
Шифр Хилла является полиграммным шифром, который может использовать большие блоки с помощью линейной алгебры. Каждой букве алфавита сопоставляется число по модулю 26. Для латинского алфавита часто используется простейшая схема: A = 0, B = 1, …, Z = 25, но это не является существенным свойством шифра. Блок из n букв рассматривается как n-мерный вектор и умножается по модулю 26 на матрицу размера n × n. Если в качестве основания модуля используется число больше чем 26, то можно использовать другую числовую схему для сопоставления буквам чисел и добавить пробелы и знаки пунктуации[5]. Элементы матрицы являются ключом. Матрица должна быть обратима в <math>\mathbb{Z}_{26}^n</math>, чтобы была возможна операция расшифрования[6][7].
Для n = 3 система может быть описана так:
- <math>
\begin{cases}
c_1 = k_{11}p_1 + k_{12}p_2 + k_{13}p_3 \pmod{26},\\
c_2 = k_{21}p_1 + k_{22}p_2 + k_{23}p_3 \pmod{26},\\
c_3 = k_{31}p_1 + k_{32}p_2 + k_{33}p_3 \pmod{26},\\
\end{cases} </math> или в матричной форме:
- <math>
\begin{bmatrix}
c_1 \\ c_2 \\ c_3
\end{bmatrix} = \begin{bmatrix}
k_{11} & k_{12} & k_{13} \\
k_{21} & k_{22} & k_{23} \\
k_{31} & k_{32} & k_{33}
\end{bmatrix} \begin{bmatrix}
p_1 \\ p_2 \\ p_3
\end{bmatrix} \pmod{26},</math>
или
- <math>C = KP \pmod{26},</math>
где <math> P </math> и <math> C </math> — векторы-столбцы высоты 3, представляющие открытый и зашифрованный текст соответственно, <math> K </math> — матрица 3 × 3, представляющая ключ шифрования. Операции выполняются по модулю 26.
Для того, чтобы расшифровать сообщение, требуется получить обратную матрицу ключа <math> K^{-1} </math>. Существуют стандартные методы вычисления обратных матриц (см. способы нахождения обратной матрицы), но не все матрицы имеют обратную (см. обратная матрица). Матрица будет иметь обратную в том и только в том случае, когда её детерминант не равен нулю и не имеет общих делителей с основанием модуля[8]. Если детерминант матрицы равен нулю или имеет общие делители с основанием модуля, то такая матрица не может использоваться в шифре Хилла, и должна быть выбрана другая матрица (в противном случае шифротекст будет невозможно расшифровать). Тем не менее, матрицы, которые удовлетворяют вышеприведенным условиям, существуют в изобилии[6].
В общем случае, алгоритм шифрования может быть выражен в следующем виде[6][9]:
Шифрование: <math>C = E(K,P) = KP \pmod{26}</math>.
Расшифрование: <math>P = D(K,C) = K^{-1}C \pmod{26} = K^{-1}KP \pmod{26} = P</math>.
Пример
В следующем примере[7] используются латинские буквы от 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 в буквенном виде):
- <math>K = \begin{bmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15\end{bmatrix}.</math>
Данная матрица обратима, так как её детерминант не равен нулю и не имеет общих делителей с основанием модуля. Опасность того, что детерминант матрицы ключа будет иметь общие делители с основанием модуля, может быть устранена путём выбора простого числа в качестве основания модуля. Например, в более удобном варианте шифра Хилла в алфавит добавляют 3 дополнительных символа (пробел, точка и знак вопроса), чтобы увеличить основание модуля до 29[5].
Так как букве «A» соответствует число 0, «C» — 2, «T» — 19, то сообщение — это вектор
- <math>P_1 = \begin{bmatrix} 0 \\ 2 \\ 19\end{bmatrix}.</math>
Тогда зашифрованный вектор будет
- <math>C_1 = KP_1 \pmod{26} = \begin{bmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15\end{bmatrix}\begin{bmatrix} 0 \\ 2 \\ 19 \end{bmatrix} \pmod{26} = \begin{bmatrix} 15 \\ 14 \\ 7\end{bmatrix}.</math>
Вектор соответствует зашифрованному тексту «POH». Теперь предположим, что наше сообщение было «CAT»:
- <math>P_2 = \begin{bmatrix} 2 \\ 0 \\ 19\end{bmatrix}.</math>
Теперь зашифрованный вектор будет
- <math>C_2 = KP_2 \pmod{26} = \begin{bmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15\end{bmatrix}\begin{bmatrix} 2 \\ 0 \\ 19\end{bmatrix}\pmod{26} = \begin{bmatrix} 5 \\ 8 \\ 13\end{bmatrix}.</math>
Этот вектор соответствует зашифрованному тексту «FIN». Видно, что каждая буква шифротекста сменилась. Шифр Хилла достиг Шаблон:Не переведено 5 по Шеннону, и n-размерный шифр Хилла может достигать диффузии n символов за раз.
- Расшифрование
Обратная матрица ключа:
- <math>K^{-1} \pmod{26} = \begin{bmatrix} 8 & 5 & 10\\ 21 & 8 & 21\\ 21 & 12 & 8\end{bmatrix}.</math>
Возьмём зашифрованный текст из предыдущего примера «POH»:
- <math>P_1 = K^{-1}C_1 \pmod{26} = \begin{bmatrix} 8 & 5 & 10\\ 21 & 8 & 21\\ 21 & 12 & 8\end{bmatrix}\begin{bmatrix} 15 \\ 14 \\ 7\end{bmatrix} \pmod{26} = \begin{bmatrix} 0 \\ 2 \\ 19\end{bmatrix}.</math>
Этот вектор соответствует сообщению «ACT».
Криптостойкость
Стандартный шифр Хилла уязвим для атаки по выбранному открытому тексту, потому что в нём используются линейные операции. Криптоаналитик, который перехватит <math>n^2</math> пар символ сообщения/символ шифротекста сможет составить систему линейных уравнений, которую обычно несложно решить. Если окажется, что система не решаема, то необходимо всего лишь добавить ещё несколько пар символ сообщения/символ шифротекста. Такого рода расчёты средствами обычных алгоритмов линейной алгебры требует совсем немного времени. В связи с этим для увеличения криптостойкости в него должны быть добавлены какие-либо нелинейные операции. Комбинирование линейных операций, как в шифре Хилла, и нелинейных шагов привело к созданию подстановочно-перестановочной сети (например, сеть Фейстеля). Поэтому с определённой точки зрения можно рассматривать современные блочные шифры как вид полиграммных шифров[7][8].
Длина ключа
Длина ключа — это двоичный логарифм от количества всех возможных ключей. Существует <math>26^{n^2}</math> матриц размера n × n. Значит, <math>\log_2(26^{n^2}) \approx 4{,}7n^2</math> — верхняя грань длины ключа для шифра Хилла, использующего матрицы n × n. Это только верхняя грань, поскольку не каждая матрица обратима, а только такие матрицы могут быть ключом. Количество обратимых матриц может быть рассчитано при помощи Китайской теоремы об остатках. Матрица обратима по модулю 26 тогда и только тогда, когда она обратима и по модулю 2 и по модулю 13[8].
Количество обратимых по модулю 2 и 13 матриц размера n × n равно порядку линейной группы GL(n, Z2) и GL(n, Z13) соответственно:
- <math>|K_1| = 2^{n^2} (1 - 1/2)(1 - 1/2^2) \dots (1 - 1/2^n),</math>
- <math>|K_2| = 13^{n^2} (1 - 1/13)(1 - 1/13^2) \dots (1 - 1/13^n).</math>
Количество обратимых по модулю 26 матриц равно произведению этих чисел:
- <math>|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).</math>
Кроме того, будет разумно избегать слишком большого количества нулей в матрице-ключе, так как они уменьшают диффузию. В итоге получается, что эффективное пространство ключей стандартного шифра Хилла составляет около <math>4{,}64n^2 - 1{,}7</math>. Для шифра Хилла 5 × 5 это составит приблизительно 114 бит. Очевидно, полный перебор — не самая эффективная атака на шифр Хилла[7].
Механическая реализация
При работе с двумя символами за раз шифр Хилла не предоставляет никаких конкретных преимуществ перед шифром Плэйфера и даже уступает ему по криптостойкости и простоте вычислений на бумаге. По мере увеличения размерности ключа шифр быстро становится недоступным для расчётов на бумаге человеком. Шифр Хилла размерности 6 был реализован механически. Хилл с партнёром получили патент на устройство (Шаблон:US patent), которое выполняло умножение матрицы 6 × 6 по модулю 26 при помощи системы шестерёнок и цепей. Расположение шестерёнок (а значит, и ключ) нельзя было изменять для конкретного устройства, поэтому в целях безопасности рекомендовалось тройное шифрование. Такая комбинация была очень сильной для 1929 года, и она показывает, что Хилл несомненно понимал концепции конфузии и диффузии. Однако устройство было довольно медленное, поэтому во Второй мировой войне машины Хилла были использованы только для шифрования трёхсимвольного кода радиосигналов[10].
Примечания
Литература
