Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
Таким образом, суммируя все сказанное, каждый пользователь криптосистемы RSA должен совершенно случайно и раз и навсегда выбрать для себя подходящие целые числа р, q и е и вычислить с их помощью d. После чего он должен сделать свой открытый ключ (е,п) доступным в пользовательском справочнике, но при этом сохранять d в секрете. Это дает возможность остальным пользователям зашифровывать Посылаемые ему сообщения, которые только он один потом сможет расшифровать. Для того чтобы эта идея могла быть реализована на практи-
56 Системы с открытым ключом
Глава 4
ке, решающим является удовлетворение требования, чтобы генерация больших случайных простых чисел и вычисление d были легкоосуществимы. К счастью, проверка чисел на простоту оказывается действительно легче их разложения на множители, благодаря вероятностным алгоритмам Роберта Соловея и Вол-кера Штрассена [339] и Майкла Рабина [298]. Проверке чисел на простоту посвящено несколько интересных работ, в частности, [289, 233, 271]. По поводу тесно связанного с криптографией вопроса о генерации подходящих простых чисел (но не их проверки на простоту) обращайтесь к [125, 16, 260]. Относительно описания расширенного алгоритма Евклида для вычисления d смотрите [7, 142] (но если же вы предпочитаете переоткрыть расширенный алгоритм Евклида самостоятельно, то можете найти полезными те указания, которые даны к задаче 8.5.12Ь из [77]).
В качестве небольшого примера, пусть р = 19 и q — 23, так что п = 437, а <р(п) = 396. Пусть также е = 13, а значит d = 61, поскольку 13 • 61 = 793 = 2<р(п) + 1. Тогда сообщение открытого текста m = 123 будет зашифровано как с = 12313 mod 437 = 386. Действительно, 38661 mod 437=123.
Особо отметим ситуацию, когда криптоаналитик, перехвативший шифртекст c=Ffc(m), посланный известному пользователю, знает естественный алгоритм шифрования Е^, который используется отправителем для вычисления с. Такое предположение имеет два важных следствия. Если бы нарушитель мог в точности угадать открытый текст сообщения ш, то он был бы в состоянии точно так же, как и отправитель, вычислить Ffc(m), а затем проверить свою догадку, сравнив полученный результат с шифртекстом с. -Учитывая возможность исчерпывающего поиска, такая угроза является довольно опасной, если число возможных открытых текстов сравнительно невелико. Если же добавлять в короткие сообщения случайные биты, то эта трудность может быть до некоторой степени разрешена, однако, более приемлемым решением несомненно является использование вероятностного шифрования (см. § 6). При желании можете обратиться также к [308].
Более существенным для криптосистемы RSA является другое следствие из того факта, что нарушителю доступен открытый алгоритм шифрования. Действительно, он знает, что с = те mod п для известных значений с, е и п (хотя и не знает тп).
Криптосистема RSA 57
Поэтому, если бы он мог разложить п на множители (раскрыв таким образом личный секретный ключ (р, q, е) законного получателя шифртекста с), то он мог бы получить и = (р—1)(^ — 1),
после чего, применив расширенный алгоритм Евклида, вычислить d, чтобы затем найти т = cd mod п. К счастью, неизвестно никакого алгоритма, с помощью которого можно было бы разложить на множители четырехсотзначное десятичное число за приемлемое время, и поэтому считается абсолютно надежным выбирать числа р и q длиной примерно в двести (десятичных) знаков. Выбирать р и q необходимо с особой тщательностью, чтобы при использовании известных алгоритмов факторизации не предоставить криптоаналитику никаких «зацепок». В частности, наибольший общий делитель чисел р — 1 и q — 1 должен быть небольшим, а оба они, как р — 1, так и q — 1, должны иметь большие простые делители. Блэкли и Борош предложили вы-
р — 1 q — 1
бирать р и q так, чтобы и —-—, и —-— также были простыми
числами [47]. Для более широкого обсуждения подобных вопросов рекомендуем обратиться к [142]. Джон Гордон в [203] и Ули Маурер в [260] предлагают эффективные способы выбора таких подходящих (сильных) простых чисел. См. также [218].
Даже если считать, что факторизация действительно трудна, остается неизвестным, является ли столь же трудным само раскрытие RSA. Ведь вполне вероятно, что d может быть вычислено из открытой информации ей п вообще без разложения п на множители. Но возможно также и то, что значение d (а, стало быть, и значения множителей числа п) действительно трудно вычислить практически из.еип, даже если существует какой-то иной эффективный алгоритм раскрытия т из е, п и те mod п. Майклом Рабином в [297] и Хуго Уилльямсом в [360] были предложены другие криптосистемы с открытым ключом, для которых они доказали, что раскрытие в них открытого текста из всей доступной нарушителю информации оказывается таким же трудным, как и разложение на множители больших чисел. Однако эти криптосистемы сразу же раскрываются при атаке на основе выбранного шифртекста. Тем не менее теоретически существуют криптосистемы, которые являются вероятностно секретными при атаке на основе выбранного шифртекста [276]. Наконец, даже если шив самом деле практически трудно вычисляется
