Шифр Хилла — полиграммный шифр подстановки, основанный на линейной алгебре и модульной арифметике. Изобретён американским математиком Лестером Хиллом в 1929 году. Это был первый шифр, который позволил на практике (хотя и с трудом) одновременно оперировать более чем с тремя символами. Шифр Хилла не нашёл практического применения в криптографии из-за слабой устойчивости ко взлому и отсутствия описания алгоритмов генерации прямых и обратных матриц большого размера.
История
Впервые шифр Хилла был описан в статье «Cryptography in an Algebraic Alphabet», опубликованной в журнале «The American Mathematical Monthly» в июне-июле 1929 года. В августе того же года Хилл расширил тему и выступил с речью о криптографии перед Американским математическим обществом в Боулдере, штат Колорадо. Позднее его лекция привела ко второй статье «Concerning Certain Linear Transformation Apparatus of Cryptography», которая была опубликована в журнале «The American Mathematical Monthly» в марте 1931 года. Дэвид Кан в своем труде «Взломщики кодов» так описал шифр Хилла и его место в истории криптографии:
Хилл был одним из тех, кто разработал общий и мощный метод. К тому же шифр Хилла впервые перевёл криптографию с использованием полиграмм в разряд практических дисциплин.
Оригинальный текст (англ.) 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, то можно использовать другую числовую схему для сопоставления буквам чисел и добавить пробелы и знаки пунктуации. Элементы матрицы являются ключом. Матрица должна быть обратима в Z 26 n {displaystyle mathbb {Z} _{26}^{n}} , чтобы была возможна операция расшифрования.
Для n = 3 система может быть описана так:
{ c 1 = k 11 p 1 + k 12 p 2 + k 13 p 3 ( mod 26 ) , c 2 = k 21 p 1 + k 22 p 2 + k 23 p 3 ( mod 26 ) , c 3 = k 31 p 1 + k 32 p 2 + k 33 p 3 ( mod 26 ) , {displaystyle {egin{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}}}или в матричной форме:
[ c 1 c 2 c 3 ] = [ k 11 k 12 k 13 k 21 k 22 k 23 k 31 k 32 k 33 ] [ p 1 p 2 p 3 ] ( mod 26 ) , {displaystyle {egin{bmatrix}c_{1}c_{2}c_{3}end{bmatrix}}={egin{bmatrix}k_{11}&k_{12}&k_{13}k_{21}&k_{22}&k_{23}k_{31}&k_{32}&k_{33}end{bmatrix}}{egin{bmatrix}p_{1}p_{2}p_{3}end{bmatrix}}{pmod {26}},}или
C = K P ( mod 26 ) , {displaystyle C=KP{pmod {26}},}где P {displaystyle P} и C {displaystyle C} — векторы-столбцы высоты 3, представляющие открытый и зашифрованный текст соответственно, K {displaystyle K} — матрица 3 × 3, представляющая ключ шифрования. Операции выполняются по модулю 26.
Для того, чтобы расшифровать сообщение, требуется получить обратную матрицу ключа K − 1 {displaystyle K^{-1}} . Существуют стандартные методы вычисления обратных матриц (см. способы нахождения обратной матрицы), но не все матрицы имеют обратную (см. обратная матрица). Матрица будет иметь обратную в том и только в том случае, когда её детерминант не равен нулю и не имеет общих делителей с основанием модуля. Если детерминант матрицы равен нулю или имеет общие делители с основанием модуля, то такая матрица не может использоваться в шифре Хилла, и должна быть выбрана другая матрица (в противном случае шифротекст будет невозможно расшифровать). Тем не менее, матрицы, которые удовлетворяют вышеприведенным условиям, существуют в изобилии.
В общем случае, алгоритм шифрования может быть выражен в следующем виде:
Шифрование: C = E ( K , P ) = K P ( mod 26 ) {displaystyle C=E(K,P)=KP{pmod {26}}} .
Расшифрование: P = D ( K , C ) = K − 1 C ( mod 26 ) = K − 1 K P ( mod 26 ) = P {displaystyle P=D(K,C)=K^{-1}C{pmod {26}}=K^{-1}KP{pmod {26}}=P} .
Пример
В следующем примере используются латинские буквы от A до Z, соответствующие им численные значения приведены в таблице.
ШифрованиеРассмотрим сообщение «ACT» и представленный ниже ключ (GYBNQKURP в буквенном виде):
K = [ 6 24 1 13 16 10 20 17 15 ] . {displaystyle K={egin{bmatrix}6&24&113&16&1020&17&15end{bmatrix}}.}Данная матрица обратима, так как её детерминант не равен нулю и не имеет общих делителей с основанием модуля. Опасность того, что детерминант матрицы ключа будет иметь общие делители с основанием модуля, может быть устранена путём выбора простого числа в качестве основания модуля. Например, в более удобном варианте шифра Хилла в алфавит добавляют 3 дополнительных символа (пробел, точка и знак вопроса), чтобы увеличить основание модуля до 29.
Так как букве «A» соответствует число 0, «C» — 2, «T» — 19, то сообщение — это вектор
P 1 = [ 0 2 19 ] . {displaystyle P_{1}={egin{bmatrix}0219end{bmatrix}}.}Тогда зашифрованный вектор будет
C 1 = K P 1 ( mod 26 ) = [ 6 24 1 13 16 10 20 17 15 ] [ 0 2 19 ] ( mod 26 ) = [ 15 14 7 ] . {displaystyle C_{1}=KP_{1}{pmod {26}}={egin{bmatrix}6&24&113&16&1020&17&15end{bmatrix}}{egin{bmatrix}0219end{bmatrix}}{pmod {26}}={egin{bmatrix}15147end{bmatrix}}.}Вектор соответствует зашифрованному тексту «POH». Теперь предположим, что наше сообщение было «CAT»:
P 2 = [ 2 0 19 ] . {displaystyle P_{2}={egin{bmatrix}2 19end{bmatrix}}.}Теперь зашифрованный вектор будет
C 2 = K P 2 ( mod 26 ) = [ 6 24 1 13 16 10 20 17 15 ] [ 2 0 19 ] ( mod 26 ) = [ 5 8 13 ] . {displaystyle C_{2}=KP_{2}{pmod {26}}={egin{bmatrix}6&24&113&16&1020&17&15end{bmatrix}}{egin{bmatrix}2 19end{bmatrix}}{pmod {26}}={egin{bmatrix}5813end{bmatrix}}.}Этот вектор соответствует зашифрованному тексту «FIN». Видно, что каждая буква шифротекста сменилась. Шифр Хилла достиг диффузии по Шеннону, и n-размерный шифр Хилла может достигать диффузии n символов за раз.
РасшифрованиеОбратная матрица ключа:
K − 1 ( mod 26 ) = [ 8 5 10 21 8 21 21 12 8 ] . {displaystyle K^{-1}{pmod {26}}={egin{bmatrix}8&5&1021&8&2121&12&8end{bmatrix}}.}Возьмём зашифрованный текст из предыдущего примера «POH»:
P 1 = K − 1 C 1 ( mod 26 ) = [ 8 5 10 21 8 21 21 12 8 ] [ 15 14 7 ] ( mod 26 ) = [ 0 2 19 ] . {displaystyle P_{1}=K^{-1}C_{1}{pmod {26}}={egin{bmatrix}8&5&1021&8&2121&12&8end{bmatrix}}{egin{bmatrix}15147end{bmatrix}}{pmod {26}}={egin{bmatrix}0219end{bmatrix}}.}Этот вектор соответствует сообщению «ACT».
Криптостойкость
Стандартный шифр Хилла уязвим для атаки по выбранному открытому тексту, потому что в нём используются линейные операции. Криптоаналитик, который перехватит n 2 {displaystyle n^{2}} пар символ сообщения/символ шифротекста сможет составить систему линейных уравнений, которую обычно несложно решить. Если окажется, что система не решаема, то необходимо всего лишь добавить ещё несколько пар символ сообщения/символ шифротекста. Такого рода расчёты средствами обычных алгоритмов линейной алгебры требует совсем немного времени. В связи с этим для увеличения криптостойкости в него должны быть добавлены какие-либо нелинейные операции. Комбинирование линейных операций, как в шифре Хилла, и нелинейных шагов привело к созданию подстановочно-перестановочной сети (например, сеть Фейстеля). Поэтому с определённой точки зрения можно рассматривать современные блочные шифры как вид полиграммных шифров.
Длина ключа
Длина ключа — это двоичный логарифм от количества всех возможных ключей. Существует 26 n 2 {displaystyle 26^{n^{2}}} матриц размера n × n. Значит, log 2 ( 26 n 2 ) ≈ 4 , 7 n 2 {displaystyle log _{2}(26^{n^{2}})approx 4{,}7n^{2}} — верхняя грань длины ключа для шифра Хилла, использующего матрицы n × n. Это только верхняя грань, поскольку не каждая матрица обратима, а только такие матрицы могут быть ключом. Количество обратимых матриц может быть рассчитано при помощи Китайской теоремы об остатках. Матрица обратима по модулю 26 тогда и только тогда, когда она обратима и по модулю 2 и по модулю 13.
Количество обратимых по модулю 2 и 13 матриц размера n × n равно порядку линейной группы GL(n, Z2) и GL(n, Z13) соответственно:
| K 1 | = 2 n 2 ( 1 − 1 / 2 ) ( 1 − 1 / 2 2 ) … ( 1 − 1 / 2 n ) , {displaystyle |K_{1}|=2^{n^{2}}(1-1/2)(1-1/2^{2})dots (1-1/2^{n}),} | K 2 | = 13 n 2 ( 1 − 1 / 13 ) ( 1 − 1 / 13 2 ) … ( 1 − 1 / 13 n ) . {displaystyle |K_{2}|=13^{n^{2}}(1-1/13)(1-1/13^{2})dots (1-1/13^{n}).}Количество обратимых по модулю 26 матриц равно произведению этих чисел:
| K | = 26 n 2 ( 1 − 1 / 2 ) ( 1 − 1 / 2 2 ) … ( 1 − 1 / 2 n ) ( 1 − 1 / 13 ) ( 1 − 1 / 13 2 ) … ( 1 − 1 / 13 n ) . {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}).}Кроме того, будет разумно избегать слишком большого количества нулей в матрице-ключе, так как они уменьшают диффузию. В итоге получается, что эффективное пространство ключей стандартного шифра Хилла составляет около 4 , 64 n 2 − 1 , 7 {displaystyle 4{,}64n^{2}-1{,}7} . Для шифра Хилла 5 × 5 это составит приблизительно 114 бит. Очевидно, полный перебор — не самая эффективная атака на шифр Хилла.
Механическая реализация
При работе с двумя символами за раз шифр Хилла не предоставляет никаких конкретных преимуществ перед шифром Плэйфера и даже уступает ему по криптостойкости и простоте вычислений на бумаге. По мере увеличения размерности ключа шифр быстро становится недоступным для расчётов на бумаге человеком. Шифр Хилла размерности 6 был реализован механически. Хилл с партнёром получили патент на устройство (U.S. Patent 1 845 947), которое выполняло умножение матрицы 6 × 6 по модулю 26 при помощи системы шестерёнок и цепей. Расположение шестерёнок (а значит, и ключ) нельзя было изменять для конкретного устройства, поэтому в целях безопасности рекомендовалось тройное шифрование. Такая комбинация была очень сильной для 1929 года, и она показывает, что Хилл несомненно понимал концепции конфузии и диффузии. Однако устройство было довольно медленное, поэтому во Второй мировой войне машины Хилла были использованы только для шифрования трёхсимвольного кода радиосигналов.