Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Четвертый ответ: 1 => те (48/8+15/16,15/2) = (105/16,15/2), т.е. те [7,7].
Итак, т = 7. Действительно, исходным сообщением является число 7: 73 = = 13(mod 15). о
Из теоремы 9.1 следует, что младший значащий бит в исходном тексте, зашифрованном алгоритмом RSA, найти так же сложно, как и целый блок исходного сообщения.
Пример 8.5 демонстрирует опасность, возникающую, когда пользователь, владеющий открытым ключом алгоритма RSA, предоставляет услуги оракула расшифровки и возвращает в ответ на запрос целый блок исходного текста. Стойкость младшего значащего бита в алгоритме RSA означает, что пользователь не должен
338
Часть III. Основные методы криптографии
играть роль ни оракула четности, ни iV/2-оракула (как в лемме 9.1), т.е. не отвечать на шифрованные запросы о бите четности исходного текста и не сообщать, превышает сообщение тп число N/2 или нет.
Следует предупредить, что атакующий может маскировать свои запросы под видом невинного протокола. Рассмотрим следующий пример.
Пример 9.2. Если Алиса и Злоумышленник согласились разделить секретный сеансовый ключ только между собой, то Злоумышленник может сделать следующее вполне разумное предложение.
"Алиса, что если мы пошлем друг другу 1 ООО сообщений, зашифрованных нашим открытыми ключами? Пусть сеансовый ключ будет строкой битов, представляющей собой результат применения операции XOR к битам четности из каждой пары исходных сообщений. Кстати, для того, чтобы убедиться, что сеансовый ключ является случайным, позволь мне послать свои 1 ООО блоков первым!"
Алиса не только согласна, но и очень благодарна Злоумышленнику за ока-' занное ей высокое доверие (сгенерировать случайный сеансовый ключ!) Однако Злоумышленник посылает ей 1000 зашифрованных сообщений, имеющих вид (2l)ec(mod АГ) (г = 1,2,..., 1 ООО), где с — шифрованный текст, когда-то посланный Алисой и перехваченный Злоумышленником.
Выполнив протокол, Злоумышленник заявляет об ошибке при вычислении сеансового ключа.
"Алиса, мне очень жаль, но я запутался в своих вычислениях. Не могла бы ты переслать мне сеансовый ключ? Пожалуйста, зашифруй его моим открытым ключом."
Бедная Алиса спешит на помощь. Увы, имея сеансовый ключ, Злоумышленник, может восстановить бит четности и применить алгоритм 9.1 для взлома исходного текста, содержащегося в зашифрованном тексте с! ?
В данном случае Злоумышленник организовал активную атаку: он модифици-1 рует зашифрованный текст с, умножая его на число (2l)e(mod АГ). Следовательно, несмотря на то, что восстановить младший значащий бит так же сложно, как и весь блок, функция шифрования в алгоритме RSA остается безнадежно уязвимой для активной атаки.
9.3 Битовая стойкость алгоритма Рабина
Если шифрование имеет вид с = m2(modAT) (т.е. показателем степени прщ шифровании является число е = 2), алгоритм 9.1 можно легко модифицировать и применить к схеме Рабина.
Глава 9. Идеальный мир: битовая стойкость.
339
Однако существуют некоторые сложности. Если число N имеет два разных простых множителя, то по теореме 6.17 (раздел 6.6.2) любое число с € QR^ име-I ет четыре разных квадратных корня по модулю N, т.е. зашифрованному тексту с I соответствуют четыре разных исходных текста. Оракул четности, проверяющий | четность случайного квадратного корня числа с (т.е. корня, случайно выбранно-I го из четырех), является ненадежным. Несмотря на это, если квадратный корень I обладает определенными свойствами, обеспечивающими детерминированность I (а значит, и надежность) оракула четности, то к схеме Рабина также можно при-I менять алгоритм бинарного поиска.
Например, оракул будет детерминированным, если он проверяет бит четности меньшего из квадратных корней положительного символа Якоби. По теореме 6.18 I (раздел 6.7), если число N является целым числом Блюма, то любой квадратич-I ный вычет с имеет два корня т и —т, являющихся корнями положительного I символа Якоби. Поскольку число N — нечетное, только один из этих двух кор-[ ней меньше N/2. Его можно назвать "меньшим из корней числа с, являющихся корнями положительного символа Якоби".
Предположим, что целое число Блюма N удовлетворяет условию (^) = 1, где | N — pq, причем р=g(mod 8). Тогда оракул четности, проверяющий бит четности меньшего из квадратных корней положительного символа Якоби, вполне работоспособен. Заметим, что при условии (^) = 1 в ответ на г-й запрос надежный оракул четности вернет исходный текст Щ (mod N) и определит знак символа Якоби для всех г запросов об исходном тексте. Детали модифицированного алгоритма бинарного поиска в схеме Рабина приведены в работе [128].
I 9.3.1 Генератор псевдослучайных битов Блюма-Блюма-Шаба
Применение алгоритма бинарного поиска к функции шифрования Рабина было основано на предположении, что младший значащий бит исходного сообщения в схеме Рабина является стойким, если выполняются условия неразрешимости задачи о разложении целого числа на простые множители (предположение 8.4 из раздела 8.8). Стойкость младшего значащего бита в схеме Рабина имеет важное практическое применение: она используется при генерировании криптографи-1 чески стойких псевдослучайных битов (cryptographically strong pseudo-random bits — CSPRB) [42]. Так называемый генератор псевдослучайных чисел Блюма-Блюма-Шаба (Blum-Blum-Shub pseudo-random number generator — BBS) использует в качестве начального значения число xq ? QRW, где N — fc-битовое целое число Блюма. Затем псевдослучайные биты, сгенерированные датчиком BBS с помощью начального значения xq, образуются из младших значащих битов каждого
