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

Шифрование

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

В следующих примерах используются латинские буквы от A до Z, соответствующие им численные значения приведены в таблице.

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

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

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

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

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

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

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

Для того, чтобы расшифровать сообщение, необходимо обратить шифротекст обратно в вектор и затем просто умножить на обратную матрицу ключа (IFKVIVVMI в буквенном виде). (Существуют стандартные методы вычисления обратных матриц, смотрите способы нахождения обратной матрицы для подробностей.) В обратная матрица к использованной в примере шифрования будет

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

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

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

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

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

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

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

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

Длина ключа

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

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

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

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

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

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

Примечания