Решение 340-символьного шифра Зодиака с помощью Mathematica

Зодиак (неопознанный американский серийный убийца, действовавший в 60-х и 70-х годах прошлого века) отправил множество издевательских писем в прессу города Сан-Франциско. В этих письмах убийца брал на себя ответственность за преступления и угрожал совершить новые убийства. Письма также содержали три шифра, каждый из которых являлся частью 408-символьной криптограммы. Убийца утверждал, что эта криптограмма раскроет секрет его личности. Зодиак отправил четвертый и последний шифр (который рассматривается в этой статье) в San Francisco Chronicle после того, как 408-символьная криптограмма, расшифрованная в 1969 году, не раскрыла личность убийцы.

Коротко о Z340

Меня вдохновило видео Дэвида Оранчака, в котором рассматривается 340-символьный шифр Зодиака (Z340). Этот шифр — один из святых Граалей криптографии, так как его не могли разгадать на протяжении 50 лет.

В своем видео Дэвид высказал идею о том, что Z340 — это одновременно и омофоническая замена, и перестановочный шифр. На данный момент существуют различные эффективные программы для решения омофонических шифров и лучшей из них считается AZdecrypt. Эксперименты показывают, что AZdecrypt способна решить все омофонические шифры с той же длиной и распределением символов, что и у Z340. Но, к сожалению, AZdecrypt не может расшифровать его. Возможно, решение заключается в поиске правильного перестановочного шифра с последующим использованием AZdecrypt для решения омофонического шифра замены.

Период-19

Дэвид выделил одну конкретную перестановку, которую нашли независимо друг от друга и разместили на zodiackillersite.com пользователь «daikon» и Ярл ван Эйке (автор AZdecrypt) — «период-19».

Ради интереса я решил построить её с помощью Mathematica:

Однако это не было похоже на перестановку, которую нашли daikon и Ярл ван Эйке. К моему удивлению, оказалось, что в их перестановке при переходе с последней строки на первую использовался период, равный 18.

Хотя эта перестановка внешне выглядела интересно, она не показалась мне естественной конструкцией, которую можно сделать на листе бумаги. Стоит отметить, что Z340 был составлен в 1969 году и поэтому наверняка он создавался вручную без использования компьютера. 

Я увидел связь между перестановкой с периодом 19 и 1,2-децимацией шифра 20x17.

Эта перестановка принимает диагонали, аналогичные перестановке с периодом 19:

Выполнение 1,2-децимации Z340 через AZdecrypt не дало решения.

Подсчет биграмм

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

В системе Mathematica легко написать код для произвольных n-грамм:

Затем мы можем построить большое количество шифров, подобных Z340, и сравнить распределение числа биграмм в них с большим количеством случайных перетасовок Z340:

Среднее количество биграмм для случайных перетасовок составило 19,8, а для случайных шифров, подобных Z340, — 34,5. Z340 имеет 25 повторяющихся биграмм, в то время как перестановка с периодом 19, которую нашли daikon и Ярл, и 1,2 децимация имеют 37 повторяющихся биграмм. Таким образом, статистически можно предположить, что мы находимся на правильном пути.

Перебор возможных перестановок

После того, как прогон 1,2-децимации через AZdecrypt не дал решения, мы решили работать над поиском среди большого числа потенциальных перестановок. Было сложно выяснить, какие перестановки проверялись в прошлом, поэтому я решил пронумеровать все приемлемые перестановки, отсортировать их по количеству биграмм и пропустить через AZdecrypt. Вот, некоторые из этих перестановок:

Я также включил все перестановки, соответствующие одномерным и двумерным децимациям. Для одномерных перечислений всех чисел, взаимно простых с 340 (чтобы заполнить весь массив) у нас есть следующие 128 соответствующих децимаций:

Для двумерных перечислений у нас есть следующие 128 соответствующих децимаций:

Например, 3,4-децимация порождает следующую перестановку:

Используя AZdecrypt, мы протестировали все перестановки с разными правилами расположения элементов: row-major, column-major, чередование строк и столбцов, чередование столбцов и строк, по внешним и внутренним спиралям, по диагоналям, а также построенные выше одномерные и двумерные децимации. Эксперимент не дал ничего похожего на решение, поэтому мы протестировали все пары перестановок. Затем мы рассмотрели возможность тестирования всех упорядоченных троек перестановок; однако для этого потребуется проверить 155 929 364 660 224 потенциальных шифров. Если предположить, что проверка одного шифра занимает одну секунду, то для полного перебора потребовалось бы более пяти миллионов лет. Поэтому мы решили ограничиться децимациями, которые можно было бы составить от руки, а затем протестировали потенциальные шифры с большим количеством биграмм. И этот поиск тоже ничего не дал.

