Так что шахматы, несмотря на все легенды и загадочность, по сути, то же самое, что крестики-нолики или «Ним». При встрече двух идеальных игроков либо белые всегда выигрывают, либо белые всегда проигрывают, либо неизменно будет ничья. И в принципе вычисление, какой из вариантов будет реализован, – всего лишь вопрос продвижения по дереву до корня. Шахматы – это сложная задача, но не настолько, как написание стихотворения, отражающего[216] пересечение политики атомного века середины столетия с модернизацией городов, ностальгией по детству, бесконечными отзвуками Гражданской войны и заменой человеческого духа механизированными изобретениями, а в смысле перемножения двух действительно больших чисел. Это может занять много времени, но в принципе вы знаете, как постепенно, шаг за шагом справиться с задачей.
В принципе. Это словосочетание – маленький коврик, элегантно уложенный над бездонной пропастью трудностей!
Игра «Ним» с двумя кучками по два камня – проигрыш. «Четыре в ряд»[217] – победа. Но для шахмат мы не знаем, будет победа, поражение или ничья. Возможно, никогда и не узнаем. У шахматного дерева очень много листьев. Нам доподлинно неизвестно сколько, но уж точно больше, чем способен рассмотреть восьмифутовый робот. Клод Шеннон, которого мы оставили за созданием фальшивого английского текста с помощью цепей Маркова, также написал одну из первых серьезных работ[218] о машинных шахматах; по его оценке, количество листьев на этом дереве выражается числом, примерно состоящим из единицы и 120 нулей, – сто миллионов триллионов гуголов. Это не просто большое число, оно больше, чем количество чего-либо во Вселенной, и уж точно это не то количество вещей, которые вам захочется просмотреть и обозначить буквами В, П или Н. В принципе, конечно, можно, но в реальности – нельзя.
Это явление (вычисления, которые мы умеем делать, но не делаем за неимением времени) – минорный мотив, звучащий на протяжении всей истории математики компьютерной эпохи. Вернемся на секунду к разложению на простые множители. Мы уже видели, что это можно делать без особых размышлений. Если вы начинаете, скажем, с числа 1001, то вам нужно найти число, на которое 1001 делится нацело, а если такого нет, то 1001 – простое число. Годится ли 2? Нет, 1001 не делится пополам. А 3? Нет. А 5? Нет. А 7? Да, поскольку 1001 = 7 × 143. (Тысяча и одна ночь – это сто сорок три недели.) Теперь можно махать топором над числом 143, проверяя деление за делением, пока не обнаружим, что 143 = 11 × 13.
Но что, если число, которое мы пытаемся разложить, состоит из двух сотен цифр? В этом случае проблема значительно превышает шахматный уровень. Чтобы проверить все возможные делители, не хватит продолжительности жизни Вселенной. Да, это всего лишь арифметика, но при этом, насколько нам известно, совершенно невыполнимая.
И это хорошо, поскольку в реальном мире, несомненно, есть нечто более ценное для вас, чья безопасность зависит от сложности этой задачи. Какое отношение факторизация чисел имеет к безопасности? Для этого нам нужно вернуться к криптографии конфедератов и книге экспериментальной поэзии в прозе Гертруды Стайн Tender Buttons («Нежные кнопки»).
Предположим, Акбар и Джефф после окончания игры решают тайно пообщаться. И это вполне реально, если у них есть общая секретная система кодирования. Общая – ключевое слово; они должны использовать один и тот же код, а это предполагает наличие некоторой общей информации, обычно называемой ключом. Допустим, ключом будет текст «Нежных кнопок» Гертруды Стайн. Если Акбар хочет втайне передать Джеффу сообщение Nim has grown dreary («Ним стал скучным»), он может сделать это так: написать его над первыми словами первого стихотворения в сборнике «Нежные кнопки» (A CARAFE, THAT IS A BLIND GLASS. A kind in glass and a cousin, a spectacle and nothing strange a single hurt color and an arrangement in a system to pointing), ставя в соответствие одну букву другой.
Теперь складываем каждую пару букв. Конечно, буквы не числа, но у каждой есть номер в алфавите, так что суммируем именно эти номера. Обычно начинают с 0, так что A – это буква номер 0, B – это буква номер 1 и так далее. В нашем случае в первой паре N – тринадцатая буква, A – нулевая, 13 + 0 = 13, поэтому берем тринадцатую букву N. Во второй паре сумма I + C дает 8 + 2 = 10, что соответствует десятой букве – K. Продолжая действовать таким образом, получаем в итоге зашифрованный текст NKM YAX K…
Однако дальше мы сталкиваемся с небольшой проблемой: R(17) + T(19) дает 36, а такой буквы нет. Но, оказывается, проблема легко решаема: после Z мы просто начинаем счет заново, и тогда двадцать шестая буква будет снова A, двадцать седьмая – B и так далее. Поэтому 36 будет соответствовать та же буква, что и числу 10, то есть K. В итоге ваше сообщение будет выглядеть так:
Теперь Джефф, получив зашифрованное сообщение и, разумеется, экземпляр книги Гертруды Стайн, может восстановить текст, но уже не добавляя, а вычитая буквы. N минус A означает 13 – 0 = 13, а числу 13 соответствует N. И так далее. Когда мы доберемся до второй K, нам предстоит вычесть T(19) из K(10). Получится – 9, но не беспокойтесь, все в порядке! Минус девятая буква находится за 9 букв до буквы А(0), а поскольку мы расположили буквы по циклу и A следует за Z, то девятая буква перед А – это восьмая буква перед Z, то есть R.
Если вам категорически не нравится сложение и вычитание, можете просто держать под рукой такую табличку[219]:
Она похожа на таблицу сложения, которой пользуются в начальной школе, но только для букв! Чтобы вычислить R + T, просто посмотрите на строку R и столбец T (или на строку T и столбец R) – и получите K.
Или еще лучше воспользоваться той геометрией, которую этот код накладывает на алфавит. По нашему правилу, когда мы сдвигаемся на одну букву правее Z, мы не выходим за пределы английского алфавита, а возвращаемся к А. Это означает, что мы представляем алфавит не в виде строки
ABCDEFGHIJKLMNOPQRSTUVWXYZ,
а в виде круга.
Каждая буква A в «Нежных кнопках» Гертруды Стайн – это 0; а значит, когда в ключе появляется А, мы оставляем букву исходного сообщения неизменной. Каждая буква С означает вращение круга против часовой стрелки на две позиции[220]. С такой геометрической точки зрения очевидно, почему этот код легко расшифровать при наличии ключа: достаточно повернуть круг на ту же величину, но по часовой стрелке.
Такой код называется шифром Виженера – в честь Блеза де Виженера, французского ученого XVI века, который его не изобретал. Подобные случаи в науке настолько распространены, что статистик и историк Стивен Стиглер сформулировал закон: «Ни одно научное открытие не названо в честь первооткрывателя». (Как отмечал сам Стиглер, закон Стиглера[221] впервые сформулировал социолог Роберт Мертон[222].)
Виженер был благородного происхождения[223], с хорошими связями, автором множества книг, секретарем у французского посланника на Вормсском рейхстаге, затем у герцога Неверского и короля Генриха. На таких должностях (особенно во время пребывания в Риме) он сталкивался с самыми сложными кодированными сообщениями. Мир римской криптографии XVI столетия был средоточием соперничества и ревностно охраняемых секретов. Известен случай, как Виженер разыграл одного из оппонентов, Пауло Панкатуччо, личного шифровальщика папы римского, написав ему сообщение по-детски примитивным шифром. Панкатуччо быстро декодировал текст и обнаружил поток оскорблений в свой адрес: «О бедный жалкий раб собственных дешифровок, на которые ты тратишь все свое масло и свои старания… Используй в будущем свой досуг и усилия на что-то более полезное и прекрати бездарно растрачивать свое время, одной-единственной минуты которого не купишь за все сокровища мира. Проверь прямо сейчас, сможешь ли ты узнать смысл хотя бы одной маленькой буквы из того, что написано дальше». И в этот момент шифр переключался на собственное изобретение Виженера – надежный код, который, как криптограф прекрасно знал, был Панкатуччо не по зубам. Все это нам известно из труда Виженера Traicté des Chiffres ou Secrètes Manières d’Escrire («Трактат о цифрах и тайнописи»), который стал стандартным справочником по криптографии, в то время как остальные работы ученого были забыты. Трактат содержит множество собственных сложных кодов Виженера, а также основные идеи вышеописанного более простого шифра Виженера, на самом деле изложенные в 1553 году[224] в труде Джовани Беллазо, который его изобрел, работая секретарем и шифровальщиком у кардинала Дюранте Дюранти в Камерино. (Насколько высоко требовалось в те дни подняться в церковной иерархии, чтобы обзавестись собственным шифровальщиком?)
Беллазо был высокого мнения о своем шифре, утверждая, что он обладает «таким изумительным совершенством[225], что его может использовать весь мир, и при этом никто не сможет понять, что пишет другой, за исключением тех, кто обладает очень коротким ключом, как написано в этой книге вместе с объяснением и способом применения». Мир в целом согласился с его оценкой: так называемый шифр Виженера стал широко известен как le chiffre indechiffrable (неразгадываемый шифр). И действительно, до появления теста Касиски, который, как мог бы предсказать Стиглер, на самом деле был изобретен Чарльзом Бэббиджем за два десятилетия до Фридриха Касиски