Шифр Хилла
Современная криптография прочно вросла своими корнями в математику. Мы разберем пример одного простого классического шифра, который уже безнадежно устарел, но зато ярко и на понятном уровне иллюстрирует тесную взаимосвязь математики с криптографией. Это шифр Хилла. Это симметрический алгоритм шифрования, основанный на решении линейных матричных уравнений в поле классов вычетов по простому модулю. За этими сложными словами стоит простая числовая алгоритмистика.
Предположим необходимо зашифровать слово «кимоно». Ключом шифрования, допустим, будет слово «коловорот». От буквенных символов перейдём к числам. Для этого придумаем свою таблицу кодирования:
| а | б | в | ... | я | . | , | - | |
| 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 → «о»
Получаем открытый текст: «кимоно»