Число, пришедшее с холода. Когда математика становится приключением

Тем не менее описанный здесь метод шифрования действительно существует, и был он предложен специалистами по информатике Рональдом Ривестом, Ади Шамиром и Леонардом Адлеманом и назван по первым буквам их фамилий «RSA-методом». Для шифрования берут два простых числа — в нашем примере 13 и 17 — и перемножают их между собой. Таким способом получают модуль. У нас он получился равным 13 × 17 = 221. Потом берут произвольное число — в нашем случае 11 — и называют его степенью. (Выбор степени не вполне произволен, но в данном случае это несущественная деталь.) После этого число, которое хотят сохранить в тайне, кодируют, возводя его в степень, а остаток от деления полученного числа на модуль сообщают партнеру. В нашей истории Смайли хотел сообщить число 7. Для этого он вычислил значение степени 7¹¹, разделил его на 221, а остаток от деления, то есть число 184, сообщил своему начальству. Дешифровка осуществляется так: из выбранных простых чисел вычитают по единице, а затем перемножают между собой. Мы назвали это произведение секретным модулем. В нашем случае он равен числу 12 × 16 = 192. Так как в нашей истории 2 × 192 + 1 = 35 × 11, секретная экспонента равна 35. Степень зашифрованного числа с показателем, равным секретной экспоненте, дает в результате, если проанализировать остаток от деления на модуль, исходное число, отправленное агентом. В нашем случае Тоби Эстерхази разделил 184³⁵ на 221 и получил 7, то есть номер того агента, с которым хотел встретиться Смайли.

На деле для шифрования чисел по методу RSA, в отличие от нашей вымышленной истории, используют произведения простых чисел, неизмеримо больших, нежели 13 и 17. Используют огромные простые числа с тремястами или четырьмястами разрядами. Естественно, что произведения этих чисел дают в результате гигантские модули из семисот-восьмисот разрядов. Расчеты с такими числами можно выполнять только с помощью компьютеров, но умножение машины выполняют молниеносно. По методу RSA модуль вычисляют за считаные секунды.

Секретной службе абсолютно безразлично, знает ли противник (да хоть и весь мир) величину модуля, потому что вычислить два простых числа, произведение которых составляет число, состоящее из 700 разрядов, очень и очень непросто. До сих пор не существует алгоритмов, позволяющих сделать это быстро. Даже при использовании самых совершенных компьютеров, обладающих невероятным быстродействием, на решение этой задачи могут уйти месяцы. Однако для дешифровки знание этих простых чисел безусловно необходимо, ибо, только используя их, можно вычислить секретный модуль и секретную экспоненту. Без этого вычислить секретную экспоненту невозможно даже теоретически.

Конечно, если модуль известен на протяжении нескольких недель, не говоря уже о месяцах, то пользоваться им для шифрования рискованно. Возможно, противнику уже удалось вычислить оба простых числа, произведение которых равно модулю. Поэтому все секретные службы время от времени меняют модули и экспоненты, использующиеся для кодирования. Эти изменения не слишком трудоемки. В конце концов, существует бесконечное множество простых чисел. Количество 400-значных простых чисел превышает 10³⁹⁷. Это число начинается с единицы и заканчивается 397 нулями^{17}.

Методом RSA пользуются не только секретные службы.

Когда человек набирает на клавиатуре банкомата код своей банковской карты, этот номер передается в банк по открытой телефонной линии. Однако ни один посторонний человек не может подсмотреть код, потому что в банкомате он автоматически шифруется и только в зашифрованном виде передается в банк. Во всех операциях по выдаче наличных метод RSA бесчисленное множество раз используется в банкоматах по всему миру.

Если человек делает через интернет какой-либо заказ и оплачивает его кредитной картой, то номер этой карты должен быть передан по адресу проведения расчетов. Очень опасна сама возможность того, что этот номер может стать известным посторонним людям, которые затем могут считать все остальные данные кредитной карты. По этой причине фирмы одним нажатием клавиши шифруют номер карты, а затем дешифруют его — только после того, как зашифрованный номер приходит по нужному адресу. Таким образом, метод RSA обеспечивает безопасность электронной торговли.

Но не будем закрывать глаза на очевидное: смысл и цель создания метода RSA состоит в облегчении работы спецслужб — сокрытия и обмана, дезинформации и мошенничества.

Иллюзия и реальность