Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
602
Часть V. Методы формального доказательства стойкости
16.2 Сильная стойкость схемы цифровой подписи
Введем необходимые определения.
Во-первых, будем представлять схему цифровой подписи в виде тройки (Gen, Sign, Verify), элементы которой определены в разделе 10.4 (определение 10.2). Поскольку защита схем цифровой подписи от подделок обеспечивается с помощью криптографических функций хэширования, будем считать, что в алгоритмах Sign и Verify используются одна или несколько сильных функций хэширования. Под сильной функцией хэширования подразумевается функция, имитирующая поведение случайного оракула (раздел 10.3.1.2). Действительно, все доказательства стойкости, приведенные в главе, основаны на модели случайного оракула (см. раздел 15.2.1).
Приведем определение атаки на основе адаптивно подобранных сообщений.
Определение 16.1 (Атака на основе адаптивно подобранных сообщений).
Пусть к — положительное целое число. Адаптивный алгоритм подделки цифровой схемы (Gen, Sign, Verify) представляет собой вероятностный алгоритм, время работы которого полиномиально зависит от параметра к. Он получает на вход открытый ключ рк, где (рк, sk) *—ц Gen(lfc), и пытается подделать подписи в соответствии с ключом рк. Фальсификатору разрешается посылать запросы и получать подписи на сообщениях, выбранных заранее. В ходе моделирования этого процесса фальсификатор получает доступ к алгоритмам подписи и хэширования, время работы которых полиномиально зависит от параметра к.
Фальсификатор осуществляет (t(k), Айу(к))-взлом схемы, если за время t(k) он с вероятностью Adv(fc) создает корректную подпись, т.е. пару сообщение-подпись (m, s), удовлетворяющую условию Verify^ (т, s) = True, где т — распознаваемое сообщение, созданное с помощью функции хэширования, используемой в схеме, но еще не поступавшее на вход алгоритма Sign. Здесь t(k) — полином, a Adv(fc) — значимая вечичина, зависящая от параметра к.
Понятие значимой величины приведено в разделе 4.6.
Мы упростили это определение, не включив в него два выражения, оценивающие количество подписей и хэшированных запросов, созданных фальсификатором. Обе оценки являются полиномиальными: поскольку фальсификатор представляет собой полиномиальный алгоритм, зависящий от параметра к, количество подписей и хэшированных запросов ограничено полиномом.
Определение 16.2 (Стойкая схема цифровой подписи). Схема цифровой подписи (Gen, Sign, Verify) называется (t(k), Adv(к))-стойкой, если не существует фальсификатора, способного осуществить (t(k), А<\\(к))-взлом схемы при всех Ъпстаточно больших параметрах к.
Глава 16. Сильная и доказуемая стойкость схем цифровой подписи
603
Определение 16.2 используется для доказательства стойкости схем цифровой подписи путем "сведения к противоречию". Предположим, что заданная цифровая схема допускает (t(k), Adv(fc))-B3.ioM, где t(k) — полином, a Adv(fc) — значимая величина. Мы построим редукцию, позволяющую перевести полином t{k) в полином t'(k), а величину Adv(fc) — в величину Adv'(fc) так, что трудноразрешимая задача, лежащая в основе схемы цифровой подписи, будет допускать (t'(k), Adv'(A;))-B3.4oM. Если процесс редукции достаточно эффективен, то значение t'(k) будет малым, а величина Adv'(Ar) близкой к величине Adv(fc), т.е. значимой. Следовательно, взлом цифровой схемы становится возможным, если трудноразрешимая задача допускает (*'(&), АсЬ/(А;))-решение, что считаете*! невозможным. Это противоречие доказывает стойкость схемы. Понятие эффективной редукции описано в разделе 15.2.5.
Как и в предыдущей главе, при доказательстве стойкости схем цифровой подписи с помощью редукции будет использоваться специальный агент Саймон-имитатор. Он будет играть роль объекта атаки, посылая атакующему алгоритму свои подписи, поставленные на полученные запросы. Для этого используется имитация оракула подписи. Для того чтобы фальсификатор проявил всю свою силу, имитируемый оракул подписи не должен отличаться от истинного автора подписи. Поскольку фальсификатор полиномиально ограничен, достаточно применить понятие полиномиальной неразличимости, введенное в определении 4.15 (раздел 4.7).
В оставшейся части главы фальсификатор называется Злоумышленником и является активным атакующим алгоритмом.
16.3 Сильная и доказуемая стойкости схем цифровой подписи Эль-Гамаля
Долгое время (1985-1996) после появления схемы цифровой подписи Эль-Гамаля (раздел 10.4.6) и его аналогов (например, схемы Шнорра, описанной в разделе 10.4.8.1, и схемы DSS, изученной в разделе 10.4.8.2) считалось, что сложность их подделки связана с вычислением дискретного логарифма в большой подгруппе конечного поля. Однако до 1996 года этот факт не был формально доказан.
Строгое доказательство этого факта было получено Пойнтшевалем и Штерном (Stern) [235]. Для этого они применили мощное средство: модель случайного оракула (ROM) [22]. Основные идеи, положенные в основу этой модели, представлены в разделе 15.2.1. Модель Пойнтшеваля и Штерна представляет собой остроумную конкретизацию общей модели случайного оракула.
