Искусство мыслить рационально. Шорткаты в математике и в жизни

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

Во время Второй мировой войны немцы считали, что нашли хитроумный способ использования шифров подстановки, не позволяющий расшифровывать сообщения при помощи этого шортката. Идея заключалась в следующем: для кодирования каждой следующей буквы сообщения нужно использовать новый шифр подстановки. Например, если нужно было зашифровать последовательность букв ЕЕЕЕ, все буквы Е заменялись разными буквами, что делало бесполезными любые попытки применить частотный анализ аль-Кинди. Для шифрования сообщений таким методом множественной подстановки была создана специальная шифровальная машина «Энигма»[128].

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

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

Но они не приняли в расчет гениальность Гаусса XX века, математика Алана Тьюринга, который, работая в Блетчли-Парке, все же выискал в этой системе слабое место, позволявшее создать шорткат, который избавлял от необходимости перебора всех вариантов. Дело в том, что машина никогда не зашифровывала букву той же буквой. Ее схема всегда преобразовывала одну букву в какую-нибудь другую. Казалось бы, в этом нет ничего страшного. Но Тьюринг нашел способ использовать это свойство для получения гораздо более ограниченного набора вариантов шифровки конкретных сообщений.

Тем не менее для окончательных поисков ему все равно приходилось использовать машины. В домиках Блетчли-Парка ночи напролет жужжали «бомбы», как дешифровщики называли машины, которые реализовывали шорткат Тьюринга. Зато союзники каждую ночь получали доступ к сообщениям, которые немцы пересылали, считая их абсолютно защищенными от дешифровки.

Подозрительная простота

Коды, которые защищают сегодня наши кредитные карты, «летающие» по интернету, используют математические задачи, к решению которых, как мы считаем, в принципе не может быть шорткатов. В основе одного из таких шифров, который называется RSA[129], лежит загадочная категория чисел – простые числа. Каждый веб-сайт выбирает два секретных простых числа длиной порядка 100 знаков и перемножает их. Получившееся число, имеющее в длину около 200 знаков, можно опубликовать на сайте. Это кодовое число данного сайта. Когда я посещаю этот сайт, мой компьютер получает это 200-значное число, которое используется затем в математических операциях с моей кредитной картой. Зашифрованное таким образом число можно пересылать по интернету. Оно надежно защищено, так как для его расшифровки хакеру нужно было бы найти два простых числа, произведение которых дает 200-значное кодовое число веб-сайта. Такой шифр считается надежным, потому что эта задача, по-видимому, относится к категории задач об иголках в стогах сена. Математикам известен лишь один способ подбора таких простых чисел: перебирать эти числа одно за другим, надеясь случайно набрести на иголку, то есть на число, на которое кодовое число сайта делится без остатка.