Математики, шпионы и хакеры. Кодирование и криптография - [20]
Шифровальщики навахо
Хотя Соединенные Штаты умело использовали информацию, перехваченную у противника во время военных действий на Тихом океане, американские военные для собственной связи применяли несколько шифров, по сути похожих на те, о которых говорилось в начале книги. Алгоритмы шифрования были основаны непосредственно на природе слов. Эти шифры — чокто, команче, месквоки и прежде всего навахо — не были четко описаны в сложных руководствах и не были результатом работы отделов криптографии: это были просто подлинные языки индейцев.
Армия Соединенных Штатов включала радистов из этих племен в отделы шифровальщиков на фронте, чтобы они передавали сообщения на своих языках, на которых не говорили не только японцы, но и другие американские военные. Эти сообщения дополнительно шифровались простыми кодами, чтобы захваченные в плен солдаты не смогли их перевести. Такие радисты служили в американских отделах вплоть до Корейской войны.
Два шифровальщика навахо во время битвы за Бугенвиль в 1943 г.
Шифры, обсуждавшиеся прежде, в которых один символ заменялся другим по некоторому заранее установленному правилу, как мы уже видели, всегда уязвимы для криптоанализа.
В 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 соответственно, что было бы чрезвычайно трудоемким процессом для вычислений вручную. Современные компьютеры позволяют работать с огромными матрицами и с обратными к ним.
У шифра Хилла есть существенный недостаток: имея даже небольшой фрагмент исходного текста, можно расшифровать все сообщение. Поиск идеального шифра был еще далек от завершения.
Глава 4. Процесс общения посредством нулей и единиц
Изобретение компьютера Colossus и расшифровка кода «Энигмы» открыли путь к величайшей революции в сфере коммуникаций. Этот гигантский шаг вперед произошел в значительной степени благодаря развитию систем шифрования, что обеспечило безопасную, эффективную и быструю связь по разветвленным сетям, представляющим собой компьютеры и их пользователей — то есть нас с вами. Когда сегодня мы употребляем слово «безопасность», мы имеем в виду не только криптографию и секретность. Это слово имеет более широкий смысл, который включает в себя понятия надежности и эффективности.
Двоичная система является основой технологической революции. Этот суперпростой код, содержащий лишь два символа, 0 и 1, используется в цифровых устройствах из-за его способности представлять состояние электронных схем: единица означает, что в контуре есть ток, ноль — тока нет. Одна двоичная цифра — 0 или 1 — называется битом.
