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

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

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

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

(5) Боб проверяет, что 1 = 7Tmagb+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

затем она посылает Бобу 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, и пос1лает Кэрол k = g"av mod p

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

y = (k/)z mod p

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

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

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

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

y/hw = h"bv (mod

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

В другом протоколе Кэрол может преобразовать протокол доверенного лица в обычную цифровую подпись . Подробности в [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

(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 = г2 mod n

и посылает z Алисе.

(3) Алиса вычисляет четыре квадратных корня z (mod n). Она может сделать это, так как она знает разложение n на множители. Назовем их +x, -x, +y и -y. Обозначим как x меньшее из следующих двух чисел:

x mod n

-x mod n

Аналогично, обозначим как у меньшее из следующих двух чисел: y mod n -у mod n

Обратите внимание, что r равно либо x, либо y.

(4) Алиса делает пытается угадать, какое из значений равно r - x или у, и пос1лает свою догадку Бобу.

(5) Если догадка Алисы правильна, результатом броска монеты является "орел", а если неправильна -"решка". Боб объявляет результат броска монеты.

Подпротокол проверки:

(6) Алиса посылает p и q Бобу.

(7) Боб вычисляет x и y и посылает их Алисе.

(8) Алиса вычисляет r.

У Алисы нет возможности узнать r, поэтому она действительно угадывает. Она на этапе (4) сообщает Бобу только один бит своей догадки, не давая Бобу получить и x, и y. Если Боб получит оба этих числа, он сможет изменить r после этапа (4).

Бросание "честной" монеты с помощью возведения в степень по модулюp

В этом протоколе в качестве однонаправленной функции используется возведение в степень по модулю пр о-стого числа p [1306]:

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

(1) Алиса выбирает простое число p так, чтобы множители p-1 были известны, и среди них было по крайней мере одно большое простое число.

(2) Боб выбирает два примитивных элемента, h и t, в GF(p). Он посылает их Алисе.

(3) Алиса убеждается, что h и t являются примитивными элементами, и затем выбирает случайное число x, взаимно простое с p-1. Затем она вычисляет одно из двух значений:

у = hx mod p, или у = tx mod p

Она посылает y Бобу.

(4) Боб пытается угадать, вычислила Алиса у как функцию h или как функцию t, и посылает свое предположение Алисе.

(5) Если догадка Боба правильна, результатом бросания монеты является "орел", в противном случае -"решка". Алиса объявляет результат броска монеты.

Подпротокол проверки:

(6) Алиса раскрывает Бобу значение x. Боб вычисляет hx mod p и tx mod p, убеждаясь, что Алиса играла честно и проверяя результат броска. Он также проверяет, что x и p-1 - взаимно простые числа.

Чтобы Алиса могла смошенничать, она должна знать два целых числа, x и x, для которых выполняется hx-tx mod p. Для того, чтобы узнать эти значения, ей нужно вычислить :

logth =xx-1 mod p-1 и logth =xx-1 mod p-1.

Это трудные проблемы.

Алиса смогла бы сделать это, если бы она знала logth, но Боб выбирает h и t на этапе (2). У Алисы нет другого способа кроме, как попытаться вычислить дискретный логарифм . Алиса может также попытаться смоше н-ничать, выбрав x, которое не является взаимно простым с p-1, но Боб обнаружит это на этапе (6).

Боб может смошенничать, если h и t не являются примитивными элементами в поле in GF(p), но Алиса сможет легко проверить это после этапа ( 2), так как ей известно разложение p-1 на простые множители.