Неотрицаемые цифровые подписи

Автором этого алгоритма неотрицаемой подписи (см. раздел 4.3) является Дэвид Чаум (David Chaum) [343,327]. Сначала опубликовываются большое простое число p и примитивный элемент g, которые будут совместно использоваться группой подписывающих. У Алисы есть закрытый ключ x и открытый ключ g^xmod p.

Чтобы подписать сообщение, Алиса вычисляет z= m^xmod p. Это все, что ей нужно сделать. Проверка подписи немного сложнее.

(1) Боб выбирает два случайных числа, aи b, меньшие p, и отправляет Алисе:

c = z^a(g^x)^b mod p

(2) Алиса вычисляет t=x^-1 mod (p-1), и отправляет Бобу:

d= c^t mod p

(3) Боб проверяет, что

d º m^ag^b(mod p)

Если это так, он считает подпись истинной.

Представим, что Алиса и Боб выполнили этот протокол, и Боб теперь считает, что Алиса подписала сообщение. Боб хочет убедить в этом Кэрол, поэтому он показывает ей запись протокола. Дэйв, однако, хочет убедить Кэрол, что документ подписан кем-то другим. Он создает поддельную запись протокола. Сначала он генерирует сообщение на этапе (1). Затем на этапе (3) он генерирует dи ложную передачу от другого человека на этапе (2). Наконец, он создает сообщение этапа (2). Для Кэрол записи Боба и Дэйва одинаковы. Ее невозможно убедить в правильности подписи, пока она не выполнит протокол самостоятельно.

Конечно, если бы она следила из-за плеча Боба за тем, как он выполняет протокол, она была бы убеждена. Кэрол нужно увидеть выполнение этапов по порядку, так, как это делал Боб.

Используя эту схему подписи, можно столкнуться с проблемой, но я не знаю подробностей. Прежде, чем воспользоваться этой схемой, просмотрите литературу.

Другой протокол включает не только протокол подтверждения - Алиса может убедить Боба в правильности своей подписи - но и протокол отрицания. Алиса может с помощью интерактивного протокола с нулевым знанием убедить Боба, что ее подпись неправильна, если это так [329].

Как и предыдущий протокол группа подписывающих использует общедоступное большое простое число p и примитивный элемент g. У Алисы есть закрытый ключ x и открытый ключ g^xmod p. Чтобы подписать сообщение, Алиса вычисляет z= m^xmod p. Чтобы проверить подпись:

(1) Боб выбирает два случайных числа, aи b, меньшие p, и отправляет Алисе:

c = m^ag^b mod p

(2) Алиса выбирает случайное число q, меньшее p, а затем вычисляет и отправляет Бобу:

s₁= cg^qmod p, s₂= (cg^q)^xmod p

(3) Боб посылает Алисе aи b, чтобы Алиса могла убедиться, что Боб не мошенничал на этапе (1).

(4) Алиса посылает Бобу q, чтобы он мо воспользоваться m^xи восстановить s₁и s₂. Если

s₁º cg^qmod p

s₂º (g^x)^b+qz^a (mod p)

то подпись правильна.

Алиса может также отказаться от подписи zпод сообщением m. Подробности приведены в [329]. Дополнительные протоколы для неотрицаемых подписей можно найти в [584, 344]. Лейн Харн (Lein Harn) и Шубао Янг (Shoubao Yang) предложили схему групповых неотрицаемых подписей [700].