Научная литература
booksshare.net -> Добавить материал -> Математика -> Коблиц Н. -> "Курс теории чисел и криптографии" -> 50

Курс теории чисел и криптографии - Коблиц Н.

Коблиц Н. Курс теории чисел и криптографии — Москва: Научное изд-во ТВП, 2001. — 254 c.
Скачать (прямая ссылка): theory-chisel-kriptographii.djvu
Предыдущая << 1 .. 44 45 46 47 48 49 < 50 > 51 52 53 54 55 56 .. 125 >> Следующая


Замечания. 1. При выборе р и q пользователь А должен позаботиться о выполнении ряда условий. Самые важные из них следующие: эти простые числа не должны быть слишком близки друг к другу (например, одно должно быть на несколько десятичных разрядов длиннее другого), числа р—1 и q—1 должны иметь очень маленький наибольший общий делитель и каждое из них должно иметь хотя бы один большой простой делитель. Некоторые причины появления таких условий указаны в последующих упражнениях. Разумеется, если

104

ГЛ. IV. ОТКРЫТЫЙ ключ

будет изобретен метод факторизации, который быстро находит ответ при некоторых ограничениях на р и q, то будущим пользователям RSA придется накладывать на выбор р и q дополнительные условия.

2. В §1.3 мы видели, что, когда п является произведением двух простых чисел р и q, знание ц>(п) эквивалентно знанию разложения. Предположим теперь, что мы решили вскрыть систему RSA посредством нахождения такого натурального d, что aed = a (mod п) для всех а, взаимно простых с га. Это эквивалентно тому, что ed—1 кратно наименьшему общему кратному чисел р — 1 и q — 1. Знание т = ed — 1 несет в себе меньше информации, чем точное знание <р(п). Однако сейчас мы приведем процедуру, позволяющую по та с большой вероятностью разложить га.

Итак, предположим, что даны целое число га, которое является произведением двух неизвестных простых чисел, и такое целое число та, что ат = 1 (mod га) для всех а, взаимно простых с п. Заметим, что такое та обязательно четно (в чем можно убедиться, взяв а = -1). Сначала проверим, обладает ли тем же самым свойством число та/2, в случае чего можно заменить т на т/2. Если a™ ^2 не сравнимо с 1 по

модулю п для некоторых а, взаимно простых с га, то а171*"2 ф 1 (mod га), по крайней мере, для половины элементов множества (Z/raZ)* (это доказывается точно так же, как пункт а) упражнения 21 к § П. 2). Таким образом, если мы выберем случайно несколько дюжин значений а и обнаружим, что во всех этих случаях ат/'2 = 1 (mod п), то можно с большой надежностью считать, что это сравнение выполнено для всех а, взаимно простых с га, и можно снова заменить та на та/2. Эта процедура повторяется до тех пор, пока сравнение не перестанет выполняться. Тогда имеется две возможности.

1) та/2 кратно одному из чисел р - 1 или q — 1 (скажем, р — 1), но не обоим. В этом случае ат^2 всегда сравнимо с 1 по модулю р и точно в половине случаев сравнимо по модулю g с -1, а не с 1.

2) т/2 не кратно ни одному из чисел р — 1 и q — 1.B этом слу-

m/2 1 /

чае а сравнимо с 1 как по модулю р, так и по модулю q (а значит, и по модулю га) ровно в 25% случаев, сравнимо с -1 как по модулю р, так и по модулю q ровно в 25% случаев, а в остальных 50% случаев выбора а оно сравнимо с 1 по одному модулю и с —1 по другому.

Таким образом, случайно выбирая значения а, мы с большой ве-роятностью быстро найдем такое а, при котором а — 1 делится только на одно из наших двух простых чисел (скажем, р). (Случайно выбранное а с вероятностью 50% удовлетворяет этому условию.) Как только такое а найдено, мы сразу можем разложить п, так как НОД (п,ат/2 -1) = р.

§ 2. КРИПТОСИСТЕМА RSA

105

Приведенная процедура дает пример вероятностного алгоритма. Мы еще встретимся с вероятностными алгоритмами в следующей главе.

3. Как послать подпись в системе RSA? При обсуждении проблемы аутентикации в предыдущем разделе мы предполагали для простоты, что V = C Для системы RSA ситуация немного сложнее. Существует способ, который позволяет избежать сложностей с неодинаковостью чисел пА и размеров блоков (число букв к в элементе открытого текста меньше числа букв / в элементе шифртекста). Предположим, как и в предыдущем разделе, что Алиса посылает свою подпись (некоторый открытый текст P) Бобу. Ей известны ключ шифрования Боба КЕВ = (пв,ев) и собственный ключ дешифрования Kp1a = (па,^а). Она должна послать /в/д^-Р), если пА < пв, и Ia1 Ib(P), если пА > пв. В первом случае она берет наименьший положительный вычет P А по модулю пА, затем, приведя это число по модулю пв, она вычисляет (pdA (mod пА))ев (mod пв), что и посылает в качестве элемента шифртекста. Если пА > пв, то она сначала вычисляет Рев (mod пв) и потом возводит это выражение в степень dA по модулю пА. Ясно, что Боб, чтобы проверить подлинность сообщения, в первом случае использует возведение в степень dg по модулю пв, а потом в степень еА по модулю пА. Во втором случае эти операции применяются в обратном порядке.

УПРАЖНЕНИЯ

1. Пусть для открытых и шифрованных текстов во всех случаях используется 40-буквенный алфавит с числовыми эквивалентами 0-25 для A-Z, пробел =26, . = 27, ? = 28, $ = 29 и с числовыми эквивалентами 30-39 для цифр 0-9. Пусть элементами открытого текста являются биграммы, а шифртекста — триграммы (т. е. k = 2, / = 3, 402 < пА < 403 для всех пА).

а) Послать сообщение «SEND $7500» пользователю с ключом шифрования (пА, еА) = (2047, 179).

б) Вскрыть код, разложив пА на множители и вычислив затем ключ дешифрования (nA,dA).

в) Объяснить, почему аналитик может сравнительно быстро определить ключ дешифрования, не прибегая к факторизации пА. Другими словами, почему число 2047, помимо своего малого размера, является очень плохим вариантом для пА1
Предыдущая << 1 .. 44 45 46 47 48 49 < 50 > 51 52 53 54 55 56 .. 125 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed