Криптографические приключения. Таинственные шифры и математические задачи

С собой папа привёз кучу разных вещей. Во-первых, всё заднее сиденье было уставлено бутылями с водой. Действительно, привезённая из города вода у нас уже почти закончилась. Хотя у тёти Кати я пил колодезную воду, но папа не советовал мне этого делать. Не знаю уж почему, ведь он в детстве пил ту же самую воду. Несколько часов мы выгружали эти бутыли в подсобку нашего штаба.

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

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

На следующий день я показал папе свои выкладки о разделении множества символов на две половины в соответствии с их частотностью. Отец внимательно изучил всё, что я ему показал, а потом спросил, где я это вычитал. Я горячо возразил, что всё придумал сам (ну, может быть, Катя немного помогла). А вообще идея пришла ко мне во сне.

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

– Ты лучше скажи, для чего это нужно. Ведь мы с Катей не смогли придумать, как использовать новый код.

– Это потому, что у вас не было под рукой телеграфа. Если бы попробовали отправлять сообщения при помощи этого нового кода, то сразу поняли бы.

– И все-таки расскажи, пожалуйста.

– Всё просто. В том коде, который я вам дал, каждая буква представлена пятью битами. А в твоём коде длина представления буквы зависит от её частоты: чем чаще, тем короче. Теперь понимаешь?

– То есть для длинных передач моим кодом надо будет меньше раз жать на ключ, чем для передач твоим?

– Абсолютно верно. Давай попробуем. У Кати есть копия этого кода?

– Должна быть, она перерисовала его себе.

– Тогда включай телеграф и вызывай её.

Прежде всего я закодировал при помощи нового кода сообщение: «КАТЯ ПРИЕЗЖАЙ ПАПА РАССКАЖЕТ НОВУЮ ТЕМУ». Получилось довольно длинно и необычно. Я включил телеграф и передал сигнал начала сессии. Пять минут не было никакого ответа, и тогда я снова передал этот сигнал. На этот раз ответ пришёл через две минут. Что ж, алгоритм установки сессии работал.

Я передал подготовленный шифр и стал ждать. В ответ пришло сообщение: «01101 01000 10111 00101 00011 01110 01101 00101 01111 01110 01101 01000 01100 00000 11110», что соответствовало тексту «НИЧЕГО НЕ ПОНИМАЮ». Тогда я передал обычным кодом: «ИСПОЛЬЗУЙ НОВЫЙ КОД». Через какое-то время пришло сообщение: «0100 11001 11010 11111100 11001 0110 1000 0100», что при декодировании новым кодом значило «ЕДУ ЖДИТЕ».

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

Папа рассказывал:

– Люди с древнейших времён передают информацию как в пространстве, так и во времени. Например, полководец отправляет гонца с посланием своим офицерам. Это – передача информации в пространстве, от источника информации к её потребителям. А если учёный пишет научный трактат для потомков, то это передача информации во времени. Конечно, можно передавать информацию только в будущее время. И такую передачу называют «хранением информации».

Папа расхаживал из стороны в сторону:

– Только в середине прошлого века были разработаны научные основы передачи информации. Основоположником теории информации стал Клод Шеннон, который опубликовал несколько фундаментальных статей по криптографии и кодированию.

Затем он взял мой блокнот и раскрыл его на той странице, где был записан придуманный мною код. Отец продолжил свой рассказ:

– То, что вы придумали, впервые было разработано Клодом Шенноном. Другой учёный, Роберт Фано, создал то же самое независимо от Шеннона, поэтому код носит двойное имя: Шеннона – Фано. Этот код – сжимающий и, как вы сами поняли, он основан на частотности символов: чем чаще встречается символ, тем короче его код. Но он также префиксный, то есть ни один код символа не является началом другого, и это свойство удобно использовать при декодировании. Можно посылать поток символов без разделения, а отделять для декодирования надо начальные биты последовательности, и это произойдёт однозначно. Давайте попробуем сделать это с какой-нибудь фразой.