Шифр Хилла

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

Особенность шифра Хилла заключается в том, что он работает не с отдельными символами, а с блоками символов (обычно биграммами или триграммами), что делает его устойчивым к частотному анализу, в отличие от простых моноалфавитных шифров.

Ключ: квадратная матрица размером n×n, n — длина блока шифрования. Важно, чтобы матрица была обратимой, то есть ее определитель не равен нулю и не имеет общих делителей с модулем.

Открытый текст разбивается на блоки длиной n. Каждый символ блока заменяется его числовым эквивалентом. Это соответствие также является частью ключа.

Каждый блок открытого текста умножается на ключевую матрицу. Результат умножения по модулю размера алфавита (в случае с английским алфавитом mod 26) дает зашифрованный блок.

Числовые значения зашифрованного блока преобразуются обратно в символы, формируя зашифрованный текст.

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

Пример:

Алиса хочет передать Бобу сообщение “HELLO”. Латинский алфавит, в котором буквы пронумерованы от 0 до 25.

[pic 1]

[pic 2]

Открытый текст, обозначим как P, будет выглядеть следующим образом: 7 4 11 11 14

 C - зашифрованное сообщение: JGUAU.

Криптостойкость:

• Устойчив к полному перебору;
• Практически не поддается частотному анализу;
• Шифр Хилла очень уязвим для атаки по открытому тексту.

Если «противник» знает n пар “открытое сообщение”/ “зашифрованное сообщение”, то он может вычислить ключ.

Стандартный шифр Хилла уязвим для атаки по выбранному открытому тексту, потому что в нём используются линейные операции. Криптоаналитик, который перехватит [pic 3] пар символ сообщения/символ шифротекста сможет составить систему линейных уравнений, которую обычно несложно решить. Если окажется, что система не решаема, то необходимо всего лишь добавить ещё несколько пар символ сообщения/символ шифротекста.