Решаем криптографическую задачу: Из России с любовью

Ранее в блоге FirstVDS уже была статья с разбором решения криптографической задачи с MysteryTwister. В этом топике разберём задачу с довольно многозначительным названием «Из России с любовью» ("From Russia with Love"). Автор задачи Sansibar.

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

Задача

Сара и Игорь — студенты по обмену. Сара живет в Москве, а Игорь в Берлине. Сара учит русский язык и, чтобы сохранить свои маленькие секреты в тайне, они шифруют свои электронные письма. Ключом они обменялись лично, и он состоит из 26 букв латинского алфавита.

Пример:

Сара шифрует следующий открытый текст:

HEUTE REGNETE ES DEN GANZEN TAG

Ключевое слово DNJEPR используется для определения первых 6 букв шифралфавита:

DNJEPRABCFGHIKLMOQSTUVWXYZ — сформированный шифралфавит.

Своё сообщение Сара шифрует полученным шифралфавитом с помощью простой замены.

BPUTP QPAKPTP PS EPK ADKZPK TDA — зашифрованное сообщение.

Далее Сара меняет латиницу на кириллицу в соответствии со следующим правилом замены:

и отправляет текст Игорю:

БПУТП ЯПАКПТП ПС ЕПК АДКЗПК ТДА — итоговое зашифрованное и преобразованное сообщение.

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

После очередной замены ключа Игорь получает новое зашифрованное электронное письмо от Сары:

ЦМГГЙ  ДБЙП  ЩПЯРЩИ  РЩЯР  ОЩЯРМИКЩИ  ВМП  ИДСЦР  БМИЗ  ЩДИАМСЦ  ЗТ  ГЙЩЯЩИ  АПЩТЩ  ХДСЦ  КДСЦ  ЗТ  ЯДГУЩЯРЩП  ЦДЩП  ДИ  ХЙЯФМТ  ЗТ  РПЩААЩИ  ДИ  ГДЩОЩ  КЩДИЩ  ЯМПМЦ

В оригинальной задаче необходимо было расшифровать лишь одно определённое слово из текста, что вполне реально сделать и без дешифровки всего текста и поиска ключа. Я усложнил себе задание и решил задачу полностью. Расшифровал весь текст и вычислил ключевое слово. Причём, что интересно, ключ вычислил уже в конце расшифровки. Кому-то это может показаться странным, однако проблема заключалась не в сложности самой задачи, а в том, что при её решении я столкнулся со своим небольшим недостатком. Мой немецкий язык находится на презрительно-отвратительном уровне, заключающемся в знании числительных и совсем уж мутных воспоминаниях о неком репортёре Шрайбикусе.

Решение

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

Первым делом проведём обратную замену кириллицы на латиницу, согласно приведённому в задаче правилу. Получаем следующий текст:

CMGGJ  DBJP  WPQRWI  RWQR  OWQRMIKWI  VMP  IDSCR  BMIZ  WDIAMSC  ZT  GJWQWI  APWTW  HDSC  KDSC  ZT  QDGUWQRWP  CDWP  DI  HJQFMT  ZT  RPWAAWI  DI  GDWOW  KWDIW  QMPMC

Далее я сформировал несколько гипотез.

Используя факт, что последние буквы алфавита имеют низкие коэффициенты частотности, и зная правило формирования шифралфавита, я предположил неизменность их положения относительно обычного алфавита (я оставил на своём месте XYZ).

Отсутствие блочной записи привело к выводам, что короткие слова — это предлоги либо частицы, хотя могут быть и наречиями. Тем не менее в полученном тексте три одинаковых коротких слова ZT и два DI, скорее всего, за ними скрываются предлоги. Используя список, сформированный из субтитров фильмов и телесериалов общим объемом около 25 миллионов слов, я предположил, что ZT — это ZU (по частоте употребления на 12 месте).

Далее я вспомнил один из любимых мной рассказов Артура Конана Дойля «Пляшущие человечки». В рассказе Шерлок Холмс разгадывает загадку шифра замены, состоящего из изображений пляшущих человечков.

