Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Посмотрим, что именно должен сделать Саймон. Для подписанного запроса М Саймон генерирует случайные числа и и v, которые меньше р — 1, и вычисляет следующие величины.
r *- 3V(modp);
s <--ru-1(modp — 1);
? *--rm>-1 (mod p — 1).
Саймон возвращает число ? в качестве ответа случайного оракула на запрос (М, г) и тройку (г, е, s) — в качестве подписи сообщения М (т.е. подписанный ответ на подписанный запрос М). Читатели могут убедиться, что возвращенная подпись действительно является корректной. Этот алгоритм имитации подписи точно совпадает с алгоритмом экзистенциальной подделки, описанным в разделе 10.4.7.2.
В рамках модели случайного оракула имитация подписи имеет точно такое же распределение, как и подпись, созданная алгоритмом, которая применяется случайным оракулом вместо функции хэширования Н. Вот почему Злоумышленник ничего не подозревает. Итак, "имитация обучения", обеспечиваемая Саймоном (см. рис. 16.1), имеет высокое качество, и Злоумышленник должен быть удовле-
612
Часть V. Методы формального доказательства стойкости
творен как подписанными ответами, так и ответами случайного оракула. Он должен проявить все свои способности, а метод редукции приведет нас к требуемому противоречию. Подведем итоги.
Теорема 16.1. Пусть (Gen(lfc), Sign, Verify) — одна из тройных схем цифровой подписи Эль-Гамаля, в которой простое число р удовлетворяет следующему условию: существует k-битовое простое число q, являющееся делителем числа р — 1, причем число (р — \)/q не имеет больших простых множителей. Если алгоритм атаки на основе адаптивно подобранных сообщений может взломать схему за время t(k) с преимуществом Adv(/c), то задачу о вычислении дискретного логарифма по модулю р можно решить за время t'(k) с преимуществом Adv'(/c), где
2(t(k) + qHr) + 0B{qsk3) * {k)~ AdvTfc) '
Adv L=-
Здесь qsu q — количество подписей и запросов оракулу Н соответственно, а величина т — время, необходимое оракулу Н для ответа на запрос. ?
Величина /с3 представляет собой количество битовых операций, необходимых для возведения в степень по /с-битовому модулю (эта оценка была выведена в разделе 4.3.2.6).
16.3.2.3 Выводы
• Вновь продемонстрирована мощь модели случайного оракула при доказательстве стойкости. Исследование стойкости тройной схемы цифровой подписи Эль-Гамаля показало следующее: если соответствующий алгоритм является действительно случайной функцией, то проще всего подделать подпись, вычислив дискретный логарифм, а затем повторяя действия автора сообщения. Этот результат аналогичен выводам, полученным при исследовании битовой стойкости в главе 9.
• Итак, доказательство стойкости, основанное на модели случайного оракула, демонстрирует, что наиболее уязвимым местом реальной схемы цифровой подписи является функция хэширования, если, коненчно, атакующий не придет к выводу, что атаковать функцию хэширования труднее, чем вычислить дискретный логарифм. Следовательно, основное внимание при разработке схемы цифровой подписи нужно уделить функции хэширования.
• Показано, что преимущество, с которым Саймон вычисляет дискретный логарифм, равно -^=, где qn — количество запросов случайному оракулу Н,
Глава 16. Сильная и доказуемая стойкость схем цифровой подписи
613
которые должен послать Злоумышленник. Для того чтобы Саймон мог вычислять дискретный логарифм с постоянным преимуществом, процесс редукции необходимо выполнить yfqn раз. Это увеличивает время работы Саймона до величины
2(* + №T) + 0B(<7s(logp)3)
^-Adv-•
Если функция хэширования вычисляется эффективно, разумно предложить фальсификатору вычислить ее 250 раз (см. раздел 15.2.5). Следовательно, в редукционном доказательстве Злоумышленнику разрешается сделать 250 запросов случайному оракулу. Иначе говоря, следует положить = = 250. В этом случае мы получим следующую оценку времени, которое понадобится Саймону для вычисления дискретного логарифма.
О
\AdvJ
Эта оценка означает, что процесс редукции не очень эффективен. Следовательно, полученное противоречие теряет смысл, если простое число р состоит из 1024 бит, а преимущество Adv мало. Однако, если простое число р состоит из 2048 бит, противоречие становится существенным. Несмотря на то что процесс редукции не имеет идеальной эффективности, метод ветвящейся редукции, предложенный Пойнтшевалем и Штерном, стал первым редукционным доказательством стойкости тройной схемы цифровой подписи Эль-Гамаля.
Ирония заключается в том, что доказательство неуязвимости против атаки на основе адаптивно подобранных сообщений, представляющей собой наиболее сильное понятие стойкости схем цифровой подписи, основано на предположении, что схема уязвима для экзистенциальной подделки. Однако эта ситуация отличается от доказательства стойкости схемы RSA-OAEP, изложенного в разделе 15.2.4, где в качестве открытого показателя степени алгоритма шифрования RSA, мы предложили использовать число три. Экзистенциальная уязвимость схемы цифровой подписи, использующей однонаправленные функции с секретом, не является существенной слабостью.
Несмотря на то что стандарт цифровой схемы DSS не является тройной схемой (функция хэширования получает на вход только битовую строку, а не сообщение и фиксатор), ее неуязвимость несложно доказать с помощью модели случайного оракула. Для этого достаточно предположить, что Саймон способен документировать все запросы случайному оракулу и запросы на подпись, связанные с определенным ключом. В этом случае на повторные
