магическое число d внутри себя; фактически можно было бы запоминать в RSA-блоке только число d вместо чисел р и поскольку в обязанности блока после вычисления числа N входит только защита своих секретов и вычисление кубических корней по модулю N.

Подобная схема кодирования не дает эффекта, если х < \/N, так как х mod N = х, а. кубический корень легко можно найти. Из описанного в разделе 4.2.4 логарифмического закона ведущих разрядов следует, что старшая позиция xi fc-раз-мерного сообщения {xi,... ,Xk) будет меньше примерно в случаев, поэтому данная проблема требует своего решения. В упр. 32 рассмотрен один из способов, позволяющих избежать этих сложностей.

Надежность схемы кодирования при помощи RSA базируется на том факте, что никто не может узнать, как вычислять кубический корень по модулю N, не зная множителей числа N. Похоже, что не существует методов, позволяющих это сделать, однако абсолютной уверенности нет. Все, что можно сказать по данному поводу,- это то, что обычные методы обнаружения кубических корней задачу не решают. Например, бесполезно пытаться вычислять число d как функцию числа N; причина в том, что если известно d или фактически если известно любое число т разумной длины, такое, что равенство х mod N = 1 справедливо для значительного количества величин X, то потребуется намного больше шагов для поиска множителей числа N (упр. 34). Таким образом, любой из методов, основанных на явной или скрытой попытке нахождения такого числа т, не может оказаться лучше, чем метод разложения на простые множители.

Тем не менее нужно соблюдать осторожность. Если одно и то же сообщение по компьютерной сети отослано трем лицам, то некто, кому известно х по модулю Ni, N2 ч N3, может восстановить х mod N1N2N3 = х, используя китайскую теорему об остатках, после чего число х уже не будет секретом. Фактически даже в случае, когда одно и то же сообщение отослано семерым разным лицам с отметками времени (2\x + ti) mod Ni, в которых времена U известны или могут быть с достаточной достоверностью предугаданы, значение величины х может быть найдено (упр. 44). В связи с этим некоторые криптографы рекомендуют кодировать информацию с использованием числа 2 + 1 = 65 537 вместо 3. Данный показатель степени является простым, поэтому на вычисление числа а;? jqj затрачивается примерно в 8.5 раз больше времени, чем на вычисление числа х mod Л. [CCITT Recommendations Biue BooJc (Geneva: International Telecommunication Union, 1989), Fascicle VIII.8, Recommendation X.509, Annex C, 74-76.]

В оригинальном описании методики шифрования Р. Л. Ривест, А. Шамир и Л. Эдлеман предлагали кодировать число х числом а;" modV, где а-любой простой показатель функции (p{N), а не только о = 3. Тем не менее на практике предпочтение отдается показателю, для которого кодирование вьшолняется быстрее, чем декодирование.

Чтобы схема, реализуемая в RSA, была эффективной, числа р и g не должны оказаться "случайно" близкими простыми. Как подчеркивалось выше, чтобы обеспечить существование единственных кубических корней по модулю Л, числа р - 1 и д-1 не должны делиться на 3. Другое условие сводится к тому, что для числа р-1 доджен существовать по крайней мере один очень большой простой множитель. То же самое относится и к числу q- 1; в противном случае число может быть раз-

ложено на простые множители по алгоритму из упр. 19. Фактически этот алгоритм сводится к поиску малого числа тп, характеризуемого тем, что ж" mod N быстро становится равным 1, а мы уже знаем, что использовать такое число небезопасно. Если для чисел р - 1 и g - 1 существуют большие простые множители pi и qi, то согласно теории, изложенной в упр. 34, число т будет либо кратным pii (тогда его будет трудно найти), либо вероятность того, что ж"* = 1, будет меньше, чем 1/pigi (поскольку число ж"* mod N почти никогда не равно 1). К тому же нежелательно, чтобы числа р и q были близки одно к другому; иначе их можно будет довольно просто найти, используя алгоритм D. Нежелательно также, чтобы отношение этих чисел p/q было близко к простой дроби, в противном случае эти числа можно будет получить, используя обобщение Лемана из алгоритма С.

Предлагаемая процедура генерирования чисел р и q почти всегда выполняется безошибочно. Начинаем с правдоподобного случайного числа ро, принадлежащего интервалу, скажем, между 10° и 10. Находим первое простое число pi, большее, чем Ро; для этого потребуется проверить Inpo « 90 нечетных чисел. Будет вполне достаточно, если после 50 пробных делений, вьшолняемых алгоритмом Р, число pi окажется "вероятно, простым" с вероятностью > 1 - 2""°°. После этого выбираем другое правдоподобное случайное число рг между, скажем, 10 и 10*°. Находим первое простое число р вида kpi + 1, где к > р2, к - четное и А; = pi (по модулю 3). Для этого, прежде чем простое число р будет найдено, потребуется проверить I lnpip2 « 90 чисел. Простое число р будет длиной около 120 разрядов; подобная конструкция может быть применена и для поиска простого числа q длиной около 130 разрядов. Чтобы обеспечить супернадежность, желательно убедиться в том, что числар-И nq+lne содержат малых простых множителей (упр. 20). Теперь произведение N = pq, величина которого имеет порядок 10°, удовлетворяет всем требованиям, и в настоящее время такое число не может быть разложено на простые множители.

Например, предположим, что известен метод разложения 250-разрядного числа N, время выполнения которого имеет порядок iV° мс. Следовательно, для разложения такого числа на простые множители потребуется 10 мс, но в году имеется только 31556 952 ООО ООО мкс, так что для завершения процесса разложения потребуется более Зх 10 лет машинного времени. Если предположить, что закуплено 10 млрд компьютеров и все они задействованы в решении этой проблемы, пройдет более 31 года, прежде чем один из них разложит число N на простые множители. Но пока правительство будет закупать так много специализированных компьютеров, люди начнут применять 300-разрядные числа N.

Поскольку метод кодирования х mod N известен, он обладает еще и дополнительными достоинствами, помимо того факта, что расшифровать код можно только при помощи RSA-блока. Такие системы "общедоступных ключей" были впервые рассмотрены В. Диффи (W. Diffie) и М. Э. Хеллманом (М. Е. Hellman) в журнале IEEE Trans. IT-22 (1976), 644-654. Как пример того, что можно сделать, когда метод кодирования широко известен, предположим, что Алиса желает связаться с Бобом по электронной почте и при этом они оба хотят, чтобы их письма были подписаны так, чтобы получатели были уверены, что никто не подделывает сообщение. Пусть Еа{М) - кодирующая функция для сообщений М, направляемых Алисе, а Ва{М) -декодирующая функция RSA-блока, установленного у Алисы. Пусть так-

же Ев{М), Db{M) - соответственно кодирующая и декодирующая функции RSA-блока, принадлежащего Бобу. Тогда Алиса может отослать подписанное сообщение, поставив свою подпись и дату, а затем переслать Бобу сообщение Eb{Da{M)), использовав для вычисления Da{M) свой компьютер. Когда сообщение получает Боб, его RSA-блок преобразует это сообщение в сообщение Da{M); Бобу известно Еа, так что он может вычислить М = Ea{Da{M)). Это должно убедить его, что сообщение поступило именно от Алисы; никто другой не мог отослать сообщение с кодом Da{M). (Ну хорошо, теперь Бобу известен и кодПа{М), поэтому он, посылая сообщение Ех{Da{M)) Ксавьеру, может представлять Алису. Чтобы защититься от таких попыток подделки, в содержимом кода М должно быть четко указано, что оно предназначено только для Боба.)

Естественно задать вопрос, каким образом Алиса и Боб узнают кодирующие функции Еа и Ев друг друга? Простого хранения этих функций в общедоступном файле явно недостаточно, поскольку некто Чарли может проникнуть в этот файл, подставив вычисленный им код N. Затем Чарли получит возможность тайно перехватывать и декодировать чужие сообщения до того, как Алиса или Боб что-нибудь заподозрят. Выход из этой ситуации заключается в том, чтобы хранить такие произведения Na и Nb в специальном общедоступном каталоге, который имеет собственный RSA-блок и широко известное произведение Nd- Когда Алиса пожелает узнать, как связаться с Бобом, она запросит в этом каталоге произведение для Боба; компьютер, управляющий каталогом, отправит ей подписанное сообщение, выдав значение Nb- Такое сообщение должно быть легитимным, поскольку подделать его никто не сможет.

Интересную альтернативу RSA-схеме предложил Майкл Рабин (Michael Rabin). В работе, опубликованной в MIT Lab. for Сотр. Sci., report TR-212 (1979), он описал способ кодирования функцией mod N вместо функции х mod N. В этом случае механизм декодирования, который можно было бы назвать SQRT-блоком, возвращает четыре различных сообщения; суть в том, что четыре различных сообщения содержат один и тот же квадрат по модулю N, а именно - х, -х, fxmodN и (-fx) mod N, где

/ = (p»-i-gP-i)modiV.

Если условиться на будущее, что х - четное число или что ж < V, то двусмысленность коснется двух сообщений, из которых предположительно только одно имеет смысл. Эта двусмысленность может быть легко устранена, как показано в упр. 35. Схема Рабина "обладает важным свойством - найти квадратные корни по модулю N, вероятно, так же трудно, как найти разложение на простые множители числа N = рд. Если число х выбрать случайно, шансы на то, что при вычислении квадратного корня из mod N будет найдено значение у, такое, что выполняются условия

ж = и ж ±у,

причем gcd(ж-у, N) = р или д, равны 50/50. Однако эта система имеет существенный изъян, который, похоже, отсутствует в RSA-схеме (упр. 33). Каждый, кто обращается к SQRT-блоку, может легко определить простые множители числа N. Это не только допускает возможность жульничества со стороны нечестных служащих или угрозы вымогательства, но также позволяет выдать секрет чисел рид. После этого