Другие схемы

Подсознательный канал можно организовать для любой схемы подписи [1458, 1460, 1406]. Описание прото­кола встраивания подсознательного канала в схемы Fiat-Shamir и Feige-Fiat-Shamir вместе с возможными зло­употреблениями можно найти в [485].

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

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

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

(1) Боб выбирает два случайных числа, аи Ь, меньшие/;, и отправляет Алисе: c = z^a(g^xfmod p

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

(3) Боб проверяет, что d = m^ag»(mod p)

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

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

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

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

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

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

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

(1) Боб выбирает два случайных числа, аиЬ, меньшие/;, и отправляет Алисе: c = m^ag»mod p

(2) Алиса выбирает случайное число q, меньшее/;, а затем вычисляет и отправляет Бобу: _Sl = cg^q mod/;, s₂ = (cg^qf mod/;

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

(4) Алиса посылает Бобу q, чтобы он мо воспользоваться т^х и восстановить s и s₂. Если _Sl = cg^q mod/;

s₂ = {g^x)^b+qz^a{mod p)

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

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

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

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

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

g=h<T^iyq mod p

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

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

y = g^x mod p

u=g^H mod p

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

T = g^r mod p

и

m' = Ttzm mod q.

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

т'= rx + Rs (mod q)

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

(1) Боб генерирует два случайных числа, а и Ъ, и вычисляет с = Т^У mod/; и посылает результат Алисе.

(2) Алиса генерирует случайное число к и вычисляет h_x = eg* mod/; и А₂ = А^ mod/;, а затем посылает оба числа Бобу.

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

(4) Алиса проверяет, что с = Т^У mod/;. Она посьшает к Бобу.

(5) Боб проверяет, что Ai = 7^i>"^ag ⁺ mod/;, и что h₂ ^у^га/^аи ⁺ mod/;.

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

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

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

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

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

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

(1) Алиса выбирает случайное х и вычисляет
a = g^x mo&p

b = h^x mo&p

Она вычисляет хэш-значение т, Щт), и хэш-значение объединения аиЬ, Ща,Ь), а затем

j = (H(m)®H(a,b))^m mod n

и посылает а, Ъ иу Бобу.

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

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

e = (cdf mod p

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

(5) Алиса проверяет, что g^sh' ss с (mod/;)

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

(6) Боб проверяет
d = g^q mo&p

e/a^q ее a^sb' (mod/;)

(Щт) © H(a,b)) =/^/3 mod n

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

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

(1) Дэйв выбирает случайные и и v, меньшие/;, и посылает Кэрол ifc = gVmod/>

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

у = (klf mod p

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

(4) Кэрол проверяет, что gV = ifc(mod/>)

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

(5) Дэйв проверяет, что
g^w = l (mod p)

y/h^w = h^ub^v (mod p)

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

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

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

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

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

g^e = x{mo&p)

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

(1) Алиса выбирает случайное число г, меньшее/;.

(2) Алиса вычисляет x' = xg^r mo&p

(3) Алиса просит Боба решить g^e' = x'{mo&p)

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

(5) Алиса восстанавливает е, вычисляя

e = (e' - r) mod (p - 1)

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

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

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

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

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

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

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

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

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

x mod n

-х mod n

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

уто&п

-у mod n

Обратите внимание, что г равно либо х', либо у'.

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

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

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

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

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

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

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

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

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

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

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

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

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

у = h^x то&р,м1шу = f тоАр

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

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

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

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

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

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

log_th =х'х^л mod/;-l и log_th =хх'^л modp-1.

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

Алиса смогла бы сделать это, если бы она знала log,/z, но Боб выбирает h и t на этапе (2). У Алисы нет дру­гого способа кроме, как попытаться вычислить дискретный логарифм . Алиса может также попытаться смошен­ничать, выбрав х, которое не является взаимно простым с р-l, но Боб обнаружит это на этапе (6).

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

Удачным в этом протоколе является то, что если Алиса и Боб захотят бросить несколько монет, он7и смогут использовать одни и те же значения р, h и t. Алиса просто генерирует новое х, и протокол продолжается с этапа (3).