Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Напомним, что число п является полиномиально ограниченным, так что величина 1/v/J^ не является пренебрежимо малой. Иначе говоря, Саймон получает
Глава 16. Сильная и доказуемая стойкость схем цифровой подписи
609
две поддельные корректные подписи (г, е, s) и (г', е7, s') со значимой вероятностью 1/у/п. Кроме того, поскольку во втором сеансе Саймон порождает другие равномерно распределенные ответы, условие е' ф e(mod q) должно выполняться с огромной вероятностью 1 — 2_fc.
При успешном разветвлении Саймон способен вычислить дискретный логарифм. Посмотрим, как он это делает.
Вычисление дискретного логарифма
Получив две корректные подделки, Саймон может вычислить следующие величины.
yrrs = де (mod р), yrrs' = <7e'(modp).
Поскольку д — порождающий элемент по модулю р, для некоторого целого числа ? < р — 1 выполняется условие г = j/(modp). Кроме того, у = ^(modp). Следовательно,
xr + ?s = e(mod(j), xr + is' — e'(modg).
Поскольку из условия е' ф e(modg) следует, что s' ф s(modg), выполняется равенство
е-е' ? =-j(mod<7).
В заключение, если q \ г, редукция оказывается невозможной. Это условие делает возможной атаку Блайхенбахера [41] на схему цифровой подписи Эль-Гамаля (см. раздел 10.4.7.1). Однако, поскольку атака Блайхенбахера возможна лишь при злонамеренном выборе параметров открытого ключа, при случайном выборе открытого ключа вероятность события q | г равна 1/q и является пренебрежимо малой. Следовательно, не стоит опасаться, что Злоумышленник успешно подделает подписи (M,?q,H(M,?q),s) при некотором целом числе ?, поскольку это событие имеет пренебрежимо малую вероятность. Таким образом, с огромной вероятностью числа г wq являются взаимно простыми, и Саймон может вычислить значение x(mod q) по формуле
х = -——(mod*/).
Напомним, что число (р — V)/q не имеет больших простых множителей, т.е. величина x(modp — 1) вычисляется достаточно легко.
610
Часть V. Методы формального доказательства стойкости
Поскольку числа г, е и е' содержатся в двух списках Саймона, а числа s и s' являются результатом вычислений, выполненных Злоумышленником, Саймон действительно может применить описанный выше метод для вычисления дискретного логарифма числа у с базой д по модулю р. В этом методе Саймон использует Злоумышленника как "черный ящик": его не интересует технология, которую применяет Злоумышленник — ему нужен лишь результат.
Результат редукции
Итак, получены следующие результаты редукции.
1. Преимущество, с которым Саймон вычисляет дискретный логарифм, равно
Adv'(fc)»
поскольку число qn полиномиально ограничено, а величина Adv'(/c) является значимой.
2. Время работы Саймона оценивается как
2(t + gH) ~ Adv(fc) '
где число t обозначает время, потраченное Злоумышленником на подделку подписи. Эффективность этого алгоритма редукции обсуждается в разделе 16.3.2.3.
Теоретической основой редукционного доказательства, использующего модель случайного оракула, является лемма о ветвлении (forking lemma) [235].
Примечание 16.1. Метод ветвления работоспособен, поскольку Саймон-имитатор повторно генерирует ответы случайного оракула, так что одному и тому же множеству вопросов, заданных Злоумышленником, соответствуют два совершенно разных множества ответов. Это выглядит так, будто Злоумышленник слишком глуп и не способен понять, что на один и тот же вопрос он получает два разных ответа. В то же время Злоумышленник достаточно умен, чтобы подделать цифровую подпись. Следует иметь в виду, что Злоумышленник — это вероятностный алгоритм, единственным предназначением которого является создание корректных поддельных подписей, если его окружение является корректным, а ответы случайного оракула имеют правильное распределение. Мы не должны считать, что вероятностный алгоритм имеет дополнительные функциональные возможности, т.е. обладает человеческим сознанием и понимает, когда его дурачат. Фактически, возвращая Злоумышленнику правильно распределенные ответы, Саймон вовсе не дурачит его. ?
Глава 16. Сильная и доказуемая стойкость схем цифровой подписи
611
16.3.2.2 Стойкость к атаке на основе адаптивно подобранных сообщений
Рассмотрим атаку на основе адаптивно подобранных сообщений.
Метод редукции в этом случае остается практически неизменным. Однако теперь Злоумышленнику, кроме запросов случайному оракулу, разрешается создавать qs подписанных сообщений. Следовательно, Саймон-имитатор должен, помимо ответов на запросы случайному оракулу, реагировать на подписанные запросы, причем эти ответы Злоумышленник может подвергать верификации с помощью алгоритма Verifypfc. Саймон должен делать это, даже несмотря на то, что у него нет ключа подписи. Именно эту часть информации он стремится получить с помощью Злоумышленника! Процедуру подписи Саймон имитирует.
Таким образом, нам достаточно показать, что в рамках модели ROM Саймон действительно удовлетворяет подписанные запросы Злоумышленника с высоким качеством.
Поскольку в алгоритме подписи используется функция хэширования, моделируемая случайным оракулом, для каждого запроса Л/, подписанного Злоумышленником, Саймон выбирает новый элемент г < р и создает запрос случайному оракулу (М, г) от имени Злоумышленника, а затем возвращает как ответ случайного оракула, так и подписанный ответ Злоумышленнику. Создание нового числа г для каждого нового запроса точно соответствует процедуре подписи. Саймон никогда не должен повторно использовать ни одно число г.
