Шифр Хилла — полиграммный шифр подстановки , основанный на линейной алгебре и модульной арифметике . Изобретён американским математиком Лестером Хиллом в 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, то можно использовать другую числовую схему для сопоставления буквам чисел и добавить пробелы и знаки пунктуации . Элементы матрицы являются ключом. Матрица должна быть обратима в ${\displaystyle \mathbb {Z} _{26}^{n}}$ , чтобы была возможна операция расшифрования .

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

${\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}}}$

или в матричной форме:

${\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}},}$

или

${\displaystyle C=KP{\pmod {26}},}$

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

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

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

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

Расшифрование: ${\displaystyle P=D(K,C)=K^{-1}C{\pmod {26}}=K^{-1}KP{\pmod {26}}=P}$ .

Пример

В следующем примере используются латинские буквы от 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 в буквенном виде):

${\displaystyle K={\begin{bmatrix}6&24&1\\13&16&10\\20&17&15\end{bmatrix}}.}$

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

Так как букве «A» соответствует число 0, «C» — 2, «T» — 19, то сообщение — это вектор

${\displaystyle P_{1}={\begin{bmatrix}0\\2\\19\end{bmatrix}}.}$

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

${\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}}.}$

Вектор соответствует зашифрованному тексту «POH». Теперь предположим, что наше сообщение было «CAT»:

${\displaystyle P_{2}={\begin{bmatrix}2\\0\\19\end{bmatrix}}.}$

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

${\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}}.}$

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

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

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

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

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

${\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}}.}$

Этот вектор соответствует сообщению «ACT».

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

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

Длина ключа

Длина ключа — это двоичный логарифм от количества всех возможных ключей. Существует ${\displaystyle 26^{n^{2}}}$ матриц размера n × n . Значит, ${\displaystyle \log _{2}(26^{n^{2}})\approx 4{,}7n^{2}}$ — верхняя грань длины ключа для шифра Хилла, использующего матрицы n × n . Это только верхняя грань, поскольку не каждая матрица обратима, а только такие матрицы могут быть ключом. Количество обратимых матриц может быть рассчитано при помощи Китайской теоремы об остатках . Матрица обратима по модулю 26 тогда и только тогда, когда она обратима и по модулю 2 и по модулю 13 .

Количество обратимых по модулю 2 и 13 матриц размера n × n равно порядку линейной группы GL( n , Z ₂ ) и GL( n , Z ₁₃ ) соответственно:

${\displaystyle |K_{1}|=2^{n^{2}}(1-1/2)(1-1/2^{2})\dots (1-1/2^{n}),}$

${\displaystyle |K_{2}|=13^{n^{2}}(1-1/13)(1-1/13^{2})\dots (1-1/13^{n}).}$

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

${\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}).}$

Кроме того, будет разумно избегать слишком большого количества нулей в матрице-ключе, так как они уменьшают диффузию. В итоге получается, что эффективное пространство ключей стандартного шифра Хилла составляет около ${\displaystyle 4{,}64n^{2}-1{,}7}$ . Для шифра Хилла 5 × 5 это составит приблизительно 114 бит. Очевидно, полный перебор — не самая эффективная атака на шифр Хилла .

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

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

Примечания

Литература

• 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 : .
• Wade Trappe, Lawrence C. Washington. . — Pearson Prentice Hall, 2006. — P. -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 .