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

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

Простой арифметический прием подсчета букв означает, что любое сообщение, закодированное с помощью шифра подстановки, нельзя сделать секретным. Мария I, королева Шотландии, узнала это на собственном опыте. Она обменивалась посланиями, содержащими планы по убийству королевы Елизаветы I, с другим заговорщиком, Энтони Бабингтоном, при этом буквы в них заменялись странными символами (рис. 4.01).

Рис. 4.01. Шифр Бабингтона

На первый взгляд сообщения, посланные Марией, казались непроницаемыми, но при дворе Елизаветы был один из главных европейских знатоков по взламыванию шифров – Томас Фелиппес. Он не был привлекательным человеком, что ясно из следующего описания: «Малорослый, во всем худосочный, подслеповатый, с темно-золотистыми волосами на голове и светло-золотистой бородой, с оспинами на лице». Многие люди считали, что Фелиппес наверняка был в сговоре с дьяволом, раз обладал способностью понимать такие иероглифы, но он использовал тот же прием частотного анализа. Он взломал код, Мария была арестована и предана суду. Расшифрованные письма были тем свидетельством, которое в конечном счете привело королеву к смертной казни за участие в заговоре.

Как математики способствовали победе во Второй мировой войне

Когда стало понятно, что шифру подстановки присуща эта уязвимость, криптографы начали придумывать более изощренные способы кодирования, чтобы отразить атаки, использующие подсчет букв. Одна идея состояла в варьировании шифра подстановки. Вместо того чтобы использовать лишь один шифр подстановки для всего текста, вы можете поочередно использовать два различных шифра. Таким образом, если вы, к примеру, кодируете слово beef, то буквы е в нем будут закодированы по-разному, поскольку к первой из них применяется один шифр, а ко второй – другой. Может оказаться, что beef будет закодирована как PORK[14]. Чем более безопасным вы желаете сделать ваше сообщение, тем больше различных шифров нужно использовать в нем.

Если вам необходимо взломать шифр Камасутры, то для анализа частоты употребления различных букв в закодированном тексте может оказаться полезной следующая веб-страница: http://simonsingh.net.

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

Французский дипломат XVI в. Блез де Виженер считал, что для воспрепятствования частотному анализу будет достаточно переключаться между несколькими шифрами подстановки. Хотя шифр Виженера, как он стал известен, на самом деле является значительно более надежной формой кодирования, его все же можно взломать. Британский математик Чарльз Бэббидж в конечном счете нашел метод, позволяющий сделать это. Бэббидж по праву считается дедушкой компьютерного века: он был убежден, что машины можно использовать для автоматических вычислений, а в лондонском Музее науки можно увидеть реконструкцию его «Разностной машины» – механического аппарата для проведения вычислений. Именно систематический подход к решению задач способствовал тому, что в 1854 г. у него появилась идея, как взломать шифр Виженера.

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