Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Схемы цифровой подписи из второго семейства конструируются с помощью последовательной комбинации рандомизированных заполнений путем однонаправленных перестановок с секретом. Редукционное доказательство их стойкости
Глава 16. Сильная и доказуемая стойкость схем цифровой подписи 631
аналогично редукционному доказательству стойкости схем шифрования с открытым ключом, использующих рандомизированные заполнения с помощью однонаправленных перестановок с секретом, изученных в предыдущей главе. Несмотря на это, успешная атака (фальсификация подписи с помощью атаки на основе адаптивно подобранных сообщений) может привести к полному инвертированию однонаправленной функции. Таким образом, редукционное доказательство стойкости схем цифровой подписи с рандомизированным заполнением является строгим, т.е. способность атакующего алгоритма подделать подпись может быть полностью сведена к инвертированию одной из необратимых функций (т.е. соответствующей однонаправленной функции с секретом). Такое свойство называется точной стойкостью.
В заключительной части главы рассмотрены схемы зашифрованной подписи, представляющие собой эффективные и полезные криптографические примитивы. Аналогично другим схемам шифрования и цифровой подписи, рассмотренным в книге, схемы зашифрованной подписи используют две распространенные криптографические задачи: вычисление дискретного логарифма и факторизацию целого числа.
Упражнения
16.1. Что представляет собой "прикладная" стойкость цифровой подписи?
16.2. Если Злоумышленник — нехороший человек, почему мы должны позволять ему получать подписи на сообщениях по его выбору без всяких ограничений?
16.3. При доказательстве стойкости тройной схемы Эль-Гамаля в лемме о ветвящихся ответах Саймон дважды выполняет алгоритм Злоумышленника и на одно и то же множество запросов случайному оракулу возвращает два разных множества ответов. Следует ли считать, что Саймон таким образом обманывает Злоумышленника?
16.4. Обсудите полезность понятия экзистенциальной подделки тройной подписи Эль-Гамаля при доказательстве стойкости этой схемы.
16.5. Предположим, что алгоритм PSS подписывает одно и то же сообщение дважды. Какова вероятность, что он создаст одну и ту же подпись?
16.6. В упражнении 15.2 мы ввели понятие полосы пропускания схемы шифрования. Аналогичное понятие можно ввести для схемы цифровой подписи. Предположим, что мы выбрали те же самые параметры безопасности, что и в упражнении 15.2. Какова полоса пропускания в универсальной схеме заполнения с помошью алгоритма RSA (алгоритм 16.2) 1) при подписании; 2) при шифровании?
632
Часть V. Методы формального доказательства стойкости
16.7. Почему две полосы пропускания, описанные в предыдущей задаче, отличаются друг от друга?
16.8. Обсудите различия между невозможностью отказа от авторства в схеме цифровой подписи Женя и в схеме зашифрованной подписи TBOS.
16.9. Аргументы, приведенные в пользу стойкости схемы зашифрованной подписи TBOS (в разделе 16.5.2.2), являются убедительными, но не строгими. Почему?
Подсказка: являются ли эти аргументы редукционными?
Глава 17
Формальные методы анализа протоколов аутентификации
17.1 Введение
В главе 11 показано, что протоколы аутентификации и протоколы согласования аутентифицированных ключей (в этой главе обе разновидности часто называются протоколами аутентификации) весьма уязвимы. Причем дефекты этих протоколов могут быть скрыты. Как создать действительно стойкие протоколы аутентификации? Эта тема находится в центре внимания многих исследователей. Некоторые из этих ученых являются криптографами и математиками, другие — специалистами по компьютерным наукам. В среде этих исследователей стало общепризнанным, что для анализа протоколов аутентификации необходимо развивать формальные подходы.
Формальные методы являются естественным продолжением неформальных. Формальными могут быть методологические, механические и логические понятия. Как правило, для моделирования поведения системы с помощью логических и математических средств формальный метод использует язык символов. Иногда формальный метод представляет собой экспертную систему, имитирующую поведение людей и даже пытающуюся моделировать человеческое мышление. Общим для всех этих методов является систематический, а иногда даже исчерпывающий подход к проблеме. Следовательно, формальные методы весьма полезны для анализа сложных систем.
В области формального анализа протоколов аутентификации различаются два подхода. Один из них использует формальные рассуждения о некоторых полезных свойствах, например, стойкости, а другой направлен на поиск нежелательных и опасных дефектов.
В рамках первого подхода анализируемый протокол должен выбираться или разрабатываться весьма тщательно. Анализ должен показать, что выбранный протокол действительно соответствует предъявляемым требованиям, которые также должны быть строго формализованы. Методы формального доказательства часто приспособлены для конкретного протокола и предполагают широкомасштабное
634
Часть V. Методы формального доказательства стойкости
