Как шутят математики. Решение первого шифра Олама

Не так давно в одной из статей я уже касался темы, краешком связанной с Манхэттенским проектом, и этот материал также имеет к нему некоторое отношение. Более того, учитывая масштаб и количество участников проекта, я наверняка буду его упоминать и в некоторых последующих текстах. Эта статья написана на основе исследования американского разработчика программного обеспечения Пола Релкина.

Итак, Лос-Аламос объединил одной целью многих видных учёных того времени. Одним из них был замечательный учёный Ричард Фейнман. Разумеется, основным предметом его интереса всегда была физика, но помимо потрясающих познаний в ней, профессор Фейнман отличался и другими талантами. Из его автобиографии (всем, кто ещё не читал, настоятельно рекомендую) известен факт, что профессор особенно гордился своими реактивными скилами решения головоломок и математических задач.

Ричард Фейнман не только был гениальным физиком, но и отличным математиком, правда, сам себя таковым никогда не считал и даже шутил по этому поводу. Помимо этого, он обладал великолепным чувством юмора, которое в совокупности с остальными его талантами иногда приводило к весьма забавным анекдотичным историям, некоторые из которых можно узнать из его автобиографической книги. Другие же появляются в книгах тех, кто писал о нём.

Меня очень забавляли мои собственные попытки быстрого выполнения арифметических действий с помощью хитрых приемов...

Однажды во время обеденного перерыва он заявил, что сможет решить любую задачу, которую можно сформулировать за 10 секунд, с точностью до 10% за одну минуту. Хотя профессор и решил все предложенные коллегами задачи, в этом испытании он потерпел поражение от своего друга, математика Пола Олама. Задача, из-за которой профессор влип, сводилась к вычислению тангенса десяти в сотой степени, а это тот ещё подвиг, требующий вычисления числа Пи с точностью до 100 знаков. На Хабре есть годная статья на эту тему.

После окончания Гарварда Пол Олам приехал в Принстонский университет, чтобы получить учёную степень по физике. Так Джон Уилер, автор терминов «чёрная дыра» и «червоточина», получил ещё одного аспиранта, помимо Ричарда Фейнмана. На протяжении многих лет оба наслаждались дружеским интеллектуальным троллингом, в том числе соревновались друг с другом в расшифровке зашифрованных сообщений. Уже после войны и смерти первой супруги Фейнман работал в Калифорнийском технологическом институте. В архивах хранятся оригиналы части его работ и записей, среди которых есть два ранее не разгаданных шифра, отправленных учёному его другом-математиком. Эти шифры, обозначенные как “Olum I” и “Olum II”, оставались неразгаданными более 75 лет.

Помимо этого, существуют ещё как минимум три других закодированных задачи, заданных Фейнману во время его пребывания в Лос-Аламосе. Чаще всего их называют «шифрами Фейнмана». В конце 1970-х годов Фейнман передал эти шифры своему аспиранту Крису Коулу. 20 декабря 1987 года Коул разместил в Usenet сообщение с этими шифрами. В этом посте он написал: «Когда я был аспирантом Калифорнийского технологического института, профессор Фейнман показал мне три шифра, которые ему отправил коллега из Лос-Аламоса и которые он так и не смог взломать. Мне это тоже не удалось. Теперь я выкладываю их в сеть, чтобы кто-нибудь попробовал это сделать».

Первый шифр Фейнмана с пометкой “Easier”, был вскрыт на следующий день Джеком Моррисоном из научно-исследовательской лаборатории НАСА (Jet Propulsion Laboratory). Сообщение было зашифровано с помощью транспозиционного шифра 5×76. Расшифрованное сообщение представляет собой первые 12 строк общего пролога «Кентерберийских рассказов» Джеффри Чосера, написанного на среднеанглийском языке. Второй и третий шифры, помеченные как “Harder” и “New Message” соответственно, оставались нерешёнными до середины прошлого года.

В отличие от шифров Олама, автор которых чётко указан, достоверно неизвестно, кто из коллег профессора Фейнмана является автором этих трёх шифров. Итак, перейдём, собственно, к первому шифру Олама.

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

Следуя догадке Фейнмана о том, что шифр содержит простую замену, было принято решение использовать алгоритм Томаса Якобсена, одного из разработчиков IO Interactive и автора алгоритмов трёхмерного поиска пути для легендарной игры Hitman: Codename 47.

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

Алгоритму необходимо вычислить матрицу распределения только один раз, а последующая оценка открытого текста выполняется с помощью манипуляций этой матрицей, а не путём расшифровки и повторного анализа полученного открытого текста на каждой итерации. То есть алгоритм делает первоначальное предположение о ключе шифрования, а затем итеративно корректирует решение для оптимизации частотного распределения символов, ожидаемых для данного целевого языка. Применительно к шифру Олама это давало в основном случайный текст с несколькими реальными, но абсолютно несвязанными английскими словами (А):

Поскольку первый шифр Фейнмана был закодирован снизу вверх, с шифром Олама была произведена та же операция, но результат опять оказался далёк от совершенства, хотя и выявил ряд возможных английских фраз с ошибками в написании.

Хотя программы-решатели нередко возвращают случайные слова, повторение правдоподобных последовательностей слов типа theywwillbhepidcukehdup и thleywillhbepicrkedsuvp в перевёрнутом и заменённом зашифрованном тексте (Б) послужило некоторым поводом для воодушевления.

Учитывая, что большинство возможных слов-кандидатов включали лишние буквы, казалось вероятным, что шифрование включало либо случайную, либо систематическую вставку нулевых символов. Определив слова, которые можно было прочитать с относительно высокой уверенностью, можно попробовать выявить закономерность в расположении нулевых букв. Количество пробелов между нулевыми буквами в исходном шифре соответствует последовательности 14142135624, которая распознаётся как округление до десяти знаков после запятой квадратного корня из 2. На рисунке ниже показан образец включения нулевых букв, когда исходный зашифрованный текст (до переворота) форматируется в строки по 44 символа, представляющие длину повторяющегося квадратного корня из двух шаблонов.

В расшифрованном тексте были очевидны три числовых значения (два адреса и одна дата). За датой “Monday August” следовал символ “W”, что не дало значимого результата при применении соответствующей алфавитной замены “E”, исходя из предположения, что, когда вместо букв использовались числовые значения, применялись разные замены.

В шифре содержится сообщение о доставке посылок на объект в Лос-Аламосе. Хотя адрес Манхэттенского проекта был тщательно охраняемым секретом, его расположение по адресу 109 East Palace Avenue в Санта-Фе, штат Нью-Мексико, и почтовый абонентский ящик №1663 в Санта-Фе, использовавшийся для доставок, был рассекречен после войны. На основе этих адресов можно было применить числовые замены, но всё ещё оставалась некоторая неопределённость относительно числовой замены даты.

Четыре однозначные календарные даты, выпадающие на понедельник августа, произошли во время пребывания Фейнмана и Олама в Лос-Аламосе: 2 и 9 августа 1943 года, 7 августа 1944 года и 6 августа 1945 года.

9 августа 1943 года и 6 августа 1945 года маловероятны, поскольку 6 и 9 закодированы другими буквами в почтовых адресах, указанных выше. Дополнительные сведения о дате в шифре были получены из рассекреченных документов в архивах Лос-Аламоса, в которых описывалось изменение в управлении и месте закупочных операций для Манхэттенского проекта. Возможное отношение к сообщению в шифре Олама имеет рассекреченный отчёт Комиссии по атомной энергии от декабря 1947 года, в котором говорится: «Г-н. Джеймс Харман отвечал за закупки до июля 1943 года. Первоначально офис находился на территории Проекта, но [в] середине 1943 года он был перенесён в здание Бишопа в Санта-Фе, и его возглавил г-н Питер А. Карран». Тот факт, что отдел закупок переехал в место, указанное в шифре, летом 1943 года, позволяет предположить, что сообщение в шифре Олама относится к дате 2 августа 1943 года.

Итак, что мы получаем. Первый шифр Олама решается путем исключения символов с интервалом, определяемым первыми 11 цифрами квадратного корня из 2, переворачивания зашифрованного текста и последующего применения буквенно-цифровой замены.

Добавление знаков препинания и заглавных букв приводит к появлению сообщения, описывающего процесс отправки почтовых отправлений для получения и доставки на секретный объект в Лос-Аламосе.

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

Методы шифрования, использованные при создании первого шифра Олама, были широко известны в то время, когда Фейнман и Олам жили в Лос-Аламосе. Судя по объёму рукописных заметок Фейнмана, видно, что он потратил немало времени, пытаясь найти решение этого шифра. К чести профессора, он был совершенно прав, предположив, что шифр предполагает простую замену. Однако он ошибся, решив, что речь идёт ещё и о перестановке. Фейнман, по-видимому, не догадался, что Олам вставил левые буквы по всему сообщению с интервалом, соответствующим первым 11 цифрам квадратного корня из 2, и шифр нужно читать задом наперёд. Учитывая относительно простой характер шифра, несколько удивительно, что он поставил профессора Фейнмана в тупик и оставался неразгаданным более 75 лет.

Вполне возможно, что пустые буквы, которые необходимо удалить из зашифрованного текста, могут содержать другое сообщение, и его ещё предстоит расшифровать. Эти буквы в порядке появления, следующие:

EBESBSBSBBXBBBFEBBEBMSBSBBSBXAGBYFEMXEVBOBBJSPYBABIJXMPBBBJIOBYACSSVEBEVSVEBEPSSABFBYFDCBEIBACCVBABSBEAOVAEAEEEXEVSJAFVBBOBIVBAGEBMPMPYMXSBYVBBDGAVBEJVBMSVOCBSMBBGBBIMBJBBBBYMSDVEDVGSBDS

Есть несколько примечательных повторяющихся последовательностей, таких как SBSBSBBX/SBSBBSBX, VBOBB/VBBOB и SVEBE/SVEBE. Однако частоты символов весьма своеобразны и не типичны для английского языка.

Используется всего 16 уникальных букв, причем 12 из 16 встречаются 5 или кратно 5 раз. Буквы, встречающиеся менее 10 раз, представляют собой последовательные биграммы: CD, FG, IJ, OP, XY. Эти функции снижают вероятность того, что дополнительное сообщение будет закодировано нулевыми символами этого же шифра.

В случае если левые буквы не содержат второго сообщения, возможно, профессор Олам выбрал эти необычные частоты символов для противодействия частотному анализу. Заметки Фейнмана свидетельствуют о том, что он пытался применять частотный анализ. Он обнаружил, что “B” — наиболее часто встречающаяся буква, и сопоставил её с “E” в английском тексте. Однако частота буквы “B” была увеличена за счёт вставки 55 нулевых букв. В шифре буква “B” фактически заменяется менее распространенной буквой “S”. Аналогичным образом, из-за 20 случаев использования пустой буквы “S” профессор Фейнман сопоставил “S” с буквой “H” вместо гораздо менее распространенной буквы “V”. Это говорит о том, что профессор Олам, возможно, увеличил количество низкочастотных букв, чтобы свести на нет частотный анализ.

Заметки профессора также включают перечисление возможных транспозиций зашифрованного текста. Фейнман ошибочно заявил, что шифр «представляет собой простую замену с некоторой неполной перестановкой». Вероятно, он пришел к такому выводу из-за нескольких последовательностей в зашифрованном тексте, содержащих одни и те же буквы в несколько ином порядке. Решение шифра показало, что эти очевидные перестановки на самом деле представляют собой одни и те же последовательности, изменённые включением нулевых букв (например, PAGGNE и APGGNE, где “A” — нулевой символ). Возможно, Олам выбрал определённые нулевые символы, чтобы создать видимость использования транспозиции.

Ник Пеллинг написал пост, в котором указал, что автор трёх шифров Фейнмана неизвестен, и предположил, что автор мог быть членом британской миссии в Лос-Аламосе. На основе этого предположения у автора расшифровки появилась идея применить лексикографический анализ к первому декодированному сообщению в попытке получить дальнейшее представление о его авторстве. Основой для анализа послужило своеобразное написание определённых слов в «Кентерберийских рассказах» в различных транскрипциях, опубликованных на протяжении многих лет. «Кентерберийские рассказы» переписывались и переиздавались бесчисленное количество раз. Среди множества различных опубликованных изданий есть несколько своеобразных.

Хотя отдельные строки во многих различных изданиях пишутся одинаково, было обнаружено, что 12 строк первого шифра Фейнмана, взятые вместе, достаточно уникальны, чтобы соответствовать только одной опубликованной транскрипции. Чтобы найти издание, на котором основан этот текст шифра, была проведена огромная поисковая работа. Оказалось, что единственной версией пролога, соответствующей шифру, было первое издание полного собрания сочинений Чосера американского кельтиста Фреда Норриса Робинсона. Существуют несколько различных изданий этой транскрипции, опубликованных между 1933 и 1938 годами, которые мог бы использовать автор шифров Фейнмана.

Автор предположительно был владельцем одной из книг, содержащих первое издание транскрипции Робинсона Чосера, или, по крайней мере, имел доступ к её копии в Лос-Аламосе.

Мог ли Пол Олам быть автором шифров Фейнмана? Безусловно. Описание Фейнманом остроумия приятеля в своей биографии кажется вполне совместимым с тем, кто составил бы шифр на среднеанглийском языке. К тому же есть по крайней мере одно сходство в способе кодирования двух шифров. Оба они были закодированы обратным порядком. Для дальнейших исследований автор связался с профессором Кеном Оламом, чтобы узнать, есть ли среди вещей отца сочинение Чосера. Оказалось, что есть, правда, в другой транскрипции. Хотя всё ещё возможно, что Пол Олам был автором шифров Фейнмана, но теперь вероятность этого несколько снизилась, и вопрос авторства шифров Фейнмана остаётся открытым.

Хотя криптографические методы, использованные в первом шифре Олама, были относительно простыми, его разработка одноалфавитной замены оказалась достаточно эффективной, чтобы превзойти гений Ричарда Фейнмана и оставаться неразгаданной в течение многих десятилетий. Решение шифра придаёт дополнительные оттенки историческому моменту, когда два блестящих учёных, участвовавших в одном из самых масштабных научных проектов ХХ века, на время отвлекались от секретных работ на обмен шифрованными головоломками.

НЛО прилетело и оставило здесь промокод для читателей нашего блога:
-15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.