Криптографические приключения: таинственные шифры - Страница 26

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

Мы с Катей недоумённо переглянулись. Оказывается, мы занимались всякой всячиной! Надо же. Но отец продолжал:

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

Папа вынес на улицу свой ноутбук, повернул его к нам и продолжил:

— Мы можем написать программу, которая займётся перебором. Но если бы мы попытались перебрать все варианты распределения по буквам чисел, которые есть в нашей шифровке, то нам бы не хватило на это оставшегося лета. Боюсь, что и жизней наших не хватило бы. Однако если подумать, то можно серьёзно оптимизировать поиск. Для этого можно воспользоваться техникой, которая называется «генетический алгоритм».

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

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

— Но я сказал «генетический алгоритм», а не «генетика». Слушайте дальше.

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

Отец объяснил, что для запуска генетического алгоритма на компьютере придется разработать несколько вещей. Во-первых, необходимо представить элементы, среди которых мы будем искать, в виде последовательности «генов», то есть единиц информации, которые можно комбинировать друг с другом. Во-вторых, определить над представленными таким образом элементами операции скрещивания и мутации для того, чтобы генерировать новые поколения. В-третьих, надо определить функцию отбора, которая будет работать так же, как естественный отбор в живом мире.

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

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

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

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

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

Мы с Катей одновременно покачали головами. Это действительно было трудно. Отец вздохнул и попытался в третий раз:

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

Теперь мы кивнули. Это как раз было просто. Отец продолжил:

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

— А почему бы просто не смотреть на то, что получается в процессе подбора, и не искать глазами правильный текст?

Отец вздохнул и ответил:

— Но я же сказал, что это заняло бы у нас много-много веков, даже если бы мы сумели просматривать по одному варианту в секунду без перерыва на сон и обед. А компьютер сможет оценивать миллионы вариантов в секунду без нашего вмешательства. Итак, теперь есть идеи, что представляет собой ген в нашем случае?

Катя подняла руку, и отец кивнул ей. Она заявила:

— Я думаю, что ген в нашем случае — сопоставление чисел и букв.

Отец похвалил её, но сказал, что это не совсем так. Геном является одно сопоставление между числом из шифровки и буквой. А то, что назвала Катя, то есть весь набор таких сопоставлений, — это одна особь, которую можно подвергнуть отбору. Критерием будет близость частот к эталонному варианту.

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