Наконец, он создает сообщение этапа (2). Для Кэрол записи Боба и Дэйва одинаковы. Ее невозможно убедить в правильности подписи, пока она не выполнит протокол самостоятельно .

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

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

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

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

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

c = magb mod p

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

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

(4)Алиса посылает Бобу q, чтобы он мо воспользоваться mx и восстановить s1 и s2. Если s1 = cgq mod p

S2 = (gx)b+qza (mod p) то подпись правильна.

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

Преобразуемые неотрицаемые подписи

Алгоритм для преобразуемых неотрицаемых подписей, которые можно проверять, отменять и преобраз о-вывать в обычные неотрицаемые подписи, приведен в [213]. Он основан на алгоритме цифровых подписей El-Gamal.

Как и в ElGamal, сначала выбираются два простых числа, p и q, так, чтобы q было делителем /7-1. Теперь нужно создать число g, меньшее q. В диапазоне от 2 до выбирается случайное число h и вычисляется

g=ht1)/q mod p

Если g равно 1, выбирается другое случайное h. Если нет, используется полученное значение g.

Закрытыми ключами служат два различных случайных числа , x и z, меньшие q. Открытыми ключами являются p q, g, y и и, где

y = gx mod p

M=g* mod p

Для вычисления преобразуемой неотрицаемой подписи сообщения m (которое в действительности является хэш-значением сообщения), сначала диапазоне от 1 до q-1 выбирается случайное число t. Затем вычисляется

T = gr mod p

m = Ttzm mod q.

Теперь вычисляется обычная подпись ElGamal для m. Выбирается случайное число R, меньшее и взаимно простое с ним. Затем вычисляется r = gR mod p и, с помощью расширенного алгоритма Эвклида, в ы-числяется s, для которого

m = rx + Rs (mod q)

Подписью служат подпись ElGamal (r, s) и T. Вот как Алиса подтверждает свою подпись Бобу:

(1)Боб генерирует два случайных числа, a и b, и вычисляет c = TTmagb mod p и посылает результат Алисе.

(2)Алиса генерирует случайное число k и вычисляет h1 = cgk mod p и h2 = h1z mod p, а затем посылает оба числа Бобу.

(3)Боб посылает Алисе a и b.

(4)Алиса проверяет, что c = TTmagb mod p Она посылает k Бобу.

(5)Боб проверяет, что h1 = TTmagb+k mod p, и что h2 = yrarsaub+k mod p

Алиса может преобразовать все свои неотрицаемые подписи в обычные, опубликовав z. Теперь любой может проверить ее подпись без ее помощи .

Схемы неотрицаемых подписей можно объединить со схемами разделения секрета, создав распределенные преобразуемые неотрицаемые подписи [1235]. Кто-нибудь может подписать сообщение, а затем распределить возможность подтверждения правильности подписи . Он может, например, потребовать, чтобы в протоколе уб е-ждения Боба в правильности подписи участвовали трое из пяти обладателей возможность подтверждения пр а-вильности. В [700, 1369] предложены улучшения, позволяющие отказаться от необходимости доверенного лица - распределителя.

23.5 Подписи, подтверждаемые доверенным лицом

Вот как Алиса может подписать сообщение, а Боб проверить его так , чтобы и Кэрол немного позже могла доказать Дэйву правильность подписи Алисы (см. раздел 4.4) [333].

Сначала опубликовываются большое простое число p и примитивный элемент g, которые будут совместно использоваться группой пользователей . Также опубликовывается n, произведение двух простых чисел. У Кэрол есть закрытый ключ z и открытый ключ h = gx mod p

В этом протоколе Алиса может подписать m так, чтобы Боб мог проверить правильность ее подписи, но не мог убедить в этом третью сторону.

(1)Алиса выбирает случайное x и вычисляет a = gx mod p

b = hx mod p

Она вычисляет хэш-значение m, H(m), и хэш-значение объединения a и b, H(a,b), а затем j = (H(m) © H(a,b))1/3 mod n и посылает a, b и j Бобу.

(2)Боб выбирает два случайных числа, s и t, меньших p и посылает Алисе c = gsht mod p

(3)Алиса выбирает случайное q, меньшее p, и посылает Бобу d = gq mod p

e = (cd)x mod p

(4)Боб посылает Алисе s и t.

(5)Алиса проверяет, что gsht - c (mod p)

затем она посылает Бобу q.

(6)Боб проверяет d - gq mod p

e/aq - asbt (mod p)

(H(m) © H(a,b)) = j1/3 mod n

Если все тождества выполняются, то Боб считает подпись истинной .

Боб не может использовать запись этого доказательства для убеждения Дэйва в истинности подписи , но Дэйв может выполнить протокол с доверенным лицом Алисы, Кэрол. Вот как Кэрол убеждает Дэйва в том, что a и b образуют правильную подпись.

(1)Дэйв выбирает случайные и и v, меньшие p и посылает Кэрол k = guav mod p

(2)Кэрол выбирает случайное w, , меньшее p и посылает Дэйву l = gw mod p

y = (k/)z mod p

(3)Дэйв посылает Кэрол и и v.

(4)Кэрол проверяет, что g"av = k (mod p)

Затем она посылает Дэйву w.

(5)Дэйв проверяет, что gw = / (mod p)

y/hw = h"bv (mod p)

Если все тождества выполняются, то Дэйв считает подпись истинной.

В другом протоколе Кэрол может преобразовать протокол доверенного лица в обычную цифровую подпись . Подробности в [333].

23.6Вычисления с зашифрованными данными

Проблема дискретного логарифма

Существует большое простое число p и генератор g. Алиса хочет для конкретного x найти такое e, для которого

ge = x (mod p)

Это трудная проблема, и Алисе не хватает вычислительных мощностей для вычисления результата . У Боба есть такие возможности - он представляет правительство, или мощный вычислительный центр, или еще какую-нибудь влиятельную организацию. Вот как Алиса может получить помощь Боба, не раскрыв ему x [547, 4]:

(1)Алиса выбирает случайное число r, меньшее p

(2)Алиса вычисляет x = xgr mod p

(3)Алиса просит Боба решить ge = x (mod p)

(4)Боб вычисляет e и посылает его Алисе.

(5)Алиса восстанавливает e, вычисляя e = (e - r) mod (p - 1)

Аналогичные протоколы для проблем квадратичных остатков и примитивных корней приведены в [3, 4]. (См. также раздел 4.8.)

23.7Бросание "честной" монеты

Следующие протоколы позволяют Алисе и Бобу бросать честную монету в сети передачи данных (см. раздел 4.9) [194]. Это пример бросания монеты в колодец (см. раздел 4.10). Сначала только Боб узнает результат броска и сообщает его Алисе . Затем Алиса может проверить, что Боб сообщил правильный результат броска .

Бросание "честной"монеты с помощью квадратных корней

Подпротокол бросания честной монеты :

(1)Алиса выбирает два больших простых числа, p и q, и посылает их произведение n Бобу.

(2)Боб выбирает случайное положительное целое число r, меньшее n/2. Боб вычисляет z = r2 mod n