Шифр Хилла

Современная криптография прочно вросла своими корнями в математику. Мы разберем пример одного простого классического шифра, который уже безнадежно устарел, но зато ярко и на понятном уровне иллюстрирует тесную взаимосвязь математики с криптографией. Это шифр Хилла. Это симметрический алгоритм шифрования, основанный на решении линейных матричных уравнений в поле классов вычетов по простому модулю. За этими сложными словами стоит простая числовая алгоритмистика.

Предположим необходимо зашифровать слово «кимоно». Ключом шифрования, допустим, будет слово «коловорот». От буквенных символов перейдём к числам. Для этого придумаем свою таблицу кодирования:

а б в ... я . ,   -
0 1 2 ... 32 33 34 35 36

Мы специально подобрали таблицу кодирования таким образом, что число символов в нём является простым числом. Это число равно 37 и называется модулем. Если это число будет составным, то в общем случае шифр Хилла работать не будет.

Кодируем открытый текст в соответствии с таблицей кодирования:

«кимоно» → (11 9 13 15 14 15)

Кодируем ключ в соответствии с таблицей кодирования:

«коловорот» → (11 15 12 15 2 15 17 15 19)

Выписываем ключ в виде матрицы:

Матрица должна быть обязательно квадратной. Поэтому искусственным путём необходимо гарантировать, чтобы количество букв ключа было квадратом натурального числа.

Разбиваем текст на векторы:

Чтобы зашифровать исходный текст, надо умножить векторы M1 и M2 на матрицу K. В результате произведения возникают новые векторы той же размерности, что и исходные. При вычислении необходимо помнить, что вся арифметика идет по модулю 37:

Ниже подробно приведен процесс умножения (процент означает остаток от деления):

(11 · 11 + 9 · 15 + 13 · 17) % 37 = 477 % 37 = 33
(11 · 15 + 9 ·  2 + 13 · 15) % 37 = 378 % 37 = 8
(11 · 12 + 9 · 15 + 13 · 19) % 37 = 514 % 37 = 33

Таким образом:

Аналогично находим C2:

Получаем:

Склеиваем зашифрованные векторы:

Декодируем в соответствии с таблицей кодирования: «.з.б,и»

Итак, открытый текст «кимоно» зашифровался в «.з.б,и».

Теперь посмотрим, как расшифровать зашифрованный текст. Для расшифровки используется матрица K-1, которая обратна к матрице K. Для нахождения обратной матрицы воспользуемся формулой:

В этой формуле требуется найти обратное к определителю матрицы K. Этот момент является ключевым во всем шифре Хилла. Сначала найдем определитель матрицы K (например, по правилу «треугольника»):

11 · 2 · 19 + 17 · 15 · 15 + 15 · 15 · 12 - (17 · 2 · 12 + 15 · 15 · 19 + 11 · 15 · 15) = -215 % 37 = 7

Обратным к 7 будет такой элемент, который при умножении на 7 будет давать единицу по модулю 37. Таким элементом является 16. В самом деле: 7 · 16 = 112 = 37 · 3 + 1. В остатке получается единица, а это значит, что элементы 7 и 16 взаимнообратны по модулю 37.

Элементы Aji — это алгебраические дополнения к элементам aij матрицы K. Алгебраические дополнения вычисляются точно также как и в линейной алгебре над полем вещественных чисел, только конечные результаты вычислений необходимо «обрезать» по модулю 37. Приведём готовый результат:

Теперь расшифруем шифротекст:

Для первого вектора:

Для второго вектора:

Обязательно самостоятельно убедитесь в справедливости приведенных вычислений. Склеиваем полученные результаты, получаем итоговый вектор:

Декодируем полученный вектор:
11 → «к»
 9 → «и»
13 → «м»
15 → «о»
14 → «н»
15 → «о»

Получаем открытый текст: «кимоно»