Шифр Хилла

Калькулятор позволяет зашифровать и расшифровать текст методом Хилла.

Шифр Хилла — полиграммный шифр подстановки, основанный на линейной алгебре. Лестер С. Хилл изобрел этот шифр в 1929. Калькулятор ниже позволяет зашифровать и расшифровать текст методом Хилла. Подробности о шифре для интересующихся приведены под калькулятором.

PLANETCALC, Шифр Хилла

Шифр Хилла

Все символы, подвергающиеся шифрованию, должны входить в алфавит
Преобразованный текст
 

Как работает шифр

Для начала символы используемого алфавита (в широком смысле этого слова, например, алфавит может включать в себя пробел и некоторые знаки пунктуации, как в калькуляторе выше) кодируются числами, то есть каждому символу алфавита сопоставляется некоторое число, например, порядковый номер. Выбирается матрица размера n x n, которая будет являться ключом шифра. Весь текст разбивается на блоки из из n букв, числовые значения которых рассматриваются как вектор размерности n. Каждый вектор умножается на матрицу шифрования n × n. Результирующий блок (вектор) размерности n — соответствующий исходному блоку зашифрованный текст. Операции сложения и умножения при этом выполняются в кольце вычетов по модулю m, где m — размерность алфавита. Очевидно, это делается для того, чтобы значения результирующего блока тоже принадлежали исходному алфавиту.

Ключ, в принципе, можно сразу задавать матрицей, но для удобства еще чаще задают кодовой фразой, числовое представление которой трансформируют в матрицу. Понятно, что для того, чтобы получить квадратную матрицу n x n, длина кодовой фразы должна являться квадратом целого числа, то есть, 4, 9, 16, 25, и т. д.

Дополнительные ограничения на ключ шифра накладывает необходимость осуществления расшифровки зашифрованного текста :)
Предположим, что мы зашифровали исходный вектор B матрицей шифрования А и получили вектор С — соответствующий зашифрованному тексту. Для того, чтобы восстановить исходный вектор B по вектору C (расшифровать текст), вектор С надо умножить на матрицу, обратную к матрице А.

BA=C \to CA^{-1}=BAA^{-1}=BE=B

Таким образом, чтобы операция расшифрования была возможна, матрица шифрования должна быть обратима в {Z}}_{{m}}^{n} — кольце вычетов по модулю m.

Отсюда вытекают два условия: детерминант матрицы не должен быть равен 0, и, дополнительно, детерминант матрицы должен иметь обратный элемент в кольце вычетов по модулю m.
Второе следует из формулы
A^{-1} = \frac{1}{\det A}\cdot C^* \to A^{-1} = (det A)^{-1}\cdot C^*.
где операция деления на детерминант заменена на операцию умножения на обратный элемент.

Чтобы иметь обратный элемент, детерминант и модуль (длина алфавита) должны быть взаимнопростыми числами. См. Обратный элемент в кольце по модулю. Для того, чтобы повысить вероятность этого, обычно составляют алфавит, длина которого является простым числом. Поэтому русский алфавит в данном примере был расширен пробелом и символами пунктуации до 37 символов.

Не каждая матрица подойдет для шифра Хилла (и не каждое кодовое слово), но тем менее, подходящих более чем достаточно. Кстати, когда я писал калькулятор, я случайно с первого раза выбрал неподходящее кодовое слово — «абыр валг».

Дополнительно можно почитать в википедии

Ссылка скопирована в буфер обмена
PLANETCALC, Шифр Хилла

Комментарии