Тут меня осенила счастливая мысль. Письма обычно начинаются с имени того, кому письмо адресовано. Человек, писавший миссис Кьюбит эти послания, был, безусловно, близко с ней знаком. Вполне естественно, что он называет её просто по имени. А имя её состоит из четырех букв и кончается той же буквой, какой начинается: зовут её Илси. Таким образом, я оказался обладателем трёх букв: И, Л и С.

В отличие от письма у Холмса, первое слово письма Сары на одну букву больше имени адресата, но содержит две одинаковые буквы подряд, поэтому я предположил, что это приветствие на немецком языке — HALLO. Следовательно, следующее слово как раз и будет именем адресата — IGOR.

Обладая знанием, что D — это I, предположим, что предлог DI — это IN (на 16 месте), получаем ещё одну букву. В итоге у нас есть ряд букв.

Теперь перейдём к частотному анализу. В таблице указаны значения количества букв в тексте сообщения, частотность в тексте и частотность букв немецкого языка, основанная на текстовой выборке из немецкого справочного корпуса. С одной стороны, выборка из 117 букв (шифрованное сообщение) слишком мала, с другой, из полученной таблицы всё равно можно почерпнуть некоторую информацию.

Обратите внимание на явные перекосы, которые я отметил цветом. Особенно на букву E (в зашифрованном сообщении отсутствует) и W (неоправданно большое количество) и их процентное взаимоотношение (~16%). E — вообще самая распространённая буква в немецком языке, а в зашифрованном тексте она отсутствует. Поэтому я делаю вывод, что это она и есть.

Далее меня заинтересовала Q, за ней явно скрывается более употребляемая согласная. Пока непонятно какая. Теперь обратимся к технической стороне вопроса. Для этого немного переформатируем таблицу.

Надеюсь, вы помните, что шифралфавит составляется путём смещения и исключения букв, из которых состоит ключевое слово? Тогда дальше заполняем пробелы между D и G, G и I, T и X оставшимися буквами.

Вернёмся к тексту сообщения. Посмотрим, что получилось.

Обратите внимание на некоторые слова:

Первое – 100% MOSKAU, а второе – SARAH (т. к. Сара живёт в Москве, а в конце сообщений иногда принято добавлять что-то типа «с любовью Сара»), получим, что Q = S.

Теперь взглянем на слова:

Учитывая моё отвратительное знание немецкого языка, прибегнем к помощи поисковика и словаря. Liebe — любовь; привязанность. Deine — твой (твоя, твоё, твои), таким образом, предполагаем фразу: IN LIEBE DEINE SARAH. Следовательно, у нас есть ещё две буквы O = B, K = D.

Далее заполняем текст полученными буквами.

Заполняем пробелы таблицы. Остаётся три буквы R, S, A.

Учитывая, что наши герои — студенты, легко предположить в словах:

ERSTEN TEST (первый тест), таким образом, у нас есть буква R = T. С помощью оставшихся двух букв простой перестановкой получаем ключевое слово MOSKWA, а следом и весь шифралфавит.

Итоговое решение задачи:

Может показаться, что шифры замены отжили своё, однако это далеко не так. Эти шифры, несмотря на весь их примитивизм, при соблюдении условий скрытности и случайности шифралфавита и шифрзаписи потенциально невзламываемые. Ещё в прошлом веке Клод Шеннон математически доказал абсолютную криптографическую стойкость одного из шифров замены (шифр Вернама). Подобные шифры до сих пор используются для передачи особо важных сведений.

P.S.

Как бы я усложнил задачу? Во-первых, использовал бы блочный метод шифрзаписи, а во-вторых, усложнил бы правила замены латиницы на кириллицу. Спасибо всем за внимание. Интересных задач и элегантных решений.

На всем земном шаре нет ни одного человека, кроме членов нашей шайки, который знал бы тайну пляшущих человечков. Как могли вы написать её?

– То, что изобретено одним человеком, может быть понято другим, – ответил Холмс.

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