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

Современная криптография - Венбо Мао

Венбо Мао Современная криптография. Под редакцией Клюшиной Д.А. — М. : Издательский дом Вильямс, 2005. — 768 c.
ISBN 5-8459-0847-7
Скачать (прямая ссылка): sovremennaya_kriptografiya.djvu
Предыдущая << 1 .. 114 115 116 117 118 119 < 120 > 121 122 123 124 125 126 .. 311 >> Следующая

Иначе говоря, факторизация исходного сообщения означает факторизацию соответствующего зашифрованного текста. Как правило, текст, зашифрованный с помощью алгоритма RSA, трудно разложить на простые множители из-за перемеривающего свойства функции шифрования, которое практически всегда приводит к тому, что размер зашифрованного текста равен размеру модуля. Однако из мультипликативного свойства следует, что если исходный текст поддается факторизации, то и зашифрованный текст — тоже. Это позволяет организовать атаку ['встреча посередине" ("meet-in-the-middle" attack). Рассмотрим следующий пример.
I Пример 83. Пусть с = me(modAr), причем Злоумышленнику известно число In < 2е. Существует ненулевая вероятность того, что число т является составным и удовлетворяет условию
(mi х m-if = т\ х m| = ci х c2(mod N).
(8.9.1)
(8.9.2)
,Из мультипликативного свойства функции RSA следует, что
с = т\- m|(mod N).
(8.9.3)
314
Часть III. Основные методы криптографии
Злоумышленник может создать упорядоченную базу данных
{le,22,3e,...)(2f)e}(modiV)
и искать в ней число c/ie(mod N), где г = 1,2,..., 2а. Согласно формулам (8.9.21 и (8.9.3) поиск сводится к проверке условия
c/ie=f (mod N)
и завершается за 2 2 шагов, при выполнении которых вычисляется величина ie(modN). Поскольку Злоумышленнику известны числа г и j, он восстанавли! вает число т = г ¦ j.
?
Оценим затраты Злоумышленника. Размер базы данных равен 2 2 log N бит., Временные затраты складываются из следующих компонентов: сложность созда! ния базы данных имеет порядок Ов(2г log3 N), сортировка — Ов(| 2г), а поиск
числа_7e(mod N) в упорядоченной базе — Ов(2г (~ + log Л7)). В последней оцен-J ке учитывается время, затраченное на возведение в степень по модулю и бинарный поиск (с помощью алгоритма 4.4). Итак, полная оценка временной сложности взлома имеет порядок Ов(22+1(| + log3 Л7)). Если Злоумышленнику доступна
?
память, имеющая размер 2 2 log N бит, то временная сложность взлома намно! го меньше 2е. Эта атака по временной сложности сравнима с атакой по метод,)! квадратного корня. о
Если размер исходного сообщения колеблется от 40 до 64 бит, то вероятность того, что исходный текст будет разложен на два одинаковых целых числа, изме-J няется от 18 до 50% [52].
Пример 8.4 (Реальный пример атаки 8.3). Представим себе сценарий, в кото-1 ром ключ алгоритма DES, состоящий из 56 бит, зашифрован с помощью 10241 битового ключа учебного варианта RSA. Если ключ алгоритма DES случаен, его] можно восстановить с ненулевой вероятностью, равной вероятности разложитн ключ DES на два целых множителя длиной по 28 бит. Для этого понадобится память, имеющая размер 238 бит (т.е. 32 гигабайт) и 229 операций возведения в степень по модулю. Этим условиям вполне соответствует хороший персональ-1 ный компьютер. В то же время непосредственный перебор ключей алгоритма DES требует выполнения 256 операций возведения в степень по модулю. Это требовав ние уже не под силу даже специализированному устройству. ?
Теперь понятно, почему не следует применять учебный вариант алгоритма' RSA для шифрования коротких ключей и паролей, длина которых не превышает 264 бит. Что же произойдет, если в конкретном приложении нам понадобитои
Глава 8. Шифрование — асимметричные методы
315
зашифровать с помощью алгоритма RSA небольшие числа, даже если размер сообщения равен одному биту? В этой ситуации следует применять методы шифрования, описанные в главе 15.
Следующий пример еще раз демонстрирует уязвимость учебного алгоритма RSA для атаки на основе подобранного открытого текста: против активной атаки этот алгоритм еще более беззащитен.
Пример 8.5. Допустим, что Злоумышленник частично контролирует блок шифрования, принадлежащий Алисе. Это условие вполне "разумно": если результат расшифровки зашифрованного текста, посланный Злоумышленником, окажется бессмысленным набором случайных цифр, Алиса должна вернуть Злоумышленнику исходный текст. "Разумность" этого условия объясняется двумя причинами.
1. "Случайный ответ на случайный запрос" — это вполне стандартный режим во многих криптографических протоколах, и, следовательно, пользователь должен выполнить определенную инструкцию "оклик-отзыв". Действительно, довольно часто криптографические протоколы допускают частичный контроль блока расшифровки со стороны пользователей. Например, протокол аутентификации с открытым ключом Нидхема-Шредера (протокол 2.5) функционирует именно так: Алиса обязана выполнить расшифровку зашифрованного текста, полученного от Боба.
2. В любом случае хочется надеяться, что расшифрованный текст, имеющий вид случайного набора цифр, не позволит атакующему извлечь какую-либо полезную информацию.
Предположим теперь, что Злоумышленник желает знать исходный текст, лежащий в основе зашифрованного текста с = me(mo6\N), перехваченного им в ходе предыдущего сеанса связи между Алисой и кем-либо еще (но не с ним!). Злоумышленник извлекает случайное число г 6 иЩ^, вычисляет зашифрованный текст с1 = rec(mod N) и посылает его Алисе. Результат расшифровки, выполненной Алисой, равен
Предыдущая << 1 .. 114 115 116 117 118 119 < 120 > 121 122 123 124 125 126 .. 311 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed