Криптографические приключения. Таинственные шифры и математические задачи
Шрифт:
Прямо за завтраком я начал составлять ответное письмо. Тётя Катя надела очки и всмотрелась, но потом сказала, что ничего в этом не понимает. Потом добавила:
– Твой отец в детстве тоже всякие такие штуки делал. Ох и непрост был.
– Да он и сейчас непрост.
Мы с тётей Катей посмеялись, я доел кашу, выпил стакан молока и дописал ответ. Получилось неплохо:
Ближе к обеду я вручил письмо Кате. Когда она увидела его, то изменилась в лице, убежала в дом и долго не показывалась. Когда
– Вот я и предлагаю научить тебя всему тому, что умею я.
Она согласилась.
– Но перед тем, как мы начнём, покажи мне символы для оставшихся четырёх букв, которых не было в твоём письме, то есть Ф, Ц, Щ и Ъ.
Катя нарисовала:
Что ж, по крайней мере, все символы выполнены в одном стиле.
И мы начали первое занятие. Я рассказал, что сложность шифра одноалфавитной замены не зависит от сложности значков, а в качестве символов подстановки вообще могут быть числа. Мы обсудили два метода взлома этого шифра, то есть частотный анализ и подбор ключевых фраз. Я сразу показал на примере её письма, как работает второй метод, а потом мы углубились в изучение частотного анализа.
Мне хотелось самостоятельно (а не в наведённых воспоминаниях) составить таблицу частот букв для русского языка. Тем более что готовой у нас сейчас не было. Но, поразмыслив, мы решили найти таблицу в интернете. Хотя канал был очень слабым, нам удалось получить нужную информацию, и я выписал все частоты к себе в рабочий блокнот.
Катя поначалу всё равно была настроена скептически, потому что метод частотного анализа на двух наших записках сразу же показал очень неоднозначные результаты, и если бы не первые два слова, то ещё неизвестно, сколько бы времени я промучился. Но потом я убедил её, взяв текст побольше из какого-то журнала – в нем количества букв очень хорошо сошлись с частотами, полученными из интернета.
Мы скачали два рассказа, которые я порекомендовал ей прочитать. Конечно же, это были рассказы про золотого жука и про пляшущих человечков. Катя сказала, что никогда не слышала о них, хотя очень любит читать. Она обещала мне поскорее прочитать оба эти рассказа. На этом мы расстались, и я поехал к тётушке.
Тётя Катя разрешила мне ночевать в амбаре, который она с самого начала нам предлагала. После ужина я ушёл туда. В голове роились какие-то математические мысли, связанные с частотами букв и двоичной системой счисления. Мне казалось, что эти две вещи можно соединить друг с другом, но я не представлял себе как, и мне не хватало знаний. Я решил лечь спать: возможно, мозг во сне упорядочит информацию и найдет какую-нибудь идею. Поэтому я не стал играть на планшете, а просто лёг и расслабился, вдыхая ароматы сена и каких-то старинных вещей.
Из дневника Кирилла:
11 июня. Ночью мне приснился сон, в котором я не мог решить задачу и мучился. Задача состояла в том, чтобы уравновесить весы при помощи металлических шариков. Но все шарики имели различный вес: я не смог найти и двух одинаковых среди всей россыпи. И вот я подбирал шарики, но весы так и не уравновешивались. Я проснулся с чувством, что не доделал какое-то важное дело, про которое никак не мог вспомнить.
Из-за странного сна, который буквально опустошил меня, я не мог сосредоточиться всё утро. Папа рассказывал, что он часто решает сложные задачи при помощи этого метода: перед засыпанием
После завтрака приехала Катя, и я рассказал ей свой сон. Она задумалась, а потом спросила, почему я не смог решить эту задачу. Надо было на одну чашу весов класть самые тяжёлые шарики, а на другую самые лёгкие. Лёгких потребовалось бы намного больше, но в какой-нибудь момент всё бы сошлось. К этому времени в голове у меня чуть-чуть прояснилось, и я только посмеялся над её предложением. Вполне могло быть так, что остался бы последний шарик, который перевешивал то одну чашу весов, то другую (именно это меня и мучило во сне).
Катя задумалась, потом достала свой блокнот и начала его листать. Мой взгляд упал на систему кодирования символов для телеграфа. Я вгляделся в таблицу. В памяти начали всплывать образы наведённых воспоминаний – такую же таблицу мы рисовали с Марком, когда делали шифровальную машину. А потом я придумал, как при помощи пяти монет генерировать случайные пятибитные числа.
У меня произошло что-то вроде лёгкого головокружения, и головоломка внезапно сошлась. Деление пополам при помощи бросания монеты, дерево переходов, двоичные числа и биты, и, наконец, частоты символов – всё это соединилось в идее, которая засияла у меня в голове. Я даже зажмурился от нахлынувшего потока ощущений. Мне казалось, что мысли и идеи обрели форму и заворочались у меня в голове, царапая мозг.
Я взял блокнот и выписал в порядке уменьшения частоты встречаемости все символы русского алфавита, начиная с пробела. Затем я разделил полученный ряд на две части, чтобы в каждой из них сумма частот равнялась примерно 50 %. Точно разделить не получилось, получилось вот так:
После этого я нарисовал первый уровень дерева выбора. Левая ветвь обозначала те символы, которые лежат слева от разделительной черты, а правая, соответственно, правые. Левую ветвь я обозначил символом «0», а правую – символом «1».
Затем каждую половину символов я разделил ещё на две части так, чтобы сумма частот каждой равнялась примерно 25 %. Сделать это точно оказалось ещё сложнее, так что получилось так, как получилось:
Я продолжал делить множества символов снова и снова пополам, чтобы при каждом делении получались два новых множества примерно с одинаковой суммой частот. К моему удивлению, множества, расположенные левее, быстро закончились, то есть я дошёл до отдельных символов. А вот множества с правой стороны делились несколько дольше. Соответственно, дерево выбора получилось не равномерным и симметричным, а скособоченным на правую сторону.
После этого пришло время собрать коды для каждого символа. Получилась вот такая таблица:
Очевидно, что чем чаще встречается символ в русском языке, тем короче в этой таблице его двоичное представление. Мы с Катей смотрели на результаты моих упражнений и не могли понять, что это такое и для чего может пригодиться. Но я чувствовал, что открыл что-то очень важное, полезное и интересное. Похоже, надо дождаться отца, чтобы показать ему и узнать, где это можно применять.