Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
15.11. Предположим, что криптосистема Крамера-Шоупа модифицирована следующим образом:
е <— hT + m.
Таким образом, расшифровка выполняется путем вычитания, а остальные части остаются без изменения. Докажите, что модифицированная схема является стойкой к атаке ССА2, т.е. любую активную атаку можно распознать. Является ли эта схема стойкой к атаке IND-CCA2?
15.12. Почему стоимость вычисления величины gfhP (mod р) сравнима со стоимостью одной операции возведения в степень?
15.13. Распространите алгоритм 15.2 на случай fxgyhz(modp).
15.14. Опишите гибридную криптосистему.
15.15. В приложениях длина секретных данных намного больше размера параметра безопасности в криптосистемах с огкрытым ключом, а в симметричных схемах шифрования — намного меньше. Какие алгоритмы шифрования следует применить при передаче таких данных: 1) RSA; 2) AES; 3) RSA-OAEP; 4) Эль-Гамаля; 5) Крамера-Шоупа или 6) гибридную криптосистему?
Глава 16
Сильная и доказуемая стойкость схем цифровой
подписи
16.1 Введение
В определение схемы цифровой подписи (определение 10.2 из раздела 10.4) входит условие Verifypfc(m, s) = False с "огромной" вероятностью, если пара (m, s) является подделкой, созданной без применения предписанной процедуры. Однако мы не уточнили, насколько высокой должна быть эта вероятность. Кроме того, как указано в разделе 10.4.9, учебное понятие стойкости схем цифровой подписи (т.е. сложность создания подделки "с нуля") является слишком слабым, чтобы получить применение на практике. Следовательно, аргументы, приведенные в главе 10, носят слишком неформальный характер. Это объяснялось тем, что в тот момент мы еще не обладали достаточными знаниями, позволяющими провести формальное и строгое доказательство стойкости.
В двух предшествующих главах изложена методика формального доказательства стойкости схем шифрования с открытым ключом, в том числе доказательство сильной стойкости (например, IND-CCA2), описаны метод "сведения к противоречию", модель случайного оракула и стандартная модель доказательства стойкости. Эти понятия образуют фундамент для формального анализа стойкости схем цифровой подписи. Как и при исследовании стойкости схем шифрования с открытым ключом, при изучении схем цифровой подписи необходимо исследовать два аспекта.
• Трудность подделки подписи в ходе наиболее распространенных атак' на схемы цифровой подписи. Наиболее распространенной атакой на cxe-i мы цифровой подписи является атака на основе адаптивно подобранных сообщений (adaptive chosen-message attack). Адаптивный алгоритм атаки< обладает открытым ключом объекта атаки и заставляет пользователя играть роль оракула подписи (oracle signing service) для любого заранее подо-, бранного сообщения. Такой алгоритм способен адаптировать свои запросы
Глава 16. Сильная и доказуемая стойкость схем цифровой подписи
601
в соответствии с собранными парами сообщение-подпись. Можно считать, что в ходе адаптивной атаки атакующий алгоритм проходит курс обучения подделке подписи. Задачей атакующего, пославшего достаточно большое количество адаптивно подобранных сообщений и получившего в ответ соответствующие подписи, является создание новой пары сообщение-подпись, согласованной с открытым ключом пользователя. Здесь слово "новое" означает сообщение, которое никогда ранее не подписывалось пользователем.
• Формальное доказательство стойкости. Это доказательство основано на методе "сведения к противоречию". Оно представляет собой эффективное преобразование, демонстрирующее, что любой успешный алгоритм подделки (например, в результате адаптивной атаки) сводится к решению трудноразрешимой задачи из теории вычислительной сложности. "Противоречие" основано на широко распространенном убеждении, что не существует эффективных алгоритмов решения трудноразрешимых задач. Голдвассер, Микали и Ривест систематически исследовали эти аспекты в своей знаменитой работе [127]. Они реализовали схему цифровой подписи и доказали ее неуязвимость к атаке на основе адаптивно подобранных сообщений. В этой схеме используется понятие "расцепленных" перестановок ("claw-free permutation"): две перестановки /о и Д, определенные на одной и той же области, называются расцепленными, если невозможно найти тройку (ж, у, z), такую что /о(х) = fi(y) = z. Голдвассер и его соавторы реализовали такие перестановки с помощью задачи факторизации целого числа. Эта схема позволяет подписать любую случайную строку без добавления распознаваемой избыточности, т.е. без применения функций хэширования при форматировании сообщения. Однако эта схема носит побитовый характер и, следовательно, не является идеальной для приложений. И все же работа Голдвассера и его коллег [127] заложила основы теории сильной (т.е. пригодной для приложений) стойкости схем цифровой подписи.
16.1.1 Структурная схема главы
В разделе 16.2 вводится понятие сильной стойкости схемы цифровой подписи. Раздел 16.3 посвящен редукционному доказательству стойкости схемы цифровой подписи Эль-Гамаля. В разделе 16.4 описываются прикладные схемы цифровоГ: подписи, основанные на методе рандомизированого заполнения и однонаправленных перестановках с секретом (в основном, функции RSA и Рабина). В разделе 16.5 изучаются схемы шифрования подписи и их сильная стойкость.
