(р{тп) делится на (f(s), а из (2) следует, что (ж. s) = 1. Подобно (4). теперь легко находим ж = ad (mod s). А кроме того, имеем ж = 0 = ad (mod г). Получившиеся сравнения в силу (r.s) = 1 дают нам (5).

Функция (1), принятая в системе RSA. может быть вычислена достаточно быстро. Как это сделать, мы обсудим чуть ниже. Пока отметим лишь, что обратная к /(ж) функция / 1 : ж -> xd (mod то) вычисляется по тем же правилам, что и /(ж), лишь с заменой показателя степени е на d. Таким образом, для функции (1) будут выполнены указанные выше свойства а) и б).

Для вычисления функции (1) достаточно знать лишь числа е и то. Именно они составляют открытый ключ для шифрования. А вот для вычисления обратной функции требуется знать число d, оно и является «секретом», о котором речь идёт в пункте в). Казалось бы. ничего не стоит, зная число то. разложить его на простые сомножители, вычислить затем с помошью известных правил значение (f(m) и. наконец, с помошью (3) определить нужное число d. Все шаги этого вычисления могут быть реализованы достаточно быстро, за исключением первого. Именно разложение числа то на простые множители и составляет наиболее трудоемкую часть вычислений. В теории чисел несмотря на многолетнюю её историю и на очень интенсивные поиски в течение последних 20 лет. эффективный алгоритм разложения натуральных чисел на множители так и не найден. Конечно, можно, перебирая все простые числа до у/т. и. деля на них то. найти требуемое разложение. Но. учитывая, что количество простых в этом промежутке, асимптотически равно 2у/то- (In то)-1, см. [5]. гл. 5. находим, что при то. записываемом 100 десятичными цифрами, найдётся не менее 4-1042 простых чисел, на которые придётся делить то при разложении его на множители. Очень грубые прикидки показывают, что компьютеру, выполняющему миллион делений в секунду, для разложения числа то > 10" таким способом на простые сомножители потребуется не менее, чем 1035 лет. Известны и более эффективные способы разложения целых чисел на множители, чем простой перебор простых делителей, но и они работают очень медленно. Таким образом, название статьи М. Гарднера вполне оправдано.

Авторы схемы RSA предложили выбирать число то в виде произведения двух простых множителей р и q. примерно одинаковых по величине. Так как

то единственное условие на выбор показателя степени е в отображении

(1) есть

(е,р-1) = (е,д-1) = 1.(7)

Итак. лицо, заинтересованное в организации шифрованной переписки с помошью схемы RSA. выбирает два достаточно больших простых числа р и q. Перемножая их. оно находит число то = pq. Затем выбирается число е. удовлетворяюшее условиям (7). вычисляется с помошью (6) число (f(m) и с помошью (3) - число d. Числа то и е публикуются, число d остается секретным. Теперь любой может отправлять зашифрованные с помошью (1) сообшения организатору этой системы, а организатор легко сможет расшифровывать их с помошью (5).

Для иллюстрации своего метода Ривест. Шамир и Адлеман зашифровали таким способом некоторую английскую фразу. Сначала она стандартным образом (а=01. Ь=02. .... z=26. пробел=00) была записана в виде нелого числа х. а затем зашифрована с помошью отображения (1) при

га =11438162575788886766932577997614661201021829672124236256256184293570 6935245733897830597123563958705058989075147599290026879543541

и е = 9007. Эти два числа были опубликованы, причем дополнительно сообщалось, что то = pq. где р и q - простые числа, записываемые соответственно 64 и 65 десятичными знаками. Первому, кто расшифрует соответствующее сообщение

f(x) =968696137546220614771409222543558829057599911245743198746951209308 16298225145708356931476622883989628013391990551829945157815154,

была обещана награда в 100$.

Эта история завершилась спустя 17 лет в 1994 г.. см. [6]. когда D. Atkins. М. Graff. А. К. Lenstra и Р. С. Leyland сообщили о расшифровке фразы, предложенной в [2]. Она1) была вынесена в заголовок статьи [6]. а соответствующие числа р и q оказались равными

р =3490529510847650949147849619903898133417764638493387843990820577, q =32769132993266709549961988190834461413177642967992942539798288533.

Интересующиеся могут найти детали вычислений в работе [6]. Здесь же мы отметим, что этот замечательный результат (разложение на множители 129-значного десятичного числа) был достигнут благодаря использованию алгоритма разложения чисел на множители, называемого

The magic words are squeamish ossifrage. Приведём перевод двух последних слов, входящих в эту. по всей видимости, бессмысленную фразу: squeamish - брезгливый, привередливый, обидчивый; ossifrage - скопа (вид птицы типа выпи).

методом квадратичного решета. Выполнение вычислений потребовало колоссальных ресурсов. В работе, возглавлявшейся четырьмя авторами проекта, и продолжавшейся после предварительной теоретической подготовки примерно 220 дней, на добровольных началах участвовало около 600 человек и примерно 1600 компьютеров, объединённых сетью Internet. Наконец, отметим, что премия в 100$ была передана в Free Software Foundation.

Описанная выше схема RSA ставит ряд вопросов, которые мы и попробуем обсудить ниже. Например, как проводить вычисления с большими числами, ведь стандартное математическое обеспечение не позволяет перемножать числа размером по 65 десятичных знаков? Как вычислять огромные степени больших чисел? Что значит быстрый алгоритм вычисления и что такое сложная вычислительная задача? Где взять большие простые числа? Как. например, построить простое число в 65 десятичных знаков? Существуют ли другие способы решения сравнения (2)? Ведь, если можно найти решение (2). не вычисляя секретный показатель d или не разлагая число m на простые сомножители, да ешё сделать это достаточно быстро, вся система RSA разваливается. Наверное, читателю могут прийти в голову и другие вопросы.

Начнем с конца. За 17 лет. прошедших между публикациями работ [2] и [6]. никто так и не смог расшифровать предложенную авторами RSA фразу. Конечно, это всего лишь косвенное подтверждение стойкости системы RSA. но все же достаточно убедительное. Ниже мы обсудим теоретические проблемы, возникаюшие при решении полиномиальных сравнений.

Мы не будем обсуждать, как выполнять арифметические действия с большими целыми числами, рекомендуем читателю обратиться к замечательной книжке Д. Кнута [7. гл. 4]. Заметим только, что большое число всегда можно разбить на меньшие блоки, с которыми компьютер может оперировать так же. как мы оперируем с цифрами, когда проводим вычисления вручную на бумаге. Конечно, для этого нужны специальные программы. Созданы и получили достаточно широкое распространение даже специальные языки программирования для вычислений с большими числами. Укажем здесь два из них - PARI и UBASIC. Эти языки свободно распространяются. Информацию о том. как их получить в пользование, можно найти в книге [19].