Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
604 Часть V. Методы формального доказательства стойкое*
16.3.1 Тройная схема цифровой подписи Эль-Гамаля
Рассмотрим типичный вариант схемы цифровой подписи Эль-Гамаля, неуязвимость которого доказана с помощью модели ROM. В этом варианте на вход схемы поступает ключ подписи sfc, открытый ключ рк и сообщение М, представляющее собой строку бит, а результатом ее работы является подпись сообщения М. представляющая собой тройку (г, е, s).
• Компонент г называется фиксатором (commitment). Он фиксирует эфемерное целое число ?, называемое передачей (committal). Это число не зависни от величин, использованных при создании предыдущих подписей. Обычно фиксатор выглядит как г = ge(modp), где д и р — часть открытых параметр ров схемы цифровой подписи.
• Компонент е представляет собой криптографическую функцию хэширова-1 ния Я(М,г).
• Компонент s называется подписью. Он представляет собой линейную функ-1 цию, зависящую от фиксатора г, передачи ?, сообщения М, функции хэшгя рования Я() и закрытого ключа подписи sk.
Такая схема цифровой подписи называется тройной (triplet signature scheme).
Исходная схема цифровой подписи Эль-Гамаля, описанная алгоритмом 10.3,] не является тройной, поскольку в ней не используется функция хэширования, и она уязвима для экзистенциальной подделки. Однако вариант схемы Эль-Гамаля, в котором используется функция хэширования (см. раздел 10.4.7.2), становится стойким к экзистенциальной подделке и может классифицироваться как тройная схема.
Схема цифровой подписи Шнорра (алгоритм 10.4) также является тройной. Подпись сообщения М, созданная этим алгоритмом, представляет собой тройку (г, е, s), где е = Я(М, г), причем Я — некая функция хэширования. Следует отметить, что в схеме Шнорра нет необходимости посылать величину г верификатору, поскольку ее можно вычислить как gsye.
Опишем метод редукции, примененный Пойнтшевалем и Штерном для доказательства неуязвимости тройной схемы цифровой подписи. Этот метод называется ветвящейся редукцией (forking reduction).
16.3.2 Ветвящаяся редукция
Как показано в разделе 10.4.7.1, многократное использование эфемерного ключа (передачи ? или фиксатора г) в схеме цифровой подписи Эль-Гамаля приводит к раскрытию секретного ключа подписи. Компрометация закрытого ключа подписи сводится к эффективному решению трудноразрешимой задачи: вычисления дискретного логарифма открытого ключа в группе по модулю, являющемуся большим простым числом.
Глава 16. Сильная и доказуемая стойкость схем цифровой подписи
605
Доказательство стойкости тройной схемы Эль-Гамаля основано на повторной передаче фиксатора, предназначенной для раскрытия секретного ключа. Поскольку фальсификация подписи эффективно сводится к неразрешимой задаче — вычислению дискретного логарифма (предположение 8.2 в разделе 8.4), корректность доказательства зависит от эффективности процесса редукции.
В редукционном доказательстве стойкости тройной схемы Эль-Гамаля функция хэширования описывается с помощью случайного оракула (random oracle — RO), поведение которого рассмотрено в разделе 10.3.1.2. В модели ROM все случайные оракулы имитируются Саймоном. Кроме того, Саймон способен имитировать процедуру подписи и таким образом отвечать на запросы Злоумышленника. Итак, Саймон-имитатор может организовать для Злоумышленника курс обучения, необходимый для подготовки к фальсификации подписи. Следовательно, чтобы достичь успеха, Злоумышленник должен легко обучаться и создавать фальшивые подписи со значимой вероятностью. Саймон может использовать фальшивую подпись для решения трудноразрешимой задачи. В случае тройной схемы Эль-Гамаля этой задачей является вычисление дискретного логарифма в конечном поле. Процесс редукции проиллюстрирован на рис. 16.3.2.1.
В следующих двух разделах при описании процесса редукции широко используются интуитивные рассуждения. Приведенные оценки вероятности можно считать верхними границами точных оценок Пойнтшеваля и Штерна. Несмотря на это, при достаточно крупном параметре безопасности их можно использовать для констатации противоречия. Читатели, которых не устраивает такой уровень точности, могут обратиться непосредственно к работе [236].
16.3.2.1 Стойкость к неадаптивной атаке
Для начала рассмотрим стойкость тройной схемы Эль-Гамаля к неадаптивной атаке.
Пусть (Gen(lfc), Sign, Verify) — тройная схема цифровой подписи Эль-Гамаля (т.е. вариант алгоритма 10.3), в которой простое число р удовлетворяет следующему условию: существует А;-битовое простое число q, являющееся делителем числа р — 1, причем число (р — l)/q не имеет больших простых множителей.
Допустим, что Злоумышленник — успешный фальсификатор подписей в схеме (Gen(lfc), Sign, Verify), а Саймон-имитатор контролирует все каналы, связывающие Злоумышленника с внешним миром, как показано на рис. 16.1. Однако в рамках неадаптивной атаки Злоумышленник не проходит "курс обучения подделке подписи", поскольку он никогда не запрашивает образец подписи.
Саймон генерирует случайное число y€Z*. Его цель — вычислить дискретный логарифм числа у с базой, представляющей собой порождающий элемент д по модулю р, т.е. найти число х, удовлетворяющее условию у = ^(modp). Саймон использует Злоумышленника как "черный ящик", так что удачная подделка новой подписи на заранее подобранном сообщении предоставляет Саймону достаточно
