Роман Душкин - Криптографические приключения: таинственные шифры и математические задачи

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

— Знаешь, а это интересная идея. Я сам до неё не додумался. А подсчитай-ка площадь коробочки и общую площадь всех элементов?

Действительно! Перед тем, как пробовать уложить элементы в коробочку, надо было бы сделать эту простую проверку. Я подсчитал обе площади, и они совпали. Это еще больше убедило меня, что я нахожусь на правильном пути. Но у меня все равно не получалось сложить головоломку. Минут через пятнадцать я хотел уже бросить это дело и уехать к Кате, но тут отец сказал:

— Давай-ка всё это сюда. Пошли к компьютеру, я как раз написал программу, которая ищет варианты плотной упаковки элементов в коробку.

Я удивился: неужели за эти пятнадцать минут папа успел осмыслить задачу и написать программу? Но спорить я не стал, собрал вырезанные элементы и вошёл внутрь штаба.

Папа сидел за компьютером и что-то усердно печатал. Когда я подошёл, он забрал у меня мою модель и сказал, что надо доработать программу, чтобы она смогла работать именно с нашей задачей. Он стал быстро вводить последовательности нулей и единиц, и я увидел, что ряды единиц повторяют форму элементов, а нули заполняют пространство, чтобы на экране элементы выглядели прямоугольными. Через несколько минут папа завершил ввод и нажал какую-то комбинацию клавиш. На экране появилось окошко командной строки, а в самом низу мигал курсор. Папа ввёл какое-то слово и нажал Enter.

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

— Есть! Давай сюда свою модель.

Я протянул ему вырезанные детали, и он начал заполнять элементами изображение коробочки. Он брал элемент, смотрел на числа на экране и ставил его. Скоро все элементы были расположены так, что все они уместились в коробочку, ни один не накладывался на другой, и в коробочке не осталось незакрытых мест. Я удивлённо хмыкнул:

— И как у тебя это получилось?

— Я написал программу, она сделала поиск плотной упаковки и выдала результат.

Это немного расходилось с моими представлениями о программировании и программах. Для меня программа — это мобильное приложение в смартфоне или на планшете, а сейчас папа уверяет, что в этом чёрном окошке с зелёными буквами он увидел какой-то результат. Но там были только числа. Я понял бы, если бы программа нарисовала эти элементы головоломки и показала, как их складывать. Но папа продолжил:

— Пусть тебя не смущает такой вид программы. Во-первых, это всего лишь прототип . Во-вторых, я написал его «на коленке», как говорят программисты. В-третьих, это программа для решения всего одной конкретной задачи. Именно поэтому всё произошло так быстро, а результаты представляются в виде невразумительного набора чисел. Смотри: каждая пара чисел представляет собой координату левого верхнего угла элемента в коробочке, начиная от левого верхнего её угла, который имеет координаты 0 и 0. Элементы идут в том порядке, в каком я вносил их в программу. Всё просто.

Я не стал спорить. В этот момент подъехала Катя. Она посмотрела на результаты нашей работы и надулась, что мы не подождали её. Папа похлопал её по плечу и утешил: ничего особенного она не пропустила, зато сейчас можно начать решать загадку.

Мы сели на скамейку, и я положил собранную головоломку перед нами. По элементам бежали строки чисел, и мы с Катей переписали их в свои рабочие блокноты. Уже тут я понял, что с этим набором чисел что-то не то. Он был слишком непохож на шифр одноалфавитной замены. Может быть, это многоалфавитная замена?

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

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

— Как я понял, Кирилл рассказал тебе, Екатерина, что простой шифр одноалфавитной замены можно очень легко взломать. Почему это можно сделать?

Катя ответила:

— Потому что количество разных букв в текстах разное.

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

Мы с Катей согласно кивнули. Ну, мне-то это было давно известно, а Катя, надеюсь, поняла мои объяснения. Отец продолжил:

— А теперь давайте сделаем такой финт. Возьмём, скажем, сто чисел от 00 до 99, то есть все двузначные числа. Для каждого символа русского языка, то есть всех букв и пробела, как мы договорились, назначим случайным образом такое количество символов, которое примерно соответствует частоте символа. Например, пробел имеет частоту 14,55 %, так что пятнадцать случайно выбранных чисел из множества от 00 до 99 будут обозначать пробел. Буква «О» имеет частоту 9,96 %, поэтому этой букве будет соответствовать десять случайно выбранных чисел, которые не совпадают с числами для пробела. Екатерина, если буква «Е» встречается в языке с частотой 6,62 %, то сколько случайно выбранных чисел ей будет соответствовать?