Решение задач Международной математической олимпиады доверят ИИ

Борьба Марии Стюарт, королевы Шотландии и Франции, за английский престол закончилась для нее на эшафоте 8 февраля 1587 года. На гибель Марию Стюарт обрекли несколько писем, которые были зашифрованы слишком простым кодом. Только что архив переписки Марии пополнился: участники проекта DECRYPT обнаружили во Франции больше пятидесяти писем королевы и расшифровали их. Шестнадцатый век, эпоха становления абсолютной монархии и новой европейской политики, наполненный придворными интригами, неофициальной дипломатией и шпионажем, стал также и временем бурного развития искусства криптографии. Переписка монархов, послов, их агентов, попав не в те руки, могла привести к войне или революции — поэтому содержание писем начинают скрывать от лишних глаз с помощью шифров. Самым распространенным — и простым — методом тогда был моноалфавитный симметричный замещающий шифр, где каждой букве соответствует один символ, а для шифровки и расшифровки используется один и тот же ключ в виде таблицы соответствия букв и символов. Взламывать его научились еще арабские математики в X веке: для этого нужно подсчитать частоту встречаемости символов и затем сопоставить ее частотой букв в других текстах на предполагаемом языке послания. В русском языке, например, самая частая буква — «о», на нее приходится 10,98 процента знаков в любом тексте. Если в зашифрованном тексте какой-то символ встречается с такой частотой, то он наверняка замещает именно «о». В частности, именно так американцы Бетти и Дональд Гардены в 1969 году прочли зашифрованные письма серийного убийцы Зодиака, которые публиковали газеты. Но для XVI века такой шифр был уже слишком простым. Появились более изощренные методы, например, омофонический шифр, в котором одну и ту же букву могли обозначать разные символы, или использование номенклатур, то есть таблиц специальных символов для некоторых слов, имен, топонимов и месяцев. Появились шифры с нулевыми знаками, которые игнорировались при расшифровке, а также знаки, которые отменяли предыдущий или, напротив, повторяли его. Ключи шифрования могли меняться по ходу текста. Да и сам текст мог быть на экзотическом языке, чтобы затруднить его идентификацию при помощи частотного анализа. Комбинирование этих приемов делало взлом шифра крайне сложной задачей. Многие документы того периода так и остались не расшифрованными ни современниками, ни последующими исследователями — и только появление методов компьютерного анализа позволило, наконец, их прочесть. Неопознанный архив Слишком простой шифр сыграл фатальную роль в судьбе Марии Стюарт. Главной уликой в суде, который приговорил ее к смерти, стало письмо Марии лидеру заговорщиков Энтони Бабингтону. Документ перехватили агенты секретаря Елизаветы I Фрэнсиса Уолсингема и прочли — он был зашифрован примитивным моноалфавитным шифром с очень небольшой номенклатурой. Неосторожность Марии, вероятно, была вынужденной. Ее молодой корреспондент — Бабингтону не было и 25 лет — скорее всего, просто не владел более сложными способами шифрования. Вообще среди писем Марии Стюарт встречаются примеры использования значительно более сложных шифров. Всего в Английском национальном архиве хранится больше сотни зашифрованных писем шотландской королевы. Многие из них связаны с заговорами по свержению Елизаветы I и коронованию Марии как королевы Англии. Теперь эпистолярный архив Марии Стюарт сильно пополнился — сразу на 57 новых документов — благодаря усилиям трех членов группы DECRYPT: компьютерщику Джорджу Ласри (George Lasry), историку Норберту Бирманну (Norbert Biermann) и физику Сатоши Томокийо (Satoshi Tomokiyo). Изучая оцифрованный архив Национальной библиотеки Франции в поисках зашифрованных рукописей, они обнаружили документы, которые были атрибутированы как итальянские письма первой половины XVI века. Изучив эти документы, исследователи поняли, что они не имеют никакого отношения к Италии, а первая попытка расшифровки — когда язык послания еще не был определен — дала им имя, которое все расставило по местам. Это было имя Фрэнсиса Уолсингема, который занимался для Елизаветы в первую очередь вопросами различной секретности, и, в конечном счете, успехи которого погубили Марию Стюарт. Но эти письма были зашифрованы гораздо более сложным кодом, чем попавшие в руки Уолсингема письма Баббингтону: в нем было много омофонических знаков и сложная номенклатура. Поскольку исчерпывающий поиск, при котором перебираются все возможные варианты расшифровки, занимает слишком много времени и вычислительных ресурсов, группа применяла метод поиска восхождением к вершине (hill climbing) — один из способов решения оптимизационных задач (например, разных типов задачи коммивояжера). Этот алгоритм начинает работу с того, что генерирует произвольное решение, а затем пошагово его улучшает, меняя параметры. Перед началом расшифровки исследователи составили таблицы вероятности для пятибуквенных сочетаний, таких как -ision, -ement, -etles, -ourle. После этого была рассчитана вероятность сочетания этих комбинаций с наиболее часто встречающимися буквами в письмах. Затем был сгенерирован случайный ключ, призванный выявить омофоны, чтобы разметить их в тексте. После незначительной модификации ключа алгоритм заново размечал текст, и, в случае улучшения результата, принимался новый ключ, в противном случае он отвергался. Алгоритм применялся до тех пор, пока не выявлялся оптимальный пик для всего текста. Этот метод позволил выявить омофоны, в то время как знаки номенклатуры — знаки, обозначающие сразу целые слова, — подбирались вручную. Письма были написаны на французском, но шифр отличался от принятого во французской дипломатии того периода и был сложнее. В частности, в шифрах французских послов в Венеции, Риме, Испании не использовались диакритические знаки, которые есть в письмах Марии Стюарт. Ласри и его коллеги пока не нашли ответа, был ли этот шифр разработан самой королевой или кем-то из ее окружения — или был усложненным вариантом французского дипломатического шифра. Исследователи проверили корректность расшифровки путем сравнения найденных писем с уже известными документами из коллекции бумаг Уолсингема в британских архивах. Ласри и его коллеги полагают, что, возможно, в дальнейшем удастся обнаружить и другие документы, связанные с судьбой Марии Стюарт, которые зашифрованы так же. Что в письмах Из 57 найденных писем Марии Стюарт 54 адресованы французскому послу при английском дворе Мишелю де Кастельно, два — посланнику французского короля Генриха III, Бертрану де Салиньяку де ла Моте-Фенлону. Еще одно письмо написано секретарем Марии Жаком Но и адресовано Жану Арно, секретарю де Кастельно. Хотя историки знали о секретной переписке Марии Стюарт с Мишелем де Кастельно, письма считались утраченными. Нынешняя находка показывает, что переписка с де Кастельно началась не позже мая 1578 года и продолжалась как минимум до середины 1584 года — весь этот период Мария находилась в Англии под стражей, но могла общаться с внешним миром с помощью писем, которые она передавала через доверенных лиц. Французский король тогда казался наиболее реальным союзником пленной шотландской королевы, а его посол Мишель де Кастельно — наиболее очевидным контрагентом по переписке. Расшифровка писем позволила датировать их и установить, что в основном они относятся к периоду 1580-1583 годов — особенно к июлю 1583-го — то есть связаны с заговором Трокмортона. Это позволило узнать новые детали заговора и уточнить степень вовлеченности в него французского двора. Кроме того, в это же время происходило еще одно событие, которое могло значительно повлиять на судьбу Марии — растянувшееся на три года сватовство брата французского короля, герцога Анжу и Алансона, к Елизавете. Показательно, что Мария активно защищает в письмах идею этого брака и даже предлагает свое посредничество при переговорах. Одновременно она предостерегает Кастельно, что англичане не ведут переговоры честно и их целью является не брак, а стремление столкнуть интересы Франции и Испании в Нидерландах, где Анжу был провозглашен «Протектором свободы». Одновременно Мария предлагает свое посредничество между Анжу и испанским королем Филиппом II с целью предотвратить возможный конфликт. В нескольких письмах Мария высказывает крайне неприязненное отношение к графу Лестеру, фавориту Елизаветы, которого она обвиняет в самых разнообразных заговорах, в том числе и против английской королевы. В частности Мария пишет о проекте брака между Лестером и Арабеллой Стюарт, правнучкой Маргариты Тюдор, то есть потенциальной претенденткой на английский престол. Можно предположить, что подразумевалась возможность организованной «утечки информации» с целью внесения раскола в окружение Елизаветы, тем более, что в этих письмах регулярно упоминается следивший за Марией секретарь Елизаветы Фрэнсис Уолсингем. В нескольких письмах, относящихся к концу 1582-го, Мария просит де Кастельно повлиять на французский двор, чтобы тот поддержал сына Марии, Якова VI (в будущем ставшим монархом Англии и Шотландии), когда его в августе 1582 года захватил Уильям Ратвен, а ко власти в Шотландии пришли радикальные протестанты. Также Мария сообщает в письмах о визитах представителей Елизаветы, которые вели переговоры о возможных условиях ее освобождения и даже восстановления на шотландском троне (совместно с сыном). Одновременно она пишет о беспредметности этих переговоров, в которых представители английской королевы не имеют полномочий предлагать что-либо конкретное. Кроме того, Мария призывает де Кастельно активизировать шпионскую активность и переманивать на свою сторону придворных Елизаветы, а также в большем объеме награждать агентов, одновременно предостерегая, что среди потенциальных сочувствующих могут быть (как, впрочем, и получилось) агенты Уолсингема. Подводя итог, можно сказать, что расшифровка недавно обнаруженных в Национальной библиотеке Франции, а также семи уже известных, но не расшифрованных писем Марии к Кастельно, которые находились в британских архивах, показывает: алгоритмический взлом омофонических шифров может пролить еще немало света на тайную дипломатию раннего Нового времени.