Жуан Гомес - Мир математики. т.2. Математики, шпионы и хакеры. Кодирование и криптография

Шифровальщики навахо

Хотя Соединенные Штаты умело использовали информацию, перехваченную у противника во время военных действий на Тихом океане, американские военные для собственной связи применяли несколько шифров, по сути похожих на те, о которых говорилось в начале книги. Алгоритмы шифрования были основаны непосредственно на природе слов. Эти шифры — чокто, команче, месквоки и прежде всего навахо — не были четко описаны в сложных руководствах и не были результатом работы отделов криптографии: это были просто подлинные языки индейцев.

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

Два шифровальщика навахо во время битвы за Бугенвиль в 1943 г.

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

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

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

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

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

* * *

НЕМНОГО ЛИНЕЙНОЙ АЛГЕБРЫ

Матрица может быть определена как таблица, представляющая собой совокупность строк и столбцов. Например, матрица 2x2 имеет вид:

а матрица 2x1 записывается как:

Произведение этих двух матриц дает нам новую матрицу 2x1, называемую вектор-столбцом:

В случае матрицы 2x2 число ( аd— Ьс) называется определителем матрицы.

* * *

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

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

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

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

Например,

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

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

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