11 ≡ 184. Смайли радирует в Лондон: «Было бы неплохо выпить чаю со 184».
Ни один из советских шпионов ни за что не догадается, что за числом 184 прячется скромная семерка. Это может узнать только лондонский Цирк. Тоби Эстерхази, тот самый человек, который в Цирке отвечает за декодирование зашифрованных депеш, лезет в свой сейф и достает оттуда документ с грифом «Совершенно секретно», в котором записана относящаяся к модулю 221 и степени 11 «секретная экспонента». Эту экспоненту (показатель степени) знает только Цирк и носится с ней как курица с яйцом. Эта экспонента известна лишь самому узкому кругу посвященных. Относящаяся к модулю 221 и показателю степени 11 экспонента равна 35.
Чтобы расшифровать донесение Смайли, Тоби Эстерхази поступает приблизительно так же, как Джордж Смайли. Он записывает присланное ему кодовое число 184 и умножает его само на себя 35 раз, то есть делает именно то, чего требует от него секретная экспонента из бронированного сейфа. Однако 18435 — это чудовищно громадное число с 80 разрядами. Для бедного Эстерхази это непосильная задача. Но так же, как Смайли, Тоби Эстерхази знает, как помочь этому горю. Он вычисляет значения последовательности степеней числа 184 — 1841, 184², 1844, 1848, 18416, 18432, причем все результаты Тоби немедленно сокращает на модуль 221. Ряд чисел приобретает следующий вид. Первым идет число 1841 = 184. Затем следует 184 × 184, то есть число 33 856. В этом числе модуль 221 содержится 153 раза. Тоби Эстерхази считает:
33 856 — 153 × 221 = 33 856 — 33 813 = 43
и приходит к результату 184² ≡ 43. Теперь для следующей степени Тоби имеет: 1844 = 184² × 184². Для вычисления этого произведения Тоби умножает остаток 43, соответствующий 184², на то же число, то есть на 43. 43 × 43 = 1849. Модуль 221 содержится в этом числе 8 раз. Тоби считает дальше и приходит к результату 1844 ≡ 81. Тоби переходит к следующей степени: 1848 = 1844 × 1844. Это число Эстерхази определяет с помощью перемножения само на себя числа, равного остатку, соответствующему числу 1844, то есть 81. 81 × 81 = 6561. Модуль 221 содержится в этом числе 29 раз. Тоби считает:
6561 — 29 × 221 = 6561 — 6409 = 152
и приходит к результату 1848 ≡ 152. Переходим к следующей степени: 18416 = 1848 × 1848. Ее Тоби вычисляет с помощью соответствующего числу 1848 остатка 152, который Тоби умножает на то же число. 152 × 152 = 23 104. Модуль 221 содержится в этом числе 104 раза. Тоби считает
23 104 — 104 × 221 = 23 104 — 22 984 = 120
и приходит, следовательно, к результату 18416 ≡ 120. Теперь настала очередь степени 18432 = 18416 × 18416. Перемножение числа, равного остатку, соответствующему числу 18416, то есть 120 с самим этим числом дает в результате 120 × 120 = 14 400. Модуль 221 содержится в этом числе 65 раз. С помощью следующего расчета
14 400 — 65 × 221 = 14 400 — 14 365 = 35
Тоби находит, что 18432 ≡ 35.
Теперь Тоби уже почти у цели, ибо для того, чтобы вычислить 18435, ему надо вычислить произведение 18432 × 184² × 1841, ибо сумма 32 + 2 + 1 в точности равна 35, то есть величине секретной экспоненты. Тоби Эстерхази пользуется соответствующими остатками и получает 35 × 43 × 184, или 276 920. В этом числе модуль 221 содержится 1253 раза, и вычитание дает:
276 920 — 1253 × 221 = 276 920 — 276 913 = 7.
Таким образом, Тоби Эстерхази получает число, которое, собственно говоря, и прислал Джордж Смайли, так как 18435 ≡ 7.
Смайли хотел попить чаю по ту сторону железного занавеса с агентом 007.
Тоби тщательно пересчитывает результат еще раз, потом еще, ибо даже крошечная ошибка может оказаться смертельной. Однако почему этот метод подсчета с секретной экспонентой 35 работает таким волшебным способом, почему из присланного числа 184 в результате расшифровки получилось число 7, то есть стало ясно желание Смайли встретиться с агентом 007, Тоби Эстерхази не понимает{15}. Он просто делает то, что ему поручено. Делает ради славы Англии, ради Билла Хейдона, своего непосредственного начальника, которому Тоби безусловно предан. И кроме того, ради своего честолюбия — ибо если у него сейчас все получится, то он войдет в лифт, нажмет заветную кнопку и вознесется на самый верхний этаж Цирка, где как небожитель обитает сам Билл Хейдон.
Теперь нам ясно, как работают кудесники-шифровальщики. Правда, открытым остается еще один вопрос.
Большие простые числа
Что, однако, можем мы теперь спросить, помешает русским агентам посчитать результат так же, как считал его Тоби? Ведь они же знают, не хуже Цирка, модуль 221 и экспоненту 11, а также отправленное Джорджем Смайли кодовое число 184. Что мешает им вычислить остаток от деления числа 18435 на 221?
Дело в том, что они не знают секретную экспоненту 35.
Но не могут ли они, зная модуль 221 и показатель степени 11, вычислить секретную экспоненту 35? Ведь каким-то образом это удалось сделать яйцеголовым из Цирка, которые затем заперли в сейф бумажку с этим заветным числом.
Надо сказать, что вообще-то это возможно. И нет никакой тайны в том, как именно получили число 35. Во всяком случае, ее нет, если знать, что 221 есть результат перемножения двух простых чисел 13 и 17: 13 × 17 = 221. Все остальное очень просто. Далее следуют такому «рецепту»: из обоих простых чисел вычитают по единице и получают соответственно числа 12 и 16, а затем перемножают их: 12 × 16 = 192. Это число 192 является «секретным модулем».
Затем составляют таблицу из увеличенных на единицу произведений последовательности натуральных чисел на секретный модуль 192, или, другими словами, следующие числа:
1 × 192 + 1 = 192 + 1 = 193,
2 × 192 + 1 = 384 + 1 = 385,
3 × 192 + 1 = 576 + 1 = 577,
4 × 192 + 1 = 768 + 1 = 769,
5 × 192 + 1 = 960 + 1 = 961
…
Какое-то из полученных чисел 193, 385, 577, 769, 961, … делится на показатель степени 11. В нашем примере уже второе из этих чисел кратно 11 — действительно, 385: 11 = 35. Так мы находим секретную экспоненту 35.
Однако если это так просто, то к чему все эти хлопоты? На самом деле все так просто, потому что в нашей вымышленной истории за модуль было принято небольшое число 221, которое можно без особых усилий представить в виде произведения двух простых чисел. Если бы Цирк предложил в качестве модуля большое число, то вся простота мгновенно бы улетучилась.
Здесь надо, конечно, признать, что вся история о Смайли и его требовании прислать агента 007 до предела упрощена, и вообще в реальности ничего подобного быть просто не могло. Хотя бы по той причине, что описанный мною способ шифрования был изобретен только в 1977 г. в Массачусетском технологическом институте{16}. К этому времени Джордж Смайли уже давно был на долгожданном покое и, как писал Джон ле Карре, «поселился в Стипл-Астоне и жил так, как вышедший на пенсию старый чудак-отшельник, удивлявший обывателей своей милой привычкой бродить по улицам, вслух разговаривая с самим собой».
Тем не менее описанный здесь метод шифрования действительно существует, и был он предложен специалистами по информатике Рональдом Ривестом, Ади Шамиром и Леонардом Адлеманом и назван по первым буквам их фамилий «RSA-методом». Для шифрования берут два простых числа — в нашем примере 13 и 17 — и перемножают их между собой. Таким способом получают модуль. У нас он получился равным 13 × 17 = 221. Потом берут произвольное число — в нашем случае 11 — и называют его степенью. (Выбор степени не вполне произволен, но в данном случае это несущественная деталь.) После этого число, которое хотят сохранить в тайне, кодируют, возводя его в степень, а остаток от деления полученного числа на модуль сообщают партнеру. В нашей истории Смайли хотел сообщить число 7. Для этого он вычислил значение степени 711, разделил его на 221, а остаток от деления, то есть число 184, сообщил своему начальству. Дешифровка осуществляется так: из выбранных простых чисел вычитают по единице, а затем перемножают между собой. Мы назвали это произведение секретным модулем. В нашем случае он равен числу 12 × 16 = 192. Так как в нашей истории 2 × 192 + 1 = 35 × 11, секретная экспонента равна 35. Степень зашифрованного числа с показателем, равным секретной экспоненте, дает в результате, если проанализировать остаток от деления на модуль, исходное число, отправленное агентом. В нашем случае Тоби Эстерхази разделил 18435 на 221 и получил 7, то есть номер того агента, с которым хотел встретиться Смайли.
На деле для шифрования чисел по методу RSA, в отличие от нашей вымышленной истории, используют произведения простых чисел, неизмеримо больших, нежели 13 и 17. Используют огромные простые числа с тремястами или четырьмястами разрядами. Естественно, что произведения этих чисел дают в результате гигантские модули из семисот-восьмисот разрядов. Расчеты с такими числами можно выполнять только с помощью компьютеров, но умножение машины выполняют молниеносно. По методу RSA модуль вычисляют за считаные секунды.
Секретной службе абсолютно безразлично, знает ли противник (да хоть и весь мир) величину модуля, потому что вычислить два простых числа, произведение которых составляет число, состоящее из 700 разрядов, очень и очень непросто. До сих пор не существует алгоритмов, позволяющих сделать это быстро. Даже при использовании самых совершенных компьютеров, обладающих невероятным быстродействием, на решение этой задачи могут уйти