Искусство мыслить рационально. Шорткаты в математике и в жизни - Маркус дю Сотой
Шрифт:
Интервал:
Закладка:
Если хакер перехватит закодированное сообщение, ему придется перебрать огромное количество разных комбинаций, чтобы его расшифровать. Но у этого шифра есть слабое место, которое обнаружил живший в IX веке ученый-энциклопедист Якуб аль-Кинди: некоторые буквы встречаются в текстах чаще, чем другие. Например, в любом тексте на английском языке чаще всего – в 13 процентах случаев – встречается буква e; второе место занимает буква t с 9 процентами[127]. Кроме того, у букв бывают индивидуальные характеристики, отражающиеся в тех сочетаниях, в которых они обычно используются. К примеру, после буквы q всегда идет u.
Аль-Кинди понял, что это может служить шорткатом для расшифровки сообщения, закодированного шифром подстановки. Если произвести частотный анализ закодированного текста и сопоставить чаще всего встречающиеся буквы с теми, которые наиболее часто попадаются в тексте нешифрованном, можно начать расшифровывать сообщение. Частотный анализ вообще дает поразительный шорткат к расшифровке таких кодов, которые оказываются не столь надежными, как может показаться.
Во время Второй мировой войны немцы считали, что нашли хитроумный способ использования шифров подстановки, не позволяющий расшифровывать сообщения при помощи этого шортката. Идея заключалась в следующем: для кодирования каждой следующей буквы сообщения нужно использовать новый шифр подстановки. Например, если нужно было зашифровать последовательность букв ЕЕЕЕ, все буквы Е заменялись разными буквами, что делало бесполезными любые попытки применить частотный анализ аль-Кинди. Для шифрования сообщений таким методом множественной подстановки была создана специальная шифровальная машина «Энигма»[128].
Одна из этих машин до сих пор выставлена на всеобщее обозрение в поместье Блетчли-Парк, в котором работали во время войны британские дешифровщики. На первый взгляд она кажется похожей на обычную пишущую машинку с клавиатурой, но выше клавиатуры имеется второй набор букв. Когда нажимаешь на одну из клавиш, над клавиатурой загорается одна из букв. Именно так кодируется каждая буква. Схема машины, по сути дела, перемешивает буквы, как в классическом шифре подстановки. Но при том же нажатии клавиши можно услышать щелчок и увидеть, как один из трех роторов, установленных в самом сердце машины, поворачивается на одно деление. Если нажать на ту же клавишу еще раз, загорится другая лампочка. Дело в том, что соединение между клавиатурой и лампочками изменилось. Соединительные провода проходят через роторы, и их повороты изменяют схему соединений в машине. Таким образом, вращение роторов обеспечивает использование нового шифра подстановки при кодировании каждой следующей буквы.
Казалось, что взломать такой шифр невозможно. Для настройки машины можно использовать шесть разных роторов, у каждого из которых есть 26 разных начальных состояний. Кроме того, в задней части машины имеется множество проводов, которые могут добавлять еще один уровень фиксированного шифрования. В общей сложности получается 158 миллионов миллионов миллионов вариантов настройки. Попытки определить, какой из них использовал оператор при зашифровке сообщения, казались буквальным воплощением идеи поисков иголки в стоге сена. Немцы были абсолютно уверены, что взломать эту машину невозможно.
Но они не приняли в расчет гениальность Гаусса XX века, математика Алана Тьюринга, который, работая в Блетчли-Парке, все же выискал в этой системе слабое место, позволявшее создать шорткат, который избавлял от необходимости перебора всех вариантов. Дело в том, что машина никогда не зашифровывала букву той же буквой. Ее схема всегда преобразовывала одну букву в какую-нибудь другую. Казалось бы, в этом нет ничего страшного. Но Тьюринг нашел способ использовать это свойство для получения гораздо более ограниченного набора вариантов шифровки конкретных сообщений.
Тем не менее для окончательных поисков ему все равно приходилось использовать машины. В домиках Блетчли-Парка ночи напролет жужжали «бомбы», как дешифровщики называли машины, которые реализовывали шорткат Тьюринга. Зато союзники каждую ночь получали доступ к сообщениям, которые немцы пересылали, считая их абсолютно защищенными от дешифровки.
Подозрительная простота
Коды, которые защищают сегодня наши кредитные карты, «летающие» по интернету, используют математические задачи, к решению которых, как мы считаем, в принципе не может быть шорткатов. В основе одного из таких шифров, который называется RSA[129], лежит загадочная категория чисел – простые числа. Каждый веб-сайт выбирает два секретных простых числа длиной порядка 100 знаков и перемножает их. Получившееся число, имеющее в длину около 200 знаков, можно опубликовать на сайте. Это кодовое число данного сайта. Когда я посещаю этот сайт, мой компьютер получает это 200-значное число, которое используется затем в математических операциях с моей кредитной картой. Зашифрованное таким образом число можно пересылать по интернету. Оно надежно защищено, так как для его расшифровки хакеру нужно было бы найти два простых числа, произведение которых дает 200-значное кодовое число веб-сайта. Такой шифр считается надежным, потому что эта задача, по-видимому, относится к категории задач об иголках в стогах сена. Математикам известен лишь один способ подбора таких простых чисел: перебирать эти числа одно за другим, надеясь случайно набрести на иголку, то есть на число, на которое кодовое число сайта делится без остатка.
О задаче разложения чисел на простые множители писал в своем великом трактате по теории чисел под названием «Арифметические исследования» (Disquisitiones Arithmeticae, 1801) сам Гаусс: «То, что задача о том, как отличать составные числа от простых и разлагать первые на их простые сомножители, принадлежит к важнейшим задачам всей арифметики и привлекала внимание как математиков древности, так и математиков нашего времени, настолько хорошо известно, что было бы излишним тратить здесь на это много слов… Кроме того, и интересы самой науки как таковой обязывают приложить все усилия к решению этой столь изящной и знаменитой проблемы»[130].
Он, разумеется, не сознавал, насколько важной станет эта задача в эпоху интернета и электронной торговли. Пока что никто, в том числе и сам великий Гаусс, не придумал шортката к нахождению простых делителей крупных чисел. Количество простых чисел, которые нужно перебрать,
