Шифр Хилла

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис
Хилл Сандерс Лестер

Шифр Хилла — полиграммный шифр подстановки, основанный на линейной алгебре и модульной арифметике. Изобретён американским математиком Лестером Хиллом в 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]:

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

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

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

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

[math]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ C = KP \pmod{26}, }[/math]

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

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

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

Шифрование: [math]\displaystyle{ C = E(K,P) = KP \pmod{26} }[/math].

Расшифрование: [math]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ P_1 = \begin{bmatrix} 0 \\ 2 \\ 19\end{bmatrix}. }[/math]

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

[math]\displaystyle{ 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]\displaystyle{ P_2 = \begin{bmatrix} 2 \\ 0 \\ 19\end{bmatrix}. }[/math]

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

[math]\displaystyle{ 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». Видно, что каждая буква шифротекста сменилась. Шифр Хилла достиг диффузии[англ.] по Шеннону, и n-размерный шифр Хилла может достигать диффузии n символов за раз.

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

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

[math]\displaystyle{ K^{-1} \pmod{26} = \begin{bmatrix} 8 & 5 & 10\\ 21 & 8 & 21\\ 21 & 12 & 8\end{bmatrix}. }[/math]

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

[math]\displaystyle{ 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]\displaystyle{ n^2 }[/math] пар символ сообщения/символ шифротекста сможет составить систему линейных уравнений, которую обычно несложно решить. Если окажется, что система не решаема, то необходимо всего лишь добавить ещё несколько пар символ сообщения/символ шифротекста. Такого рода расчёты средствами обычных алгоритмов линейной алгебры требует совсем немного времени. В связи с этим для увеличения криптостойкости в него должны быть добавлены какие-либо нелинейные операции. Комбинирование линейных операций, как в шифре Хилла, и нелинейных шагов привело к созданию подстановочно-перестановочной сети (например, сеть Фейстеля). Поэтому с определённой точки зрения можно рассматривать современные блочные шифры как вид полиграммных шифров[7][8].

Длина ключа

Длина ключа — это двоичный логарифм от количества всех возможных ключей. Существует [math]\displaystyle{ 26^{n^2} }[/math] матриц размера n × n. Значит, [math]\displaystyle{ \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]\displaystyle{ |K_1| = 2^{n^2} (1 - 1/2)(1 - 1/2^2) \dots (1 - 1/2^n), }[/math]
[math]\displaystyle{ |K_2| = 13^{n^2} (1 - 1/13)(1 - 1/13^2) \dots (1 - 1/13^n). }[/math]

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

[math]\displaystyle{ |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]\displaystyle{ 4{,}64n^2 - 1{,}7 }[/math]. Для шифра Хилла 5 × 5 это составит приблизительно 114 бит. Очевидно, полный перебор — не самая эффективная атака на шифр Хилла[7].

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

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

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

Примечания

  1. ↑ Lester S. Hill. Cryptography in an Algebraic Alphabet (англ.) : Article. — 1929. — С. 7.
  2. ↑ Chris Christensen. Lester Hill Revisited (англ.) // Taylor & Francis Group, LLC : Article. — 2014. — С. 297. — ISSN 0161-1194.
  3. ↑ Lester S. Hill. Concerning Certain Linear Transformation Apparatus of Cryptography (англ.) // The American Mathematical Monthly. — 1931. — Март. — С. 135-154.
  4. ↑ David Kahn. The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet. — Simon and Schuster. — New York: Scribner, 1996. — С. 405. — 723 с. — ISBN 0-684-83130-9.
  5. ↑ 5,0 5,1 Murray Eisenberg. Hill Ciphers: A Linear Algebra Project with Mathematica (англ.).
  6. ↑ 6,0 6,1 6,2 William Stallings. Cryptography and Network Security: Principles and Practice. — 5. — Pearson Education, 2011. — С. 46—49. — ISBN 978-0-13-609704-4.
  7. ↑ 7,0 7,1 7,2 7,3 A. V. N. Krishna, Dr. A. Vinaya Babu. A Modified Hill Cipher Algorithm for Encryption of Data In Data Transmission (англ.) // Computer Science and Telecommunications : Georgian Electronic Scientific Journal. — 2007. — № 3(14). — С. 78—83. — ISSN 1512-1232.
  8. ↑ 8,0 8,1 8,2 А. П. Алферов, А. Ю. Зубов, А. С. Кузьмин, А. В. Черёмушкин. Основы криптографии. — 2-е изд. — Гелиос АРВ, 2002. — С. 115-119. — 480 с. — ISBN 5-85438-137-0.
  9. ↑ Dorothy Elizabeth Robling Denning. Cryptography and Data Security. — London: Addison-Wesley Publishing Company, 1982. — С. 88-89. — 400 с. — ISBN 0-201-10150-5.
  10. ↑ Friedrich L. Bauer. Decrypted Secrets: Methods and Maxims of Cryptology. — Springer, 2002. — С. 85. — 474 с. — ISBN 978-3-662-04738-5.

Литература

  • William Stallings. Cryptography and Network Security: Principles and Practice. — Pearson, 2011. — P. 46-49. — 711 p. — ISBN 978-0-13-609704-4.
  • David Kahn. The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet. — Simon and Schuster, 1996. — P. 405. — 723 p. — ISBN 978-0-13-609704-4.
  • Jeffrey Overbey, William Traves, Jerzy Wojdylo. On the Keyspace of the Hill Cipher. — 2005. — Т. 29. — P. 59–72. — doi:10.1080/0161-110591893771.
  • Wade Trappe, Lawrence C. Washington. Introduction to Cryptography: With Coding Theory. — Pearson Prentice Hall, 2006. — P. 34-38. — 577 p. — ISBN 0-13-198199-5.
  • Craig P. Bauer. Secret History: The Story of Cryptology. — CRC Press, 2013. — P. 227-228. — 575 p. — ISBN 978-1-4665-6187-8.
Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Шифр_Хилла&oldid=5850551