Шифры,
обсуждавшиеся прежде, в которых один символ заменялся другим по
некоторому заранее установленному правилу, как мы уже видели, всегда
уязвимы для криптоанализа. В
1929 г. американский математик Лестер Хилл придумал, запатентовал и
выставил на продажу — правда, без особого успеха — новую систему
шифрования, в которой использовались и модульная арифметика, и линейная
алгебра. Как
мы увидим ниже, матрицы являются очень полезным инструментом для
шифрования сообщений, когда текст разбивается на пары букв и каждой
букве ставится в соответствие числовое значение. Чтобы зашифровать сообщение, мы будем использовать следующие матрицы: с определителем, равным единице, то есть ad — Ьс = 1. Для расшифровки мы будем использовать обратную матрицу: * * * НЕМНОГО ЛИНЕЙНОЙ АЛГЕБРЫ Матрица может быть определена как таблица, представляющая собой совокупность строк и столбцов. Например, матрица 2x2 имеет вид: а матрица 2x1 записывается как: Произведение этих двух матриц дает нам новую матрицу 2x1, называемую вектор-столбцом: В случае матрицы 2x2 число (аd — Ьс) называется определителем матрицы. * * * Ограничение
на значение определителя установлено для того, чтобы обратная матрица
работала как инструмент расшифровки. Как правило, для алфавита из 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 соответственно, что было
бы чрезвычайно трудоемким процессом для вычислений вручную. Современные
компьютеры позволяют работать с огромными матрицами и с обратными к ним. У
шифра Хилла есть существенный недостаток: имея даже небольшой фрагмент
исходного текста, можно расшифровать все сообщение. Поиск идеального
шифра был еще далек от завершения.
|