Как я расшифровывал имя Зодиака на научной конференции
Фрагмент шифра Зодиака Z13
Всем привет, меня зовут Сергей Па́токин, и здесь я расскажу историю про свои 18 карат невезения и участие в научной конференции.
В декабре 2020 года произошло событие, которого более пятидесяти лет ждали криптографы, журналисты и люди, добровольно изучающие переписку серийного убийцы.
Был расшифрован Z340 – один из четырёх известных шифров Зодиака, орудовавшего в конце шестидесятых годов.
С задачей справились три программиста-энтузиаста из разных стран:
Дэвид Оранчак из США;
Сэм Блейк из Австралии;
Ярл Ван Эйке из Бельгии.
Они не представляли одну государственную лабораторию и не располагали секретным суперкомпьютером. Просто три человека объединили знания, разработали необходимые инструменты и решили задачу, которая десятилетиями считалась практически неприступной.
Оригинальный шифр Z340
Z340. Триста сорок символов, несколько десятилетий попыток и три программиста, которым никто не объяснил, что подобные проекты лучше оставить на старшие курсы.
В расшифрованном тексте находилось обращение к полиции и рассуждения самого убийцы. Зодиак писал о том, что не боится казни, и продолжал поддерживать образ человека, которому известно нечто недоступное остальным.
До этого был расшифрован только Z408 – первое большое криптографическое послание Зодиака. Его разгадали ещё в 1969 году. В нём автор сообщал, что любит убивать людей, потому что это весело.
Мысль достаточно простая. Для её передачи потребовалось более четырёхсот символов и полвека внимания к личности автора.
Оставшиеся шифры продолжали сопротивляться анализу.
И вот спустя более пятидесяти лет нашлись люди, которые смогли расшифровать один из них.
О расшифровке Z340 я узнал почти сразу.
К тому моменту я уже хорошо знал биографию Зодиака, историю его преступлений, писем и публичной игры с полицией и газетами. Разумеется, я знал и о его шифрах.
Новость меня невероятно вдохновила.
Я подумал:
Смогли они – смогу и я.
На тот момент я только поступил в университет и учился на первом курсе направления «Информатика и вычислительная техника» в филиале МГТУ имени Баумана.
Я был начинающим программистом, но уже достаточно уверенно владел языками программирования и представлял алгоритмы, которые можно было реализовать для анализа другого шифра Зодиака – Z13.
Возможно, самого важного из оставшихся.
Шифр Z13
Z13 – предположительно, имя Зодиака. Всего тринадцать символов.
В сопровождавшем шифр письме Зодиак утверждал, что внутри содержится его настоящее имя.
В другой истории для решения проблемы было бы достаточно узнать имя человека и увидеть его лицо. В моей сначала требовалось расшифровать тринадцать символов, а затем каким-то образом доказать, что полученное имя действительно настоящее.
Проблема заключалась именно в длине шифра.
Для сравнения: в Z340 было триста сорок символов.
Если после расшифровки длинного сообщения получается связный текст с предложениями и устойчивым смыслом, можно с достаточно высокой уверенностью предположить, что решение найдено.
Если результатом тринадцати символов должно стать имя, вариантов становится почти бесконечно много.
Имя может быть настоящим или вымышленным, полным или сокращённым. Оно может содержать ошибку, псевдоним или дополнительный знак. Кроме того, Зодиак мог солгать.
Это предположение не требовало особенно смелой научной гипотезы.
Поэтому главная сложность состояла не в том, чтобы получить варианты расшифровки. Главная сложность – понять, что среди них есть правильный.
Я осознавал это с самого начала.
Но решил двигаться от малого: реализовать несколько возможных алгоритмов, выделить подходящие варианты и постепенно сокращать пространство поиска.
Научный проект
Весной 2021 года в университете проходила ежегодная научная конференция.
Я решил, что дешифратор Z13 станет отличной темой для проекта, пришёл на кафедру и записался.
Тема быстро стала известна среди моих однокурсников. Люди подходили, задавали вопросы, интересовались историей Зодиака и тем, каким образом я собираюсь анализировать шифр.
Я с энтузиазмом рассказывал о задумке, алгоритмах и перспективах проекта.
Постепенно о работе начали говорить преподаватели и другие сотрудники университета. На фоне стандартных студенческих разработок попытка расшифровать имя одного из самых известных неустановленных серийных убийц действительно привлекала внимание.
Первая программа
Для проекта я разработал две программы.
Первая выполняла полный перебор возможных вариантов расшифровки латинского текста.
Теоретически она гарантированно должна была обнаружить правильную последовательность – при условии, что эта последовательность вообще находилась внутри выбранного пространства поиска.
Проблема была лишь в количестве вариантов.
Полностью выполнить такой перебор на доступном мне оборудовании было невозможно из-за ограничений вычислительной мощности и памяти. Даже если бы программа завершила работу, она выдала бы огромное количество результатов, среди которых всё равно требовалось определить единственно правильный.
Но сам факт того, что нужная комбинация гарантированно присутствует среди результатов, представлялся мне интересным. Поэтому программу я реализовал как демонстрацию метода.
Технически это была конструкция с многократной вложенностью циклов.
Моя первая и, вероятно, единственная программа, в которой каждый новый уровень вложенности выглядел как ещё одна дверь, за которой находилась следующая дверь.
Код первой программы
Полный перебор. Для завершения требовались несколько тысяч лет или примерно 1,21 гигаватта.
База имён и фамилий
Вторая программа была более практичной.
Она работала с базами реальных имён и фамилий.
Готовой подходящей базы у меня не было, поэтому я начал формировать её самостоятельно. В первую очередь собирал распространённые имена и фамилии жителей США, поскольку именно там действовал Зодиак. Затем начал расширять выборку, добавляя варианты из других стран.
Имена и фамилии хранились отдельно.
Это позволяло проверять разные комбинации:
имя;
фамилию;
имя и фамилию вместе;
сокращённые варианты;
перестановки;
преобразования каждой части по отдельности.
В результате я собрал несколько тысяч имён и фамилий вручную, потому что бюджет проекта состоял из энтузиазма, свободного времени и крышек, которые университет почему-то не принимал.
Значительную часть информации приходилось искать, проверять, приводить к единому формату и вручную добавлять в локальную базу.
Я не просто написал алгоритм. Я своими силами формировал данные, на которых он должен был работать.
Фрагмент локальной базы имён и фамилий
Часть локальной базы. Несколько тысяч имён и фамилий, собранных вручную.
Первым делом я проверял сравнительно простые варианты:
прямую подстановку;
шифр Цезаря с различными смещениями;
перестановки символов;
несколько вариантов преобразования алфавита;
комбинации имён и фамилий;
сопоставление структуры повторяющихся знаков.
Постепенно я объединил несколько алгоритмов в одной программе. Она брала записи из базы, преобразовывала их разными способами и сравнивала получившиеся последовательности со структурой Z13.
Совпадений я не получил.
Ни одного.
Ни по одному из реализованных алгоритмов.
Это не было расшифровкой, но тоже представляло собой результат.
Несколько тысяч распространённых имён, несколько тысяч фамилий, различные комбинации и базовые алгоритмы не дали даже убедительного кандидата.
Это могло означать, что либо Зодиак использовал более сложный принцип шифрования, либо записал имя нестандартным способом, либо внутри вообще находилось не имя.
Был и ещё один вариант: Зодиак мог намеренно создать строку, не имеющую однозначного решения, а затем объявить, что спрятал в ней свою личность.
Для человека, который годами кормил прессу загадками, это выглядело вполне последовательно.
В дальнейшем я планировал приобрести более крупную официальную базу имён и фамилий. Она позволила бы расширить поиск и перейти от самостоятельно собранной выборки к более серьёзному массиву данных.
Для этого требовалась поддержка университета.
Выступление на конференции
Весной на научной конференции я подробно представил свою работу.
Рассказал об истории шифров Зодиака, принципах шифрования, расшифровке Z340 и особенностях Z13.
Объяснил, почему малое количество символов не упрощает задачу, а делает проверку результата почти невозможной.
Показал обе программы:
полный перебор;
систему анализа реальных имён и фамилий.
Продемонстрировал принцип их работы, рассказал о собранной базе данных, перечислил проверенные алгоритмы и обозначил дальнейшие направления исследования.
У меня не было готовой расшифровки.
У меня была сложная нерешённая задача, собственные программные инструменты, несколько тысяч собранных записей, результаты проверки гипотез и план развития проекта.
То есть исследовательская работа.
Слушателей проект заинтересовал. На фоне остальных выступлений тема выглядела необычно.
Мой научный руководитель – заведующий кафедрой и одновременно один из членов жюри – посмотрел на меня с некоторым сожалением.
Результаты конференции ещё не объявили, но мне уже начали объяснять, что я учусь только на первом курсе, что впереди будет много других проектов и что расстраиваться не следует.
Обычно человека утешают после объявления результатов.
Меня это несколько озадачило.
Научная объективность
Первые три места заняли проекты, связанные с разработкой типовых телеметрических приборов.
Темы этих проектов студентам рекомендовали преподаватели кафедры. Сами приборы были нужны кафедре.
Пока я самостоятельно искал способ решить нерешённую задачу, другим участникам уже выдали задание, указали направление и поставили маркер над конечной точкой. Оставалось только не свернуть по дороге исследовать ближайшую пещеру.
Проекты кафедры решали задачи кафедры, получали поддержку кафедры и затем оценивались представителями кафедры.
Наука иногда удивляет совпадениями.
Победившие работы опубликовали в университетском журнале. Кафедра получила необходимые ей разработки, студенты получили места, а система – ожидаемый результат.
Но не расшифровал же
Во время объявления результатов заведующий кафедрой снова отдельно упомянул мой проект.
И произнёс фразу, которую я запомнил навсегда:
Да, ты пытаешься расшифровать шифр. Но не расшифровал же.
Тогда я подумал:
Вот так да. Если бы я уже расшифровал имя Зодиака, вероятно, представлял бы результат в Гарварде.
Чтобы работа первого курса считалась достаточно успешной, мне следовало окончательно решить одну из самых известных криптографических загадок XX века.
Желательно за несколько месяцев, на домашнем компьютере и с базой данных, собранной вручную.
После этого можно было бы конкурировать с прибором, техническое задание для которого заранее подготовила кафедра.
Возможно.
Заведующий кафедрой снова сказал, что проект хороший, но я нахожусь только на первом курсе и у меня всё впереди.
Остальные участники, насколько я помню, тоже не успели состариться в стенах университета.
Просто у их проектов был более прямой маршрут к результату.
Так закончилась моя история про 18 карат невезения.
Что было дальше
Свою идею я не бросил.
Я лишь отложил её и позднее периодически возвращался к проекту по мере развития искусственного интеллекта и появления новых методов обработки данных.
Технологии постепенно давали возможности, которых у меня не было весной 2021 года.
Можно было расширять базы, использовать статистические модели, анализировать вероятности, искать закономерности и проверять значительно больше гипотез.
Но первая конференция дала мне отдельный результат, не связанный с криптографией.
Я понял, что научная среда не всегда продвигает неизвестное. Неизвестность неудобна: она не гарантирует готового устройства, публикации и результата к установленной дате.
Настоящая исследовательская задача может закончиться отрицательным результатом. Может потребовать годы. Может вообще не иметь однозначного решения.
Именно поэтому она является исследовательской задачей.
Но для победы на конференции значительно надёжнее разработать то, что уже ждут в соседнем кабинете.
С Зодиаком всё было проще.
Он хотя бы не притворялся, что играет честно.
---
К Z13 я ещё вернусь – уже с современными моделями, более крупными базами и методами, которых у меня не было в 2021 году.
Если вам интересны исследования в области программирования, искусственного интеллекта, или же просто безумные истории разработчика, который в силовой броне стремится в форбс (тяжело, шумно, но уверенно тащу ядер-колу на продажу), подписывайтесь. Здесь будут и другие мои проекты. В том числе расскажу про свою разработку видеоигр.
Какие методы вы бы проверили на тринадцати символах в первую очередь?
