Шифр Хилла

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

Шифр Хилла

Алфавит

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

никогда еще штирлиц не был так близок к провалу

Текст

Ключ

Преобразование

Зашифровать

Расшифровать

Рассчитать

Преобразованный текст

 

 Ссылка  Сохранить  Виджет

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

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

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

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

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

Отсюда вытекают два условия: детерминант матрицы не должен быть равен 0, и, дополнительно, детерминант матрицы должен иметь обратный элемент в кольце вычетов по модулю m.
Второе следует из формулы
.
где операция деления на детерминант заменена на операцию умножения на обратный элемент.

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

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

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