Шифр Хилла: матричное шифрование по mod 26

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

Идея шифра Хилла

Классические шифры подстановки работают по принципу «одна буква - одно шифрованное значение»: A всегда превращается в X, B - в K и так далее. Это делает их уязвимыми к частотному анализу, потому что самая распространённая буква языка всегда указывает на себя в шифртексте.

Хилл предложил шифровать буквы группами. В простейшем варианте берётся пара букв, каждая переводится в число от 0 до 25 (A=0, B=1, ..., Z=25), и получается вектор-столбец. Затем этот вектор умножается на ключевую матрицу $K$ размером $2 \times 2$, а результат берётся по модулю 26.

$\begin{pmatrix} c_0 \\ c_1 \end{pmatrix} = K \cdot \begin{pmatrix} p_0 \\ p_1 \end{pmatrix} \pmod{26}$

Теперь каждая буква шифртекста зависит сразу от двух букв открытого текста. Меняется любая из них - меняется весь результат. Частотный анализ по одиночным символам перестаёт работать.

Ключевая матрица и кодирование букв

Алфавит из 26 букв кодируется числами:

$A = 0,\quad B = 1,\quad C = 2,\quad \ldots,\quad Z = 25.$

Ключ шифра Хилла - это квадратная матрица с целочисленными элементами. Для блока из двух букв используется матрица $2 \times 2$:

$K = \begin{pmatrix} a & b \\ c & d \end{pmatrix},$

где $a, b, c, d \in \{0, 1, \ldots, 25\}$. Не каждая матрица годится в качестве ключа - о требованиях расскажем ниже.

Рассчитать для своей задачи

Шаг шифрования

Разберём полный алгоритм на примере. Пусть ключевая матрица

$K = \begin{pmatrix} 3 & 3 \\ 2 & 5 \end{pmatrix},$

а открытый текст - слово HI.

Шаг 1. Переводим буквы в числа:

$H = 7,\quad I = 8 \quad \Rightarrow \quad \mathbf{p} = \begin{pmatrix} 7 \\ 8 \end{pmatrix}.$

Шаг 2. Умножаем матрицу на вектор:

$K \cdot \mathbf{p} = \begin{pmatrix} 3 & 3 \\ 2 & 5 \end{pmatrix} \begin{pmatrix} 7 \\ 8 \end{pmatrix} = \begin{pmatrix} 3 \cdot 7 + 3 \cdot 8 \\ 2 \cdot 7 + 5 \cdot 8 \end{pmatrix} = \begin{pmatrix} 45 \\ 54 \end{pmatrix}.$

Шаг 3. Берём результат по mod 26:

$c_0 = 45 \bmod 26 = 19 \quad \Rightarrow \quad T,$ $c_1 = 54 \bmod 26 = 2 \quad \Rightarrow \quad C.$

Открытый текст HI зашифровался в TC. Другая пара букв с той же матрицей даст другой результат - каждая «позиция» влияет на обе выходные буквы.

Рассчитать для своей задачи

Условие обратимости матрицы

Чтобы дешифрование было возможно, матрица $K$ должна быть обратимой над кольцом $\mathbb{Z}_{26}$. Это означает, что существует матрица $K^{-1}$ такая, что

$K^{-1} \cdot K \equiv I \pmod{26},$

где $I$ - единичная матрица. Условие обратимости:

$\gcd(\det(K) \bmod 26,\; 26) = 1.$

Для матрицы $2 \times 2$ определитель вычисляется стандартно:

$\det(K) = ad - bc.$

Берём его по модулю 26 и проверяем, взаимно ли он прост с 26. Число 26 = 2·13, поэтому определитель не должен делиться ни на 2, ни на 13.

Например, для нашей матрицы:

$\det(K) = 3 \cdot 5 - 3 \cdot 2 = 15 - 6 = 9.$

Так как $\gcd(9, 26) = 1$, матрица обратима и её можно использовать как ключ.

Дешифрование: обратная матрица mod 26

Зная шифртекст $\mathbf{c}$ и матрицу $K$, открытый текст восстанавливается умножением на обратную матрицу:

$\mathbf{p} = K^{-1} \cdot \mathbf{c} \pmod{26}.$

Для матрицы $2 \times 2$

$K = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$

обратная матрица вычисляется по формуле:

$K^{-1} \equiv (\det K)^{-1} \begin{pmatrix} d & -b \\ -c & a \end{pmatrix} \pmod{26},$

где $(\det K)^{-1}$ - мультипликативное обратное определителя по модулю 26, то есть такое число $x$, что $\det(K) \cdot x \equiv 1 \pmod{26}$.

Для $\det = 9$ нужно найти $x$: $9x \equiv 1 \pmod{26}$. Перебором или расширенным алгоритмом Евклида: $9 \cdot 3 = 27 \equiv 1 \pmod{26}$, поэтому $(\det K)^{-1} = 3$.

$K^{-1} = 3 \cdot \begin{pmatrix} 5 & -3 \\ -2 & 3 \end{pmatrix} \equiv \begin{pmatrix} 15 & -9 \\ -6 & 9 \end{pmatrix} \equiv \begin{pmatrix} 15 & 17 \\ 20 & 9 \end{pmatrix} \pmod{26}.$

Проверка: шифртекст TC = [19, 2],

$K^{-1} \cdot \begin{pmatrix} 19 \\ 2 \end{pmatrix} = \begin{pmatrix} 15 \cdot 19 + 17 \cdot 2 \\ 20 \cdot 19 + 9 \cdot 2 \end{pmatrix} = \begin{pmatrix} 319 \\ 398 \end{pmatrix} \equiv \begin{pmatrix} 7 \\ 8 \end{pmatrix} \pmod{26}.$

Получаем [7, 8] = HI - верно.

Почему именно mod 26

Выбор 26 объясняется размером латинского алфавита. Арифметика по модулю 26 превращает множество {0, 1, ..., 25} в кольцо $\mathbb{Z}_{26}$ с операциями сложения и умножения. В этом кольце не каждый ненулевой элемент имеет обратный (например, 13 и чётные числа не имеют), поэтому и матрица ключа не произвольна: нужно, чтобы её определитель был обратимым элементом $\mathbb{Z}_{26}$.

Для кириллического алфавита из 32 букв или для алфавита из 256 ASCII-символов схема работает точно так же - просто меняется модуль.

Рассчитать для своей задачи

Частые ошибки

• Забыть взять результат по mod 26. После умножения матрицы на вектор каждый элемент может быть больше 25. Без операции mod 26 получится не буква, а выход за пределы алфавита.
• Использовать матрицу с необратимым определителем. Если $\gcd(\det(K) \bmod 26, 26) \ne 1$, дешифрование невозможно. Перед выбором ключа проверяй определитель.
• Подставить отрицательный остаток. В некоторых языках программирования $-9 \bmod 26$ даёт $-9$, а не $17$. Используй формулу $((x \% 26) + 26) \% 26$.
• Перепутать порядок умножения. Умножение матриц некоммутативно: $K \cdot \mathbf{p} \ne \mathbf{p} \cdot K$. Вектор открытого текста - столбец справа.
• Считать матрицу ключа обычной вещественной обратной. Обратная матрица в $\mathbb{Z}_{26}$ вычисляется с мультипликативным обратным определителя по модулю 26, а не как $1/\det$.

FAQ

Чем шифр Хилла отличается от шифра Цезаря и Виженера? Шифр Цезаря и Виженера шифруют каждую букву независимо (монографические шифры). Шифр Хилла - полиграфический: одна буква шифртекста зависит от нескольких букв открытого текста одновременно. Это делает частотный анализ одиночных символов неэффективным - хотя Хилл не устоит перед анализом биграмм при большом объёме текста.

Какой размер матрицы лучше использовать? Чаще всего в учебных задачах берут матрицу $2 \times 2$ - для неё все расчёты можно сделать вручную. Матрица $3 \times 3$ позволяет шифровать тройки букв сразу и устойчивее к атакам, но расчёт обратной матрицы сложнее. На практике шифр Хилла давно вытеснен современными алгоритмами, однако как учебный пример линейной алгебры в криптографии он остаётся актуальным.

Как атаковать шифр Хилла, зная несколько пар открытый-шифртекст? Это атака на основе известного открытого текста (known-plaintext attack). Если известны $n$ пар $(\mathbf{p}_i, \mathbf{c}_i)$ для $n \times n$-матрицы ключа, их можно собрать в матричное уравнение $C = K \cdot P$ и найти $K = C \cdot P^{-1} \pmod{m}$. При матрице $2 \times 2$ достаточно двух пар, у которых матрица $P$ обратима над $\mathbb{Z}_{26}$.

Коротко

Шифр Хилла шифрует блоки букв умножением числового вектора на ключевую матрицу по модулю 26. Формула $\mathbf{c} = K \cdot \mathbf{p} \pmod{26}$ связывает каждую букву шифртекста сразу с несколькими буквами открытого текста. Дешифрование требует обратной матрицы над $\mathbb{Z}_{26}$, которая существует тогда и только тогда, когда $\gcd(\det(K) \bmod 26, 26) = 1$. В курсах дискретной математики и криптографии этот шифр служит наглядным примером применения линейной алгебры к защите информации.