Как шутят математики. Решение второго шифра Олама
В предыдущей статье я писал о дешифровке первого шифра Олама и некоторых особенностях юмора в продуктовой команде Манхэттенского проекта. В этом материале речь пойдёт о вскрытии второго шифра Олама. Напомню, что первый шифр представлял собой простой одноалфавитный шифр замены. Он был зашифрован в обратном порядке с избыточными символами, вставленными с интервалами, соответствующими цифрам квадратного корня из 2.
Оба шифра оставались неразгаданными 75 лет. Скорее всего, виной тому оказался тот факт, что они находились в архивных хранилищах Калифорнийского технологического института, а не из-за их чрезвычайной сложности. Однако не стоит забывать, что в момент своего появления они не были вскрыты Ричардом Фейнманом, а после и его аспирантом Крисом Коулом. Разумеется, с тех пор криптоанализ существенно продвинулся и обзавёлся новыми возможностями автоматизации и вычислительными мощностями.
Шифры Олама привлекли к себе внимание совсем недавно в результате выставки некоторых архивных документов института в 2018 году. Впоследствии один из пользователей reddit разместил фото шифра «Olum II» вместе с предположениями о применённом методе шифрования в сети. При обсуждении шифра был выдвинут ряд гипотез, главная из которых была такой: шифр является чисто транспонированным без замены символов, поскольку частотность символов в точности соответствует ожиданиям для английского языка. Однако этим всё закончилось, он так и оставался до сих пор неразгаданным. Одним из главных признаков того, что текст зашифрован чистой транспозицией, является схожесть распределения частот зашифрованного и открытого текста.
Транспонированный шифр, он же шифр перестановки, является в некотором роде антиподом шифра замены. При шифровании методом транспозиции меняется только положение символа в тексте сообщения в соответствии с определённым ключевым правилом, тогда как шифр замены не меняет место символа, а заменяет его в соответствии с ключом. Очень часто совмещают оба метода для повышения надёжности шифрования.
Также к слабостям перестановки относят проблему частично неверного ключа. То есть ключи, очень близкие к правильному ключу, обнажают огромные куски разборчивого открытого текста с небольшими вкраплениями тарабарщины. Поэтому криптонитом таких шифров всегда были алгоритмы поиска оптимума.
Для начала, прежде чем строить собственные «велосипеды», нужно попробовать доступные средства.
Существует ряд доступных программ дешифровки, например:
CryptoCrack — бесплатная программа для решения классических шифров. Может решать больше 60 различных типов шифров. В нагрузку идут словари на нескольких языках, правда, русского не завезли, но это не так уж и важно.
dCode — работает из браузера, и тут куча разных возможностей — от решения скрэббла до классических шифров. Тут разработчики дуют щёки и обещают распознать больше двух сотен шифров. В общем, судя по всему, это эдакий «швейцарский» нож.
Boxentriq — тоже довольно развитый инструмент, выросший из головоломки Boxen. Что меня больше всего привлекло, так это минималистичный шведский дизайн (разработчик — швед). Решает классические шифры, позволяет работать с текстом и проводить его анализ. Также содержит ещё вагон и маленькую тележку разных опций.
Такие программы с помощью нескольких методов вскрывают некоторые шифры замены и транспонирования, используя для выявления потенциальных ключей дешифрования частотный анализ, брутфорс, алгоритм поиска восхождением к вершине и атаки по словарю.
Хотя шифр был идентифицирован как весьма вероятный шифр транспонирования, ни одной из этих программ не удалось получить приемлемый ключ дешифрования. Значит, не всё так просто в этом шифре, и для определения возможных интервалов транспонирования необходимо использовать альтернативную форму частотного анализа.
Фотография второго шифра Олама
EEIOLCNTPATIILMNIHGUTIGLFOOOHRBYSCDEYGSEEIEELMERSBITCBAANEITGDSDDOURDMSIOMHESELEDNSRRNHNINATONWAEDSYROWHEDRTRASVAWHEODESETVIFNIEHETOIGIELNIITONARTHTHLEULIITAISLSUNFCEAINIELSLTLBPSNTMTIHSDSIHTREIENDUETHHIOMEIIASTVHPFYGSORNEEIIET (Транскрипция шифра)
Интервал транспонирования для биграмм определяется как расстояние между буквами, образующими пары биграмм. Например, в последовательности шифра «TIHSD» биграммы «TH», «IS» и «HD» обладают интервалом транспозиции +2. Для триграмм интервал транспонирования состоит из двух компонентов: один соответствует расстоянию между первой парой букв в триграмме, а другой указывает на расстояние между второй и третьей буквами. Например, в «TIHSD», «TIS» и «IHD» оба имеют интервал транспонирования +1, +2. Интервалы также могут быть отрицательными. Например, в «TIHSD» триграммы «TSI» и «IDH» имеют интервал транспозиции +3, -2.
Для этого шифра имеется всего 452 интервала транспонирования биграмм и 152550 интервалов для триграмм. В общей сложности было сгенерировано 51302 биграммы и 11542950 триграмм и рассчитаны их ожидаемые частоты в английском языке. Большее количество интервалов транспозиции содержат биграммы и триграммы, которые чаще встречаются в английском языке. Например, 8139 интервалов транспозиции содержат триграмму «THE».
После этого были рассчитаны соотношения частот триграмм английского языка к частотам, полученным в результате случайного изменения порядка зашифрованного текста, и создана метрика для оценки интервалов транспозиции путём усреднения отношений всех триграмм в заданных интервалах транспозиции. Данные расчёты позволяют создать графики, показывающие интервалы, которые содержат все триграммы. Соответственно, более высокая оценка предполагает, что интервал, скорее всего, будет частью решения по транспонированию.
Усреднённые соотношения триграмм для каждого интервала транспозиции были нанесены на трёхмерный поверхностный график, на котором отбирались значения ниже двух стандартных отклонений от среднего значения. Пики на графиках образовали линии, указывающие на то, что интервалы транспозиции, вероятно, содержали триграммы, по крайней мере, с двумя из трёх букв в правильной последовательности. Это и определило интервалы транспозиции, которые содержат триграммы, вероятно, являющиеся частями зашифрованного сообщения, а не случайными комбинациями букв. Триграммы с наивысшими баллами вручную оценивались, как возможные компоненты зашифрованного сообщения. Для дешифрования шифр был разбит на 35-буквенные фрагменты. Расшифрованные фрагменты выделены цветом. Далее для наглядности все этапы дешифрования будут в графике.
Обычно, когда производят дешифрование неизвестного шифра для проверки истинности применяемых алгоритмов, проводят тест на генерализацию (обобщаемость) на похожих шифрах с известными решениями. Соответственно, при верных решениях делается вывод о применимости алгоритма к взлому текущего шифра. Иначе легко можно принять желаемое за действительное, подгоняя шифр к алгоритму, а не наоборот.
Так вот, в качестве проверки применимости методов, использованных для расшифровки нашего шифра, к другим шифрам транспонирования, они были применены к шифрам с известными решениями: первый шифр Фейнмана (о котором я упоминал в прошлой статье), несколько шифров вертикальной перестановки и рельсовых шифров транспонирования (также известен, как зигзаг).
Когда на графике отображаются отношения частот триграмм, превышающие два стандартных отклонения от среднего значения, через определённые интервалы транспозиции становится очевидной серия линий. Для шифра Олама интервал с наивысшей оценкой равен +21, -7. Этот интервал транспозиции включает в себя возможные трёхбуквенные английские слова, такие как «NOT», «HIS», «BUT» и «THE». Для этого интервала расчёт отношений частот в английском языке к частотам при случайной перестановке букв шифра показал, что триграммы «BUT», «COU» и «THE» имеют наибольшую вероятность появления в английском языке по сравнению со случайной сортировкой зашифрованного текста.
График интервалов транспозиции, показывающий средние соотношения частот триграмм
Пики отношения частот возникают при +21, -7 и -28, все они кратны 7, а это «ж-ж-ж» — неспроста! В итоге шифр был разбит на строки длиной в семь символов, чтобы облегчить поиск последовательностей слов-кандидатов. Хотя не все шифры транспозиции содержат интервалы, имеющие общий коэффициент. Такое может произойти при применении вертикальных транспозиций и других перестановок с повторяющимися шаблонами. Как только шифр был разложен в семь рядов, сразу в глаза бросилось «COU» в начале шифра. А также буквы «LD» с интервалом +21, которые вместе образуют слово «COULD». Приняв во внимание вертикальное расположение этих букв в первых пяти строках, мы пришли к потенциальному ключу дешифрования 3, 1, 5, 4, 2.
Используя этот ключ для упорядочивания строк и чтения столбцов слева направо, мы дешифровали 35-буквенную часть шифра «THE IMPREGNABILITY OF HIS LOGIC COULD NOT», а также ещё одну часть в конце шифра: «TOLD HIM BUT HE PERSISTED IN HIS ATHEISM IN». Применение того же ключа к остальной части шифра не дало адекватных результатов.
Оставшийся шифр включает четыре блока по 35 букв, а также аппендикс из 17 букв в конце. Эти оставшиеся разделы требуют других ключей транспонирования. Необходимые ключи были найдены с помощью перечисления возможных транспозиций и банального поиска английских слов для всех разделов, кроме последнего, что выявило закономерность ключа транспонирования. В шифре используется один ключ шифрования, но он меняется после каждой 35-буквенной секции (25143, 32514, 43251, 14325, 51432). Последний раздел потребовал другого подхода, поскольку он не полон. Решение для него было найдено путём сопоставления 17 букв в исходные позиции перед транспонированием на основе вращающегося ключа.
Добавление знаков препинания и заглавных букв дало следующее сообщение:
The impregnability of his logic could not be denied. Yet, logic must be regarded as mistress only in her own domain. When she dares disagree with the revelations of divine intuition, then fallacies result. All this I told him, but he persisted in his atheism in spite of everything. | Неуязвимость его логики нельзя было отрицать. Однако логику следует считать хозяйкой только в её собственной области. Когда она осмеливается не соглашаться с откровениями божественной интуиции, возникают заблуждения. Я ему рассказал всё, но он, несмотря ни на что, упорствовал в своем атеизме. |
Учитывая успех описанного подхода при решении шифра Олама, было проведено несколько тестов его применимости к другим шифрам транспонирования с известными решениями. На рисунке ниже показан график результатов, полученных в результате применения тех же методов к шифру вертикальной перестановки и первому шифру Фейнмана. Метод успешно определил правильный интервал транспонирования (-5). Анализ частот английских триграмм, сгенерированных из зашифрованного текста, без учёта их частот при случайной сортировке шифра дал частично правильные результаты. Однако превосходные результаты были получены при использовании отношения частот английских триграмм к частотам, полученным в результате случайной сортировки зашифрованного текста. Применение этого метода оказалось успешным в получении соответствующих интервалов транспонирования для ряда других шифров перестановки.
График интервалов транспозиции для первого шифра Фейнмана
Итак, вероятный метод шифрования, использованный профессором Оламом, показан на рисунке ниже, буквы «THEIM» выделены для иллюстрации позиций в процессе шифрования. Чтобы создать этот шифр, он, вероятно, начал с разделения сообщения на строки по 5 букв, разбитые на 6 блоков по 7 строк в каждом. Остальную часть текста он разбил таким же образом, получив 4 строки. Далее он прочитал столбцы первого блока сверху вниз и разместил их в строку в порядке, указанном ключом шифрования 2, 5, 1, 4, 3. Для следующего блока из 35 букв он повторил этот процесс, но сдвинул ключ шифрования на одну позицию вправо: 3, 2, 5, 1, 4. Процесс повторяется для всех остальных блоков.
Послание, содержащееся в этом шифре, описывает тщетную попытку убедить атеиста в ограниченности логики и достоинствах божественной интуиции. Сам профессор Олам считал себя атеистом. Поиск в сети источника или автора этого текста не дал результатов. Вполне возможно, что это вообще цитата из чьей-то личной переписки, хотя это не точно. Поэтому на данный момент первоначальное авторство сообщения, содержащегося в шифре, остаётся неопределённым.
Шифры транспозиции широко использовались во время Второй мировой войны и в течение последующего десятилетия. Существует множество их вариаций, и в большинстве из них используется один ключ транспонирования в отличие от шифра Олама и некоторых других. При использовании разных ключей их чаще всего выбирают случайным образом для каждого сегмента, однако профессор Олам был математиком и решил сгенерировать последовательные ключи путем их ротации. Использование нескольких ключей шифрования заслуженно признаётся одним из средств повышения надёжности транспозиционных шифров.
Подход, предложенный в этой статье с использованием отношений частот биграмм и триграмм, даёт несколько преимуществ по сравнению с другими существующими методами. Он может работать с различными типами шифров транспонирования и не требует предварительного указания типа шифра. Методика с высокой вероятностью позволяет выявить части ключа транспонирования и последовательности букв для вскрытия шифров с обычными или нерегулярными ключами транспонирования. Необходимые расчёты можно выполнить с использованием обычных вычислительных платформ. Также подход является интерактивным в той степени, в которой он требует от пользователя применения знаний, полученных в результате частотного анализа, а не непосредственного вывода полного решения.
Несмотря на то, что успешно были дешифрованы первый шифр Фейнмана, а также оба шифра Олама, остаются неразгаданными ещё два известных шифра, связанных с Ричардом Фейнманом (о них я также писал в прошлой статье). Шифры, созданные коллегами из Лос-Аламоса для профессора Фейнмана, хоть и не кажутся сегодня чем-то из ряда вон выходящим, но тот факт, что они оставались неразгаданными более 75 лет, указывает на то, что из этих исторических шифров можно кое-чему научиться.
Стратегия шифрования сообщения Пола Олама не только сбила с толку профессора Фейнмана, но и оказалась невосприимчивой к нескольким современным программам дешифрования, предполагающим применение единообразной перестановки. Таким образом, описанный метод дешифровки может пригодиться для вскрытия других подобных шифров.
НЛО прилетело и оставило здесь промокод для читателей нашего блога:
-15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.
