Искусство мыслить рационально. Шорткаты в математике и в жизни - Маркус Дю Сотой

Бывают такие ситуации, в которых важно, чтобы никаких шорткатов не было. Например, разработка нераскрываемых шифров. Разработчикам шифров выгодно такое положение вещей, когда взломать зашифрованное сообщение бывает, по-видимому, невозможно без полного перебора всех возможных вариантов. Взять, к примеру, кодовый замок. Если у него есть четыре колесика, на каждом из которых по десять цифр, то, чтобы его открыть, нужно перебрать 10 000 разных чисел, от 0000 до 9999. Некачественно изготовленные замки иногда выдают то положение, в котором замок открывается, потому что при установке правильной цифры в механизме замка происходит физический сдвиг, но в общем случае у взломщика нет никакого шортката, кроме перебора всех комбинаций.

Однако в других шифровальных системах обнаруживаются слабые места, которые можно использовать для создания шорткатов. Вот, например, классический «шифр Цезаря», он же шифр подстановки. Это код, в котором одни буквы алфавита систематически заменяют на другие. Например, каждая встречающаяся в сообщении буква А заменяется какой-нибудь другой буквой – скажем, буквой G. Затем все буквы B заменяются на одну из оставшихся букв. Таким образом, каждая из букв алфавита становится другой буквой. Разных шифров такого рода очень много. Существуют 26! (1 × 2 × 3 × … × 26) разных способов перестановки букв алфавита[126]. (В некоторых перестановках какая-нибудь буква может оставаться той же: например, буква Х заменяется на Х. Интересный вопрос: сколько существует шифров, в которых изменяются все буквы?) Чтобы стало понятно, о какой величине идет речь, заметим, что 26! секунд – это время, еще не прошедшее с момента Большого взрыва.

Если хакер перехватит закодированное сообщение, ему придется перебрать огромное количество разных комбинаций, чтобы его расшифровать. Но у этого шифра есть слабое место, которое обнаружил живший в IX веке ученый-энциклопедист Якуб аль-Кинди: некоторые буквы встречаются в текстах чаще, чем другие. Например, в любом тексте на английском языке чаще всего – в 13 процентах случаев – встречается буква e; второе место занимает буква t с 9 процентами[127]. Кроме того, у букв бывают индивидуальные характеристики, отражающиеся в тех сочетаниях, в которых они обычно используются. К примеру, после буквы q всегда идет u.

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

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

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

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

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

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

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