Шифры и квесты

Прошло часа полтора, когда папа Марка перезвонил. Марк поднял трубку и начал слушать. Я сам особо не слышал их разговора, а Марк только кивал и говорил «Угу». Когда они закончили говорить, он повернулся ко мне и торжественно заявил, что всё понял и сейчас расскажет мне о шифре многоалфавитной замены.

Марк объяснил, что для применения шифра многоалфавитной замены требуется ключ или пароль. Это должно быть слово, определяющее выбор алфавитов, символами которых заменяются буквы в шифруемом тексте. Сам ключ применяется циклически. То есть, например, если в этом ключе четыре буквы, то первая, пятая, девятая и далее каждая четвёртая буква текста будут зашифрованы при помощи одного алфавита, который определяется первой буквой ключа. Соответственно, вторая, шестая, десятая и так далее буквы текста шифруются при помощи второго алфавита, который определяется второй буквой ключа. И так далее.

Получается, что именно из-за использования разных алфавитов нарушаются частоты символов в шифровке. Я задумался. Потом достал таблицу, найденную в чемодане, и стал внимательно её рассматривать. Тут мне в голову, как обычно это происходит, молнией ударила идея. Я воскликнул:

– Смотри! Видишь, строки и столбцы таблицы помечены символами: от пробела до буквы «Я». А что, если строки обозначают символы ключа, а столбцы – шифруемого текста? Тогда на пересечении строки и столбца у нас получается та буква, которую надо записать в шифровке.

Марк ответил:

– А если наоборот. Столбец обозначает символ ключа, а строка – символ шифруемого текста?

– И что ж? Таблица-то у нас симметричная! Это совершенно неважно.

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

– Таким образом, у нас получается две задачи. Сначала нам надо разгадать, какой ключ был использован. Как только мы это сделаем, вторая задача, то есть расшифровка, будет решена при помощи этой таблицы. Но как узнать, какой ключ был использован?

Марк оторопело смотрел на меня, потом отрицательно покачал головой. Я продолжил:

– Надо попробовать вычислить длину ключа. Как только мы будем знать длину ключа, мы сможем применить подсчёт частот букв, чтобы разгадать всё. Я уже один раз применил этот метод, когда расшифровывал первую найденную шифровку. Это долго и не так просто, но это работает.

– А как вычислить длину ключа?

– Можно просто перебирать от двух и далее. Поскольку мы видели, что частоты символов отличаются от той картинки, которая нарисована для русского языка, здесь ключ длиной определённо больше единицы. То есть можно предположить, что ключ представляет собой пару символов, и тогда попытаться подобрать ключ этой длины. Если не получится, то перейти к ключу длиной в три символа, и так далее.

– Ну а как подобрать ключ такой-то длины?

– Всё просто. Посмотри на таблицу. Видишь, в ней используется пробел. Это ужасная оплошность со стороны моего отца. Я вообще поражён, что он использовал именно такую таблицу. Почему? Да потому что пробел встречается в текстах в полтора раза чаще, чем наиболее часто встречаемая буква «О». То есть мы берём самый часто встречаемый символ и предполагаем, что это пробел. Потом смотрим в таблице и получаем первую букву ключа. Вернее, даже смотреть никуда не надо, поскольку пробел кодирует буквы сами в себя, поэтому самый часто встречаемый символ и будет буквой ключа. Понял?

Марк утвердительно кивнул. Я попросил объяснить его своими словами, и он сказал:

– Предположим, что ключ состоит из двух символов. Тогда мы выписываем все буквы на нечётных местах и считаем их количества. Самый часто встречающийся символ является первой буквой ключа. Потом также считаем все буквы на чётных позициях. Опять самый часто встречающийся символ является второй буквой ключа. Так?

– Да. А что дальше?

– Думаю, что если получилось какое-то слово, то ключ угадан верно. Если нет, то переходим к следующей длине ключа.

– Отлично! Но тут есть ошибка. Ключом необязательно должно быть какое-то осмысленное слово. Я так думаю, что это может быть произвольная последовательность букв. Но твой ход мыслей мне нравится. Проще сначала проверить так.

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

Я сказал:

– Предлагаю устроить соревнование. Сфотографируй таблицу, чтобы она у тебя тоже была. И каждый из нас применит этот метод, а завтра сравним результаты. Идёт?

Марк опять кивнул. На этом мы и расстались.