Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
8.17 Резюме
В главе рассмотрено несколько хорошо известных схем шифрования с помощью открытого ключа: протокол обмена ключами Диффи-Хеллмана, а также алгоритмы шифрования RSA, Рабина и Эль-Гамаля. Описаны задачи, неразрешимость которых обусловливает стойкость этих криптосистем.
330
Часть III. Основные методы криптографии
Стойкость, которая рассматривается в этой главе, основана на принципе "все или ничего", а атаки считаются пассивными. По этой причине все алгоритмы шифрования являются учебными и могут применяться в реальных приложениях только при условии, что все передаваемые данные являются абсолютно случайными, а злоумышленники не ведут себя агрессивно (т.е. не организовывают активных атак). Нестойкость учебных криптосистем, описанных в главе, продемонстрирована на примере разнообразных атак.
Выявлена необходимость более строгого понятия стойкости, которое было бы применимо к реальным криптосистемам. Однако эти системы будут описаны в части V. Читатели, не собирающиеся внимательно изучать часть V, должны тщательно разобрать все атаки, описанные в главе, особенно если они планируют использовать учебные криптосистемы.
Упражнения
8.1. Какими двумя замечательными свойствами обладают учебные криптографические алгоритмы?
8.2. Режим сцепления блоков (СВС) блочного шифра, описанный в разделе 7.8.2, имеет случайные входные данные, и, следовательно, любая утечка информации об исходном тексте исключена. Можно ли считать режим СВС учебным криптографическим алгоритмом? Почему?
8.3. Допустим, что Злоумышленник, организовавший атаку "человек посередине" на протокол обмена ключами Диффи-Хеллмана, только передает сообщения, которыми обмениваются Алиса и Боб (т.е. "человек посередине" не изменяет сообщения, а просто выполняет расшифровку и шифрование с помощью ключей, распределенных между Алисой и Бобом). Какой является эта атака: активной или пассивной?
8.4. В качестве общепринятой нижней границы для размера конечного поля Fq используется число |<7| = 1024, а в суэкспоненциальном выражении sub_exp(<7) (8.4.2) число с должно быть меньше двух. Докажите, что при этих условиях существует полиномиальный алгоритм дискретного логарифмирования в поле Fq, причем время работы полиномиального алгоритма решения ограничено полиномом девятой степени, зависящим от размера поля q.
8.5. Допустим, что группа {д) имеет несекретный порядок ord(g). Является ли трудноразрешимой следующая задача? По заданному числу дс найти числа да и дь, такие что ab = c(modord(g)), т.е. создать кортеж Диффи-Хеллмана (5,5а,5Ь,5с) по заданной паре (д,дс).
8.6. Как связаны между собой задача дискретного логарифмирования и вычислительная проблема Диффи-Хеллмана?
Глава 8. Шифрование — асимметричные методы
331
8.7. Почему в наборе параметров открытого ключа (e,N) криптосистемы RSA показатель степени е должен быть взаимно простым с числом $(АГ)?
8.8. Разложение нечетного составного целого числа на множители считается трудноразрешимой задачей. Является ли трудноразрешимой задача о факторизации степени простого числа? (Степенью простого числа называется число N — р1, где р — простое число, а г — целое число. Выполните разложение числа N на простые множители.)
Подсказка: сколько индексов г, где г > 1, необходимо перебрать для того, чтобы найти корень г-й степени числа АР?
8.9. Если число N является степенью простого числа, одним из методов вычисления корня г-й степени числа N является метод бинарного поиска. Разработайте бинарный алгоритм поиска для вычисления корня степени р\ где показатель г известен. Докажите эффективность этого алгоритма. Подсказка: рассмотрите алгоритм бинарного поиска простых чисел, состоящих из битов.
8.10. В криптосистеме RSA функция шифрования является перестановкой в мультипликативной группе по модулю RSA. По этой причине функция RSA называется однонаправленной функцией перестановки с секретом. Является ли функция шифрования в криптосистеме Рабина (Эль-Гамаля) однонаправленной функцией перестановки с секретом?
8.11. Допустим, что N « 21024, а элементы из группы Z*N извлекаются случайным образом. Какова вероятность того, что выборочное значение будет меньше, чем 264? Используя этот результат, докажите, что в алгоритмах шифрования RSA, Рабина и Эль-Гамаля 64-битовый случайный пароль не должен считаться случайным исходным текстом.
8.12. При каких условиях функцию шифрования в криптосистеме Эль-Гамаля можно считать детерминированным алгоритмом?
8.13. Опишите атаки CPA, CCA и ССА2.
8.14. При описании стойкости криптосистем RSA и Рабина к атаке CPA использовался принцип "все или ничего" (теоремы 8.1 и 8.2.1 соответственно). Зачем это нужно?
8.15. Почему любой алгоритм шифрования в криптосистемах с открытым ключом (даже учебный) должен быть устойчивым к атаке CPA?
8.16. Назовите основную причину уязвимости учебных криптографических алгоритмов для активных атак.
8.17. Что такое услуги оракула? Необходимы ли атакующему услуги оракула для расшифровки сообщений в криптосистеме с открытым ключом?
332
Часть III. Основные методы криптографии
