Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
14.8. Курсы обучения криптоанализу (помощь при шифровании и расшифровке) — весьма эффективное средство, позволяющее Злоумышленнику взламывать все учебные криптографические алгоритмы. Почему Злоумышленник, как правило, имеет доступ к этой услуге?
14.9. Что такое стойкость к атаке IND-CCA2? Какие атаки относятся к этой разновидности?
14.10. В чем заключается важность эквивалентности понятий стойкости к атакам IND-CCA2 и NM-CCA2?
Подсказка: опишите трудности, с которыми сопряжено применение понятия стойкости к атакам NM.
14.11. Предположим, что в ходе атаки пополуночи (протокол 14.4) Злоумышленник только посылает зашифрованные тексты, созданные с помощью заранее заданной схемы шифрования. Покажите, что в этом случае атака пополуночи вырождается в атаку во время ленча. Почему эта атака не вырождается в атаку IND-CPA?
Глава 15
Доказуемо стойкие и эффективные криптосистемы
с открытым ключом
15.1 Введение
В предьщущей главе показано, что первые решения задачи о стойкости криптосистем с открытым ключом к атаке IND-CCA2 (соответственно NM-CCA2) основывались на неинтерактивных доказательствах с нулевым разглашением (NIZK). Такие доказательства демонстрируют получателю зашифрованного текста, что его автору уже известен соответствующий открытый текст, поскольку он в состоянии доказать утверждение о своем NP-членстве1.
"Зашифрованный текст с принадлежит языку L, определенному алгоритмом шифрования ? при открытом ключе рк, а его автор обладает вспомогательной информацией (т.е. свидетельством NP-задачи), позволяющей доказать его членство."
Здесь под "вспомогательной информацией" ("auxiliary input"), позволяющей? доказать членство автора, понимается соответствующий зашифрованный тексте и случайное число, поступающее на вход алгоритма шифрования ?. (Случай-, ное число необходимо для обеспечения семантической стойкости схемы шиф-| рования.) Если верификация доказательства завершается успешно, получатель^ который вольно или невольно предоставляет услуги по расшифровке сообщений^ может быть уверен, что даже если автором зашифрованного текста с являете^ Злоумышленник, возвращение ему соответствующего открытого текста не доба-| вит ничего нового к тому, что он уже знает. Следовательно, такая помощь в расы шифровке не повышает вероятность взлома криптосистемы.
Эта идея вполне разумная, но слишком дорогостоящая. Общепринятый метод неинтерактивного доказательства с нулевым разглашением заключается в том, что]
'Взаимосвязи между утверждением об NP-членстве и доказательством с нулевым разглашением изучаются в главе 18.
Глава 15. Доказуемо стойкие и эффективные криптосистемы.
555
доказывающая сторона (автор зашифрованного текста) и проверяющая сторона (получатель сообщения) владеют общей случайной строкой, вызывающей обоюдное доверие (mutually trusted). Это требование намного жестче, чем необходимо. Поскольку основным достоинством криптосистем с открытым ключом является тот факт, что двум сторонам не обязательно разделять между собой секретную информацию перед началом безопасных переговоров, доказуемая стойкость схем шифрования с открытым ключом не должна аннулировать этот преимущество!2
Доказуемая стойкость должна означать лишь, что Злоумышленник не может взламывать систему слишком быстро или слишком часто. Таким образом, доказуемая стойкость следует из оценок вероятности и вычислительной сложности взлома. В контексте доказуемой стойкости требование гарантий, что Злоумышленнику должен быть известен соответствующий открытый текст, является завышенным, а доказательство NIZK — излишним и чрезмерным. Фактически ни одна из предыдущих схем шифрования с открытым ключом, обладающих свойством доказуемой стойкости к атаке IND-CCA2 и основанных на доказательстве NIZK, не является достаточно эффективной для практического применения.
Существует множество практически эффективных и доказуемо стойких схем шифрования с открытым ключом и схем цифровой подписи. Как правило, эти схемы основаны на учебных прототипах и используют механизм проверки целостности данных. Здесь под учебными прототипами подразумеваются алгоритмы с открытым ключом, использующие однонаправленные функции с секретом, например, функции RSA, Рабина и Эль-Гамаля (раздел 8.14). Механизм проверки целостности данных позволяет установить вероятность и вычислительную сложность взлома схемы шифрования.
Стоимость схемы шифрования, усиленной таким образом, ненамного превышает стоимость ее учебного прототипа.
15.1.1 Структурная схема главы
В главе описываются две эффективные схемы шифрования с открытым ключом, обладающие свойством доказуемой стойкости к атаке IND-CCA2 — схема оптимального асимметричного шифрования с заполнением (Optimal Asymmetric Encryption Padding — ОАЕР) [24, 114, 270] (раздел 15.2) и криптосистема с открытым ключом Крамера-Шоупа (Cramer-Shoup public-key cryptosystem) [84] (раздел 15.3). Затем приводится обзор семейства так называемых гибридных криптосистем (hybrid cryptosystem), представляющих собой комбинацию алгоритмов шифрования с открытым и секретным ключами. Показано, что они являются эффективными и обладают свойством доказуемой стойкости к атаке IND-CCA2
