Шифр Хила. Подробный разбор

В этой публикации я попытаюсь максимально подробно описать шифрования и дешифрование по алгоритму Хилла. Итак, без лишних слов сразу к делу.

Шифрование

Для того, чтобы зашифровать какой-либо текст по алгоритму Хилла необходимо проделать следующие шаги:

1. Создаем кодированный алфавит. Допустим мы хотим шифровать русский текст. Тогда длина алфавита будет 33 буквы. Целесообразно добавить к алфавиту еще 4 символа на выбор, я добавлю такие: "?", ".", ","," ". Это делается для того, чтобы длина алфавита была простым числом, т.е. числом, которое делится нацело только на себя и на 1. Это, конечно, не обязательно, но очень удобно, потому что для расшифровки необходимо, чтобы детерминант ключа и длина алфавита были взаимно простыми, т.е. не имели общих делителей кроме 1. Если длина алфавита – простое число, то таких ключей, для которых выполняется это условие значительно больше. Каждому символу нашего алфавита ставим в соответствие целочисленный код. Удобнее всего использовать просто номера букв. Таким образом получаем кодированный алфавит:
   
   
   
   
2. Теперь берем текст, который хотим зашифровать и кодируем его с помощью нашего алфавита. Возьмем для примера слово «ШИФР», его код будет таким: 25 9 21 17.
   
   
3. Теперь выбираем ключевое слово, или просто набор букв, который будем использовать в качестве ключа. Тут важно, чтобы длина этого ключевого слова была равна квадрату целого числа, т.е. 4, 9, 16, 25 и т.д. Только тогда мы сможем сделать из него квадратную матрицу, необходимую для шифрования. Я выбрал слово «АЛЬПИНИЗМ». Кодируем его с помощью нашего алфавита. Получаем: 0 12 29 16 9 14 9 8 13. Запишем ключ в виде матрицы 3х3:
   
   
   
   Ключ можно задавать сразу матрицей, если вам так удобней. Я же использовал ключевое слово.
   
   
4. Теперь надо разбить текст на блоки по n символов в каждом, где n-размерность матрицы, в моем случае – 3. Начнем разбивать:
   
   Первый блок: (25 9 21)
   
   На второй блок у нас осталось всего одно число – 17. Самое простое решение в таком случае: добавить столько символов, чтобы образовать целый блок. Я решил добавить пробелы.
   
   Тогда второй блок: (17 35 35)
   
   
5. Теперь шифруем наш текст. Для шифрования текста требуется провести матричное умножение каждого блока на матрицу ключа. Тут стоит заметить, что блоки можно было бы записывать не в строки, а в столбцы. Тогда мы бы умножали ключ на столбец, это не существенное различие.
   
   Также важным фактором для данного шифра является определитель матрицы ключа: он должен быть отличным от нуля, иначе расшифровку зашифрованного текста будет невозможно осуществить.
   
   Итак, умножаем первый блок на ключ:
   
   
   
   Умножаем второй блок на ключ:
   
   
   
   Матричное умножение — это не сложная операция, поэтому расписывать его подробно я не стал.
   Теперь нам нужно получившиеся матрицы разделить по модулю на 37, т.е. взять остаток от деления на 37.
   
   Делим первую матрицу:
   
   
   
   Делим вторую матрицу:
   
   
   
   Почему делим на 37? Потому что это длина нашего алфавита, будь у вас алфавит другой длины, вы бы делили на другое число. Например, для английского алфавита делим на 26, или 29, если вы добавили какие-то символы.
   
   
6. Теперь декодируем полученные матрицы с помощью нашего алфавита.
   
   Первая матрица: АЮН
   Вторая матрица: ЧХЯ
   
   Склеиваем две матрицы и получаем зашифрованный текст: АЮНЧХЯ
   

Дешифрование

Теперь переходим к дешифрованию. Дешифрование производим по следующему алгоритму:

1. Обратно кодируем шифротекст в цифры и разбиваем на блоки.
   
   
2. Находим определитель матрицы ключа:
   
   
   
   Нахождение определителя тоже очень простая операция, так что я ее не расписывал.
   
   
3. Теперь по расширенному алгоритму Евклида находим d, x, y.
   
   Описание и сам алгоритм я расписывать не буду. Информацию об этом алгоритме легко можно найти в Интернете. На вход алгоритма подаем det K и длину нашего алфавита. На выходе мы получим d=1, x=-4, y=41. Нас интересует только x.
   
   
4. Теперь сложная и важная вещь. Нам надо найти обратный детерминанту элемент в кольце по модулю 37. Для этого делаем следующее:
   
   • Если детерминант отрицательный, а x – положительный, то обратный элемент детерминанта будет равен x.
   • Если детерминант положительный, а x – отрицательный, то обратный элемент детерминанта будет равен 37+x.
   • Если детерминант положительный, и x – положительный, то обратный детерминанту элемент будет равен x.
   • Если детерминант и x – отрицательные, то обратный элемент будет равен -x.
   
   Этот алгоритм поиска обратного элемента я подобрал экспериментальным путем, т.к. не мог найти ровным счетом ничего полезного по этой теме. В любом случае, даже если этот алгоритм примитивный, он работает.
   
   Итак, наш детерминант равен 379, он положительный, а x равен -4 – отрицательный. Тогда обратный детерминанту элемент находим по формуле 37+x=37+(-4)=37-4=33.
   
   
5. Теперь еще один момент, с которым я долго мучился, потому что никакой полезной информации в Интернете найти не удалось. Надо найти матрицу обратную матрице ключа по модулю 37. Для того чтобы найти эту матрицу нам необходимо найти матрицу алгебраических дополнений ключа и обратный детерминант матрицы ключа (уже нашли в предыдущем пункте). Матрица алгебраических дополнений ищется тоже очень просто, это я расписывать не буду. В нашем случае она выглядит так:
   
   
   
   Теперь эту матрицу делим по модулю на 37, это я уже расписывал в шифровании. Получаем такую матрицу, тут важно не терять знаки у элементов (некоторые выполняют деление по модулю с потерей минусов, в данном алгоритме это недопустимо):
   
   
   
   Умножаем матрицу алгебраических дополнений на обратный детерминанту элемент. Получаем такую матрицу:
   
   
   
   Делим данну матрицу по модулю на 37:
   
   
   
   Транспонируем ее (меняем строки и столбцы местами):
   
   
   
   Теперь если элемент матрицы отрицательный, меняем его на другой, вычисленный по формуле 37+<элемент>:
   
   
   
   Последняя полученная матрица является обратной по модулю к матрице ключа. Если перемножить матрицу ключа и эту матрицу, а потом результат разделить по модулю на 37, мы получим единичную матрицу, т.е. матрицу вида:
   
   
   
   
6. Для дешифровки шифротекста умножаем строки шифротекста на матрицу обратную ключу.
   Умножаем первую строку:
   
   
   
   Умножаем вторую строку:
   
   
   
   Делим полученные строки на 37 по модулю:
   
   
   
   Склеиваем матрицы (25 9 21 13 35 35) и декодируем с помощью нашего алфавита: ШИФР.
   
   В итоге мы получили исходный текст с двумя лишними пробелами в конце, которые никакой роли не играют.
   

Спасибо за внимание!