Математики, шпионы и хакеры. Кодирование и криптография

БЛЕСТЯЩИЙ УМ

Алан Тьюринг (слева) родился в Англии в 1912 г. Даже в молодости он демонстрировал большие способности к математике и физике. В 1931 г. он поступил в Кембриджский университет, где увлекся работами логика Курта Гёделя по общей проблеме неполноты любой логической системы. За три года до того он опубликовал работу о теоретической возможности создания машины, способной выполнять вычислительные алгоритмы, такие как сложение, умножение и т. д.

Вдохновленный работами Гёделя, Тьюринг в 1937 г. развил свои идеи о доказательствах и вычислениях и сформулировал принцип «универсальной машины», способной выполнять любые мыслимые алгоритмические действия. Так появилась одна из основ современной информатики. За два года до того Тьюринг познакомился с крупным венгерским математиком Яношем фон Нейманом, который к тому времени жил в Соединенных Штатах и носил имя Джон. Фон Нейман, считающийся «вторым отцом» информатики, предложил Тьюрингу хорошо оплачиваемую и престижную работу в Принстоне. Однако Тьюринг предпочел богемную атмосферу Кембриджа и отклонил предложение.

В 1939 г., когда началась война, он присоединился к британской команде криптоаналитиков в Блетчли-Парке. За свою работу во время войны он был награжден Орденом Британской империи. Но Тьюринг был гомосексуалистом, что было запрещено законом в то время, и в результате приговора в 1952 г. потерял право работать на секретных проектах правительства. Глубоко подавленный, Алан Тьюринг покончил жизнь самоубийством 8 июня 1954 г., приняв цианистый калий.

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

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

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

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

Нововведения: шифр Хилла

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

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

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

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

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

* * *