Тайны чисел: Математическая одиссея

Походит на галиматью, но на самом деле это послание, написанное с использованием одного из самых популярных способов кодирования. Он называется шифром подстановки и состоит в замене каждой буквы алфавита какой-либо другой буквой: так, a может стать P, t может стать C и т. д. (Я использовал строчные буквы для незашифрованного сообщения – оно называется в криптографии открытым текстом – и прописные буквы для зашифрованного текста, или шифротекста.) Если отправитель и получатель сообщения заранее договорились об используемом шифре подстановки, то получатель сможет дешифровать послания, но всем остальным они будут казаться бессмысленными строками абракадабры.

Самая простая версия этих шифров называется сдвигом Цезаря – в честь Юлия Цезаря, который пользовался им для связи со своими военачальниками во время Галльских войн. Принцип его действия состоит в сдвиге каждой буквы на одинаковое число позиций в алфавите. Например, при сдвиге на 3 a становится D, b становится E и т. д. Вы можете загрузить с веб-сайта «Тайн 4исел» соответствующий файл и вырезать шифровальное колесо для создания этих простых сдвигов Цезаря.

Сдвижка на постоянное число позиций дает вам лишь 25 возможных шифров, так что, если вы понимаете, что сообщение было закодировано с помощью одного из них, становится совсем просто расшифровать его. Существует и лучший способ закодировать сообщение: вместо простого постоянного сдвига всех букв можно перемешать их и разрешить замену любой буквы произвольной другой буквой. Эта методика шифрования сообщений была предложена за несколько веков до Юлия Цезаря, удивительно, что она изложена не в военном руководстве, а в Камасутре. Хотя этот древний трактат на санскрите обычно ассоциируется с описанием плотских удовольствий, в нем описывается и несколько других искусств, которыми должна овладеть женщина: от заклинаний и игры в шахматы до переплетного дела и плотничества. А 45-я глава посвящена искусству тайных сообщений, и объясняется, насколько совершенен может быть шифр подстановки для сокрытия подробностей любовных связей.

В то время как имеется лишь 25 сдвигов Цезаря, число возможных шифров становится заметно больше, когда мы позволяем заменять любую букву любой другой. У нас есть 26 возможностей для того, что будет использовано вместо a, для каждой из этих возможностей имеется выбор из 25 букв для буквы b (одна буква уже была использована для кодирования a). Итак, имеется 26 × 25 различных способов зашифровать буквы a и b. Если мы продолжим выбирать другие буквы для оставшегося алфавита, то найдем, что имеется

26 × 25 × 24 × 23 × 22 × 21 × 20 × 19 × 18 × 17 × 16 × 15 × 14 × 13 × 12 × 11 × 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1

различных шифров Камасутры. Как мы видели на с. 40, это число обозначается 26!. Только нужно не забыть вычесть 1 из этого числа, потому что имеется вариант, когда А соответствует а, B соответствует b и так далее вплоть до Z, соответствующего z, что не является шифром. Когда мы вычислим 26! и вычтем 1, то придем к общему числу

403 291 461 126 605 635 583 999 999

различных шифров – более четырехсот миллионов миллиардов миллиардов возможностей.

Отрывок в начале данного раздела был закодирован с помощью одного из этих шифров. Чтобы дать вам представление о числе возможных перестановок, замечу, что напиши я закодированный отрывок с использованием всех различных шифров, то лист бумаги вышел бы за пределы Млечного Пути, нашей Галактики. Компьютер, проверяющий по одному шифру в секунду с момента Большого взрыва, который произошел 13 миллиардов лет назад, к настоящему времени выполнил бы лишь часть работы по проверке всех шифров – и при этом очень малую часть.

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

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