Шифры, обсуждавшиеся прежде, в которых один символ заменялся другим по некоторому заранее установленному правилу, как мы уже видели, всегда уязвимы для криптоанализа.

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

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

Чтобы зашифровать сообщение, мы будем использовать следующие матрицы:

с определителем, равным единице, то есть ad — Ьс = 1. Для расшифровки мы будем использовать обратную матрицу:

* * *

* * *

Ограничение на значение определителя установлено для того, чтобы обратная матрица работала как инструмент расшифровки. Как правило, для алфавита из n символов необходимо, чтобы НОД определителя матрицы и числа n равнялся единице. Иначе нельзя гарантировать существование обратного элемента в модульной арифметике.

Продолжая пример, возьмем алфавит из 26 букв с символом пробела, который мы обозначим как @. Каждой букве мы поставим в соответствие число, как показано в следующей таблице:

Для получения значений от 0 до 26 мы будем работать по модулю 27.

Процесс шифрования и расшифровки текста происходит следующим образом: сначала мы определяем шифровальную матрицу с определителем 1.

Например,

Матрицей для расшифровки будет обратная матрица

Таким образом, А будет ключом шифра, А^-1 — ключом для расшифровки.

Например, зашифруем сообщение BOY («мальчик»). Буквы сообщения группируются в пары: ВО У@. Их численными эквивалентами, согласно таблице, являются пары чисел (1, 14) и (24, 26). Умножим матрицу А на каждую пару чисел.

Зашифрованное

что, согласно таблице, соответствует буквам (Q, Т).

Зашифрованное

что соответствует буквам (V, О).

Сообщение BOY будет зашифровано как QTVO.

Обратная операция расшифровки выполняется при помощи матрицы:

Возьмем пару букв (Q, Т) и найдем их числовые эквиваленты из таблицы: (16, 19). Затем умножим их на A^-1 и получим:

то же со второй парой (V, О) и ее численными значениями (21, 14) и получаем:

Таким образом, мы доказали, что расшифровка работает.

В этом примере мы рассматривали пары символов. Для большей безопасности можно группировать буквы по три или даже по четыре. Тогда расчеты будут проводиться с матрицами порядка 3 х 3 и 4 х 4 соответственно, что было бы чрезвычайно трудоемким процессом для вычислений вручную. Современные компьютеры позволяют работать с огромными матрицами и с обратными к ним.

У шифра Хилла есть существенный недостаток: имея даже небольшой фрагмент исходного текста, можно расшифровать все сообщение. Поиск идеального шифра был еще далек от завершения.