Шифр Хилла
Шифр Хилла — полиграммный шифр подстановки, основанный на линейной алгебре и модульной арифметике. Изобретён американским математиком Лестером Хиллом в 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]:
Хилл был одним из тех, кто разработал общий и мощный метод. К тому же шифр Хилла впервые перевёл криптографию с использованием полиграмм в разряд практических дисциплин.
Оригинальный текст (англ.)But Hill alone devised a method of power and generality. In addition, his procedure made polygraphic cryptography practical for the first time.
Описание шифра Хилла править
Шифр Хилла является полиграммным шифром, который может использовать большие блоки с помощью линейной алгебры. Каждой букве алфавита сопоставляется число по модулю 26. Для латинского алфавита часто используется простейшая схема: A = 0, B = 1, …, Z = 25, но это не является существенным свойством шифра. Блок из n букв рассматривается как n-мерный вектор и умножается по модулю 26 на матрицу размера n × n. Если в качестве основания модуля используется число больше чем 26, то можно использовать другую числовую схему для сопоставления буквам чисел и добавить пробелы и знаки пунктуации[5]. Элементы матрицы являются ключом. Матрица должна быть обратима в , чтобы была возможна операция расшифрования[6][7].
Для n = 3 система может быть описана так:
или в матричной форме:
или
где и — векторы-столбцы высоты 3, представляющие открытый и зашифрованный текст соответственно, — матрица 3 × 3, представляющая ключ шифрования. Операции выполняются по модулю 26.
Для того, чтобы расшифровать сообщение, требуется получить обратную матрицу ключа . Существуют стандартные методы вычисления обратных матриц (см. способы нахождения обратной матрицы), но не все матрицы имеют обратную (см. обратная матрица). Матрица будет иметь обратную в том и только в том случае, когда её детерминант не равен нулю и не имеет общих делителей с основанием модуля[8]. Если детерминант матрицы равен нулю или имеет общие делители с основанием модуля, то такая матрица не может использоваться в шифре Хилла, и должна быть выбрана другая матрица (в противном случае шифротекст будет невозможно расшифровать). Тем не менее, матрицы, которые удовлетворяют вышеприведенным условиям, существуют в изобилии[6].
В общем случае, алгоритм шифрования может быть выражен в следующем виде[6][9]:
Шифрование: .
Расшифрование: .
Пример править
В следующем примере[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 в буквенном виде):
Данная матрица обратима, так как её детерминант не равен нулю и не имеет общих делителей с основанием модуля. Опасность того, что детерминант матрицы ключа будет иметь общие делители с основанием модуля, может быть устранена путём выбора простого числа в качестве основания модуля. Например, в более удобном варианте шифра Хилла в алфавит добавляют 3 дополнительных символа (пробел, точка и знак вопроса), чтобы увеличить основание модуля до 29[5].
Так как букве «A» соответствует число 0, «C» — 2, «T» — 19, то сообщение — это вектор
Тогда зашифрованный вектор будет
Вектор соответствует зашифрованному тексту «POH». Теперь предположим, что наше сообщение было «CAT»:
Теперь зашифрованный вектор будет
Этот вектор соответствует зашифрованному тексту «FIN». Видно, что каждая буква шифротекста сменилась. Шифр Хилла достиг диффузии по Шеннону, и n-размерный шифр Хилла может достигать диффузии n символов за раз.
- Расшифрование
Обратная матрица ключа:
Возьмём зашифрованный текст из предыдущего примера «POH»:
Этот вектор соответствует сообщению «ACT».
Криптостойкость править
Стандартный шифр Хилла уязвим для атаки по выбранному открытому тексту, потому что в нём используются линейные операции. Криптоаналитик, который перехватит пар символ сообщения/символ шифротекста сможет составить систему линейных уравнений, которую обычно несложно решить. Если окажется, что система не решаема, то необходимо всего лишь добавить ещё несколько пар символ сообщения/символ шифротекста. Такого рода расчёты средствами обычных алгоритмов линейной алгебры требует совсем немного времени. В связи с этим для увеличения криптостойкости в него должны быть добавлены какие-либо нелинейные операции. Комбинирование линейных операций, как в шифре Хилла, и нелинейных шагов привело к созданию подстановочно-перестановочной сети (например, сеть Фейстеля). Поэтому с определённой точки зрения можно рассматривать современные блочные шифры как вид полиграммных шифров[7][8].
Длина ключа править
Длина ключа — это двоичный логарифм от количества всех возможных ключей. Существует матриц размера n × n. Значит, — верхняя грань длины ключа для шифра Хилла, использующего матрицы n × n. Это только верхняя грань, поскольку не каждая матрица обратима, а только такие матрицы могут быть ключом. Количество обратимых матриц может быть рассчитано при помощи Китайской теоремы об остатках. Матрица обратима по модулю 26 тогда и только тогда, когда она обратима и по модулю 2 и по модулю 13[8].
Количество обратимых по модулю 2 и 13 матриц размера n × n равно порядку линейной группы GL(n, Z2) и GL(n, Z13) соответственно:
Количество обратимых по модулю 26 матриц равно произведению этих чисел:
Кроме того, будет разумно избегать слишком большого количества нулей в матрице-ключе, так как они уменьшают диффузию. В итоге получается, что эффективное пространство ключей стандартного шифра Хилла составляет около . Для шифра Хилла 5 × 5 это составит приблизительно 114 бит. Очевидно, полный перебор — не самая эффективная атака на шифр Хилла[7].
Механическая реализация править
При работе с двумя символами за раз шифр Хилла не предоставляет никаких конкретных преимуществ перед шифром Плэйфера и даже уступает ему по криптостойкости и простоте вычислений на бумаге. По мере увеличения размерности ключа шифр быстро становится недоступным для расчётов на бумаге человеком. Шифр Хилла размерности 6 был реализован механически. Хилл с партнёром получили патент на устройство (U.S. Patent 1 845 947), которое выполняло умножение матрицы 6 × 6 по модулю 26 при помощи системы шестерёнок и цепей. Расположение шестерёнок (а значит, и ключ) нельзя было изменять для конкретного устройства, поэтому в целях безопасности рекомендовалось тройное шифрование. Такая комбинация была очень сильной для 1929 года, и она показывает, что Хилл несомненно понимал концепции конфузии и диффузии. Однако устройство было довольно медленное, поэтому во Второй мировой войне машины Хилла были использованы только для шифрования трёхсимвольного кода радиосигналов[10].
Примечания править
- ↑ Lester S. Hill. Cryptography in an Algebraic Alphabet (англ.) : Article. — 1929. — С. 7. Архивировано 14 июля 2014 года.
- ↑ Chris Christensen. Lester Hill Revisited (англ.) // Taylor & Francis Group, LLC : Article. — 2014. — С. 297. — ISSN 0161-1194.
- ↑ Lester S. Hill. Concerning Certain Linear Transformation Apparatus of Cryptography (англ.) // The American Mathematical Monthly. — 1931. — Март. — С. 135-154. Архивировано 8 декабря 2015 года.
- ↑ 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.
- ↑ 1 2 Murray Eisenberg. Hill Ciphers: A Linear Algebra Project with Mathematica (англ.). Архивировано 8 декабря 2015 года.
- ↑ 1 2 3 William Stallings. Cryptography and Network Security: Principles and Practice. — 5. — Pearson Education, 2011. — С. 46—49. — ISBN 978-0-13-609704-4.
- ↑ 1 2 3 4 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.
- ↑ 1 2 3 А. П. Алферов, А. Ю. Зубов, А. С. Кузьмин, А. В. Черёмушкин. Основы криптографии. — 2-е изд. — Гелиос АРВ, 2002. — С. 115-119. — 480 с. — ISBN 5-85438-137-0.
- ↑ Dorothy Elizabeth Robling Denning. Cryptography and Data Security. — London: Addison-Wesley Publishing Company, 1982. — С. 88-89. — 400 с. — ISBN 0-201-10150-5.
- ↑ 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.
Эта статья входит в число добротных статей русскоязычного раздела Википедии. |