альные сообщения окажутся слишком длинными, чтобы принадлежать Жп, то их необходимо разбивать на части и зашифровать, используя режим нгафрования со сцеплением блоков (СВС), который описан в § 3-5). Тогда соответствующая ключу к функция шифрования Ek.Mk -Ск определяется как Ек(т) = rrf mod п. Для того чтобы полностью определить естественный алгоритм ее вычисления, достаточно записать п и е в открытый справочник. Такая пара (п, е) чисел называется рткрытым ключом. Он легко вычисляется простым перемножением р и из личного (секретного) ключа (р, 9,е).

Вспомним из § 1, что Efc является кандидатом на однонаправленную функцию с потайным ходом, и хотя существует эффективный алгоритм вычисления обратной ей функции D/., но мы не знаем, как получить его эффективно, задаваясь только естественным алгоритмом вычисления £/. (т.е. только при заданных п и е). Тем не менее такой эффективный алгоритм вычисления Dk легко построить, задав дополнительную секретную информацию, а именно - числа р и q, являюпдаеся множителями числа п. С этой целью, используя обобщеный алгоритм Евклида для нахождения наибольшего общего делителя, необходимо вычислить целое число d, такое, что е • с? = 1 (mod <р(п)), где (р(п) - (р - l){q - I). Тогда по известной теореме Эйлера т = т (mod п) для каждого целого числа т и, следовательно, т mod п = т при условии, что О га < п, которое обеспечивается, когда теМк- Функция дешифрования Dk-Ck-Mt, в связи с этим определяется как Dk{c) = m mod п, и для ее вычисления может быть использован также эффективный алгоритм модульного возведения в степень. (Для заданных чисел р я q существует даже более эффективный алгоритм вычисления Dk, который основан на китайской теореме об остатках [292].)

Таким образом, суммируя все сказанное, каждый пользователь криптосистемы RSA должен совершенно случайно и раз и навсегда выбрать для себя подходящие целые числа р, g и е и вычислить с их помощью d. После чего он должен сделать свой открытый ключ (е,п) доступным в пользовательском справочнике, но при этом сохранять d в секрете. Это дает возможность остальным пользователям зашифровывать посылаемые ему сообщения, которые только он один потом сможет расшифровать. Для того чтобы эта идея могла быть реализована на практи-

ке, решающим является удовлетворение требования, чтобы генерация больших случайных простых чисел и вычисление d были легкоосуществимы. К счастью, проверка чисел на простоту оказывается действительно легче их разложения на множители, благодаря вероятностным алгоритмам Роберта Соловея и Вол-кера Штрассена [339] и Майкла Рабина [298]. Проверке чисел на простоту посвящено несколько интересных работ, в частности, [289, 233, 271]. По поводу тесно связанного с криптографией вопроса о генерации подходящих простых чисел (но не их проверки на простоту) обращайтесь к [125, 16, 260]. Относительно описания расширенного алгоритма Евклида для вычисления d смотрите [7, 142] (но если же вы предпочитаете переоткрыть расширенный алгоритм Евклида самостоятельно, то можете найти полезными те указания, которые даны к задаче 8.5.12Ь из [77]).

В качестве небольшого примера, пусть р = 19 и = 23, так что п = 437, а <р{п) = 396. Пусть также е = 13, а значит d = 61, поскольку 13 • 61 = 793 = 2(р{п) + 1. Тогда сообщение открытого текста га = 123 будет зашифровано как с = 123 mod 437 = 386. Действительно, 386" mod 437 = 123.

Особо отметим ситуацию, когда криптоаналитик, перехвативший шифртекст c=Ek(m), посланный известному пользователю, знает естественный алгоритм шифрования Ek, который используется отправителем для вычисления с. Такое предположение имеет два важных следствия. Если бы нарушитель мог в точности угадать открытый текст сообщения га, то он был бы в состоянии точно так же, как и отправитель, вычислить ffc(ra), а затем проверить свою догадку, сравнив полученный результат с шифртекстом с. -Учитывая возможность исчерпывающего поиска, такая угроза является довольно опасной, если число возможных открытых текстов сравнительно невелико. Если же добавлять в короткие сообщения случайные биты, то эта трудность может быть до некоторой степени разрешена, однако, более приемлемым решением несомненно является использование вероятностного шифрования (см. § 6). При желании можете обратиться также к [308].

Более существенным для криптосистемы RSA является другое следствие из того факта, что нарушителю доступен открытый алгоритм шифрования. Действительно, он знает, что с = га mod п для известных значений с, е и п (хотя и не знает га).

Поэтому, если бы он мог разложить п на множители (раскрыв таким образом личный секретный ключ (р, q, е) законного получателя шифртекста с), то он мог бы получить и уз(п) = (р - 1)(д - 1), после чего, применив расширенный алгоритм Евклида, вычислить d, чтобы затем найти т = с" mod п. К счастью, неизвестно никакого алгоритма, с помош;ью которого можно было бы разложить на множители четырехсотзначное десятичное число за приемлемое время, и поэтому считается абсолютно надежным выбирать числа р и q длиной примерно в двести (десятичных) знаков. Выбирать р и g необходимо с особой тщательностью, чтобы при использовании известных алгоритмов факторизации не предоставить криптоаналитику никаких «зацепок». В частности, наибольший общий делитель чисел р - 1 и g - 1 должен быть небольшим, а оба они, как р - 1, так и g - 1, должны иметь большие простые делители. Блэкли и Борош предложили выбирать р и g так, чтобы и --, и Ц-- также были простыми

числами [47]. Для более широкого обсуждения подобных вопросов рекомендуем обратиться к [142]. Джон Гордон в [203] и Ули Маурер в [260] предлагают эффективные способы выбора таких подходящих (сильных) простых чисел. См. также [218].

Даже если считать, что факторизация действительно трудна, остается неизвестным, является ли столь же трудным само раскрытие RSA. Ведь вполне вероятно, что d может быть вычислено из открытой информации е и п вообще без разложения п на множители. Но возможно также и то, что значение d (а, стало быть, и значения множителей числа п) действительно трудно вычислить практически из е и п, даже если существует какой-то иной эффективный алгоритм раскрытия то из е, п и га mod п. Майклом Рабином в [297] и Хуго Уилльямсом в [360] были предложены другие криптосистемы с открытым ключом, для которых они доказали, что раскрытие в них открытого текста из всей доступной нарушителю информации оказывается таким же трудным, как и разложение на множители больших чисел. Однако эти криптосистемы сразу же раскрываются при атаке на основе выбранного шифртекста. Тем не менее теоретически существуют криптосистемы, которые являются вероятностно секретными при атаке на основе выбранного шифртекста [276]. Наконец, даже если m и в самом деле практически трудно вычисляется