Шифр Хилла: матричное шифрование по mod 26
Шифр Хилла - один из немногих классических шифров, в основе которого лежит настоящая линейная алгебра: умножение матриц и модульная арифметика. Придуманный в 1929 году математиком Лестером Хиллом, он стал первым полиграфическим шифром, позволяющим надёжно шифровать несколько букв сразу. Сегодня его изучают в курсах криптографии и дискретной математики, потому что он наглядно показывает, как алгебраические операции превращаются в инструмент сокрытия информации. Покрути калькулятор ниже: он сразу показывает, как ключевая матрица преобразует пару букв в шифртекст, и разбирает каждый шаг.
Идея шифра Хилла
Классические шифры подстановки работают по принципу «одна буква - одно шифрованное значение»: A всегда превращается в X, B - в K и так далее. Это делает их уязвимыми к частотному анализу, потому что самая распространённая буква языка всегда указывает на себя в шифртексте.
Хилл предложил шифровать буквы группами. В простейшем варианте берётся пара букв, каждая переводится в число от 0 до 25 (A=0, B=1, ..., Z=25), и получается вектор-столбец. Затем этот вектор умножается на ключевую матрицу размером , а результат берётся по модулю 26.
Теперь каждая буква шифртекста зависит сразу от двух букв открытого текста. Меняется любая из них - меняется весь результат. Частотный анализ по одиночным символам перестаёт работать.
Ключевая матрица и кодирование букв
Алфавит из 26 букв кодируется числами:
Ключ шифра Хилла - это квадратная матрица с целочисленными элементами. Для блока из двух букв используется матрица :
где . Не каждая матрица годится в качестве ключа - о требованиях расскажем ниже.
Шаг шифрования
Разберём полный алгоритм на примере. Пусть ключевая матрица
а открытый текст - слово HI.
Шаг 1. Переводим буквы в числа:
Шаг 2. Умножаем матрицу на вектор:
Шаг 3. Берём результат по mod 26:
Открытый текст HI зашифровался в TC. Другая пара букв с той же матрицей даст другой результат - каждая «позиция» влияет на обе выходные буквы.

Условие обратимости матрицы
Чтобы дешифрование было возможно, матрица должна быть обратимой над кольцом . Это означает, что существует матрица такая, что
где - единичная матрица. Условие обратимости:
Для матрицы определитель вычисляется стандартно:
Берём его по модулю 26 и проверяем, взаимно ли он прост с 26. Число 26 = 2·13, поэтому определитель не должен делиться ни на 2, ни на 13.
Например, для нашей матрицы:
Так как , матрица обратима и её можно использовать как ключ.
Дешифрование: обратная матрица mod 26
Зная шифртекст и матрицу , открытый текст восстанавливается умножением на обратную матрицу:
Для матрицы
обратная матрица вычисляется по формуле:
где - мультипликативное обратное определителя по модулю 26, то есть такое число , что .
Для нужно найти : . Перебором или расширенным алгоритмом Евклида: , поэтому .
Проверка: шифртекст TC = [19, 2],
Получаем [7, 8] = HI - верно.
Почему именно mod 26
Выбор 26 объясняется размером латинского алфавита. Арифметика по модулю 26 превращает множество {0, 1, ..., 25} в кольцо с операциями сложения и умножения. В этом кольце не каждый ненулевой элемент имеет обратный (например, 13 и чётные числа не имеют), поэтому и матрица ключа не произвольна: нужно, чтобы её определитель был обратимым элементом .
Для кириллического алфавита из 32 букв или для алфавита из 256 ASCII-символов схема работает точно так же - просто меняется модуль.
Частые ошибки
- Забыть взять результат по mod 26. После умножения матрицы на вектор каждый элемент может быть больше 25. Без операции mod 26 получится не буква, а выход за пределы алфавита.
- Использовать матрицу с необратимым определителем. Если , дешифрование невозможно. Перед выбором ключа проверяй определитель.
- Подставить отрицательный остаток. В некоторых языках программирования даёт , а не . Используй формулу .
- Перепутать порядок умножения. Умножение матриц некоммутативно: . Вектор открытого текста - столбец справа.
- Считать матрицу ключа обычной вещественной обратной. Обратная матрица в вычисляется с мультипликативным обратным определителя по модулю 26, а не как .
FAQ
Чем шифр Хилла отличается от шифра Цезаря и Виженера? Шифр Цезаря и Виженера шифруют каждую букву независимо (монографические шифры). Шифр Хилла - полиграфический: одна буква шифртекста зависит от нескольких букв открытого текста одновременно. Это делает частотный анализ одиночных символов неэффективным - хотя Хилл не устоит перед анализом биграмм при большом объёме текста.
Какой размер матрицы лучше использовать? Чаще всего в учебных задачах берут матрицу - для неё все расчёты можно сделать вручную. Матрица позволяет шифровать тройки букв сразу и устойчивее к атакам, но расчёт обратной матрицы сложнее. На практике шифр Хилла давно вытеснен современными алгоритмами, однако как учебный пример линейной алгебры в криптографии он остаётся актуальным.
Как атаковать шифр Хилла, зная несколько пар открытый-шифртекст? Это атака на основе известного открытого текста (known-plaintext attack). Если известны пар для -матрицы ключа, их можно собрать в матричное уравнение и найти . При матрице достаточно двух пар, у которых матрица обратима над .
Коротко
Шифр Хилла шифрует блоки букв умножением числового вектора на ключевую матрицу по модулю 26. Формула связывает каждую букву шифртекста сразу с несколькими буквами открытого текста. Дешифрование требует обратной матрицы над , которая существует тогда и только тогда, когда . В курсах дискретной математики и криптографии этот шифр служит наглядным примером применения линейной алгебры к защите информации.
Читайте также

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

Эллиптические кривые в криптографии: точки и ключи
Как эллиптические кривые применяют для обмена ключами и цифровых подписей: сложение точек над конечным полем, учебный расчёт, ECDH и границы стойкости ECC.

Обратная матрица методом Гаусса-Жордана: пример
Как найти обратную матрицу методом Гаусса-Жордана: составляем расширенную матрицу, выполняем операции со строками и проверяем ответ умножением на исходную матрицу.

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

Сингулярное разложение матрицы: формула и пример
Сингулярное разложение матрицы простыми словами: смысл множителей U, Σ и V, пошаговый числовой пример, геометрия эллипса, ранг и приближение матрицы малого ранга.

Умножение матриц: правило строка на столбец
Как умножать матрицы по правилу строка на столбец: проверка размеров, формула элемента, подробный пример вычисления, порядок множителей и типичные ошибки.