Сегментация исходного шифра

Возможно, мы упускаем еще один шаг. Учитывая то, что 408-символьный шифр Зодиака был отправлен в виде трех одинаковых по размеру фрагментов, мы предположили, что Z340 построен из отдельных сегментов, а затем зашифрован с перестановкой и омофонической заменой:

Мы рассмотрели разделение шифра на несколько сегментов:

Затем мы использовали Reduce для вычисления всех возможных 2x2 сегментов:

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

Поиск композиций из нескольких перестановок и всех комбинаций перестановок для всех сегментов будет значительно более масштабным мероприятием. Поэтому мы решили повторно проанализировать результаты первоначального поиска. Из 650 000 протестированных перестановок одна содержала несколько особенно интересных сегментов открытого текста:

Это было интересно, поскольку тестируемой перестановкой оказалась 1,2-децимация с разделением шифра на три вертикальных сегмента:

Исследуя этот результат, Дэвид использовал полученное разделение, 1,2-децимацию и AZdecrypt с известными фрагментами текста: «HOPE YOU ARE», «TRYING TO CATCH ME» и «THE GAS CHAMBER». С помощью этого  AZdecrypt нашел следующее решение для первого сегмента:

Эврика! Спустя 51 год мы расшифровали часть Z340. Это был особенный момент. А как насчет оставшихся двух сегментов? Возможно, мы нашли только одно правильное вертикальное разделение из 9 строк, а оставшиеся 11 строк требовали другой сегментации. Или, возможно, требовалась другая перестановка, или даже другой ключ для шифра подстановки, отличающийся от полученного для первого сегмента, или все вместе взятое. Наша работа была далека от завершения.

Дальнейший криптоанализ

Дэвид обнаружил, что мы можем использовать ключ из первого сегмента к последнему сегменту для создания следующего открытого текста — без каких-либо перестановок:

Открытый текст, включая некоторые пробелы, выглядит так:

Затем, перевернем некоторые слова:

Это показалось вполне реалистичной расшифровкой последнего сегмента.

А как насчет второго сегмента? Если использовать в виде crib-фразы весь разборчивый текст из первого сегмента, мы получим следующую расшифровку:

Некоторые части этого текста имели смысл, но мы, конечно, еще не достигли желаемого результат. Мы попросили Ярла ван Эйке, автора AZdecrypt, помочь нам с этим сегментом. Он сделал следующие наблюдения:

• Открытый текст LIFEIS исключается из 1,2-децимации и читается слева направо.

• Многочисленные орфографические ошибки исправляются, если «H» в шестой строке переместить в четвертый столбец.

• Нужно применить 1,2-децимацию, пропуская позиции, содержащие «LIFEIS»:

Тогда второй сегмент станет таким:

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

Эпилог

Полное послание в примерном переводе звучит так:

«Надеюсь, вы повеселились, пытаясь меня поймать. Это был не я на ТВ-шоу. Кстати, обо мне. Я не боюсь газовой камеры, потому что она отправит меня в рай пораньше, и потому что у меня есть достаточно рабов, которые будут работать на меня там, где ни у кого другого нет ничего, когда они прибывают в рай. Поэтому они боятся смерти. А я не боюсь, потому что я знаю, что моя новая жизнь будет легкой в раю. Смерть».

Спустя пятьдесят один год после того, как Зодиак отправил этот шифр в San Francisco Chronicle, у нас появилось решение. Дэвид отправил его в отдел криптоанализа ФБР в субботу, 5 декабря 2020 г. Вскоре после этого ФБР официально подтвердило правильность нашего решения.

По сути, вся моя работа над Z340 выполнялась в системе Mathematica. Я использовал кластер высокопроизводительных вычислений Spartan в Мельбурнском университете, чтобы исключить возможные перестановки с помощью zkdecrypto, а Дэвид использовал AZdecrypt. В остальном весь статистический анализ Z340, а также создание и анализ миллионов возможных перестановок были выполнены с помощью Mathematica. Причина, по которой я использовал Mathematica, проста: это самый оптимальный и эффективный инструмент для решения данной задачи.

Автор: Stedihabr

Источник