Подсознательный канал можно организовать для любой схемы подписи [1458, 1460, 1406]. Описание протокола встраивания подсознательного канала в схемы Fiat-Shamir и Feige-Fiat-Shamir вместе с возможными злоупотреблениями можно найти в [485].
23.4 Неотрицаемые цифровые подписи
Автором этого алгоритма неотрицаемой подписи (см. раздел 4.3) является Дэвид Чаум (David Chaum) [343,327]. Сначала опубликовываются большое простое число р и примитивный элемент g, которые будут совместно использоваться группой подписывающих. У Алисы есть закрытый ключ х и открытый ключ gx mod p.
Чтобы подписать сообщение, Алиса вычисляет z = mx mod/;. Это все, что ей нужно сделать. Проверка подписи немного сложнее.
(1) Боб выбирает два случайных числа, аи Ь, меньшие/;, и отправляет Алисе: c = za(gxfmod p
(2) Алиса вычисляет t=xl mod (р-1), и отправляет Бобу: d = c'mod p
(3) Боб проверяет, что d = mag»(mod p)
Если это так, он считает подпись истинной.
Представим, что Алиса и Боб выполнили этот протокол, и Боб теперь считает, что Алиса подписала сообщение. Боб хочет убедить в этом Кэрол, поэтому он показывает ей запись протокола. Дэйв, однако, хочет убедить Кэрол, что документ подписан кем-то другим. Он создает поддельную запись протокола. Сначала он генерирует сообщение на этапе (1). Затем на этапе (3) он генерирует d и ложную передачу от другого человека на этапе (2).
Наконец, он создает сообщение этапа (2). Для Кэрол записи Боба и Дэйва одинаковы. Ее невозможно убедить в правильности подписи, пока она не выполнит протокол самостоятельно .
Конечно, если бы она следила из-за плеча Боба за тем, как он выполняет протокол, она была бы убеждена . Кэрол нужно увидеть выполнение этапов по порядку, так, как это делал Боб .
Используя эту схему подписи, можно столкнуться с проблемой, но я не знаю подробностей . Прежде, чем воспользоваться этой схемой, просмотрите литературу.
Другой протокол включает не только протокол подтверждения - Алиса может убедить Боба в правильности своей подписи - но и протокол отрицания. Алиса может с помощью интерактивного протокола с нулевым знанием убедить Боба, что ее подпись неправильна, если это так [329].
Как и предыдущий протокол группа подписывающих использует общедоступное большое простое число р и примитивный элемент g. У Алисы есть закрытый ключ х и открытый ключ gx mod p. Чтобы подписать сообщение, Алиса вычисляет z = тх mod/;. Чтобы проверить подпись:
(1) Боб выбирает два случайных числа, аиЬ, меньшие/;, и отправляет Алисе: c = mag»mod p
(2) Алиса выбирает случайное число q, меньшее/;, а затем вычисляет и отправляет Бобу: Sl = cgq mod/;, s2 = (cgqf mod/;
(3) Боб посылает Алисе аиЬ, чтобы Алиса могла убедиться, что Боб не мошенничал на этапе (1).
(4) Алиса посылает Бобу q, чтобы он мо воспользоваться тх и восстановить s и s2. Если Sl = cgq mod/;
s2 = {gx)b+qza{mod p)
то подпись правильна.
Алиса может также отказаться от подписи z под сообщением т. Подробности приведены в [329]. Дополнительные протоколы для неотрицаемых подписей можно найти в [584, 344]. Лейн Харн (Lein Ham) и Шубао Янг (Shoubao Yang) предложили схему групповых неотрицаемых подписей [700].
Преобразуемые неотрицаемые подписи
Алгоритм для преобразуемых неотрицаемых подписей,которые можно проверять, отменять и преобраз о-вывать в обычные неотрицаемые подписи, приведен в [213]. Он основан на алгоритме цифровых подписей Е1-Gamal.
Как и в ElGamal, сначала выбираются два простых числа, р и q, так, чтобы q было делителем рЛ. Теперь нужно создать число g, меньшее q. В диапазоне от 2 до р-l выбирается случайное число h и вычисляется
g=h<Tiyq mod p
Если g равно 1, выбирается другое случайное h. Если нет, используется полученное значение g.
Закрытыми ключами служат два различных случайных числа, х и z, меньшие q. Открытыми ключами являются р, q, g, y и и, где
y = gx mod p
u=gH mod p
Для вычисления преобразуемой неотрицаемой подписи сообщения т (которое в действительности является хэш-значением сообщения), сначала диапазоне от 1 до q- выбирается случайное число t. Затем вычисляется
T = gr mod p
и
m' = Ttzm mod q.
Теперь вычисляется обычная подпись ElGamal для т'. Выбирается случайное число R, меньшее р- и взаимно простое с ним. Затем вычисляется г = gR mod/; и, с помощью расширенного алгоритма Эвклида, вы-числяется s, для которого
т'= rx + Rs (mod q)
Подписью служат подпись ElGamal (r, s) и Т. Вот как Алиса подтверждает свою подпись Бобу:
(1) Боб генерирует два случайных числа, а и Ъ, и вычисляет с = Т^У mod/; и посылает результат Алисе.
(2) Алиса генерирует случайное число к и вычисляет hx = eg* mod/; и А2 = А^ mod/;, а затем посылает оба числа Бобу.
(3) Боб посылает Алисе аиЬ.
(4) Алиса проверяет, что с = Т^У mod/;. Она посьшает к Бобу.
(5) Боб проверяет, что Ai = 7i>"ag + mod/;, и что h2 ^уга/аи + mod/;.
Алиса может преобразовать все свои неотрицаемые подписи в обычные, опубликовав z. Теперь любой может проверить ее подпись без ее помощи.
Схемы неотрицаемых подписей можно объединить со схемами разделения секрета, создав распределенные преобразуемые неотрицаемые подписи[1235]. Кто-нибудь может подписать сообщение, а затем распределить возможность подтверждения правильности подписи. Он может, например, потребовать, чтобы в протоколе убеждения Боба в правильности подписи участвовали трое из пяти обладателей возможность подтверждения пр а-вильности. В [700, 1369] предложены улучшения, позволяющие отказаться от необходимости доверенного лица - распределителя.
23.5 Подписи, подтверждаемые доверенным лицом
Вот как Алиса может подписать сообщение, а Боб проверить его так, чтобы и Кэрол немного позже могла доказать Дэйву правильность подписи Алисы (см. раздел 4.4) [333].
Сначала опубликовываются большое простое число р и примитивный элемент g, которые будут совместно использоваться группой пользователей. Также опубликовывается и, произведение двух простых чисел. У Кэрол есть закрытый ключ z и открытый ключ h = gx mod p.
В этом протоколе Алиса может подписать т так, чтобы Боб мог проверить правильность ее подписи, но не мог убедить в этом третью сторону.
(1) Алиса выбирает случайное х и вычисляет
a = gx mo&p
b = hx mo&p
Она вычисляет хэш-значение т, Щт), и хэш-значение объединения аиЬ, Ща,Ь), а затем
j = (H(m)®H(a,b))m mod n
и посылает а, Ъ иу Бобу.
(2) Боб выбирает два случайных числа, s и t, меньших/;, и посылает Алисе c = gsh'mod p
(3) Алиса выбирает случайное q, меньшее р, и посылает Бобу d = gq mod p
e = (cdf mod p
(4) Боб посылает Алисе s и t.
(5) Алиса проверяет, что gsh' ss с (mod/;)
затем она посылает Бобу q.
(6) Боб проверяет
d = gq mo&p
e/aq ее asb' (mod/;)
(Щт) © H(a,b)) =//3 mod n
Если все тождества выполняются, то Боб считает подпись истинной .
Боб не может использовать запись этого доказательства для убеждения Дэйва в истинности подписи , но Дэйв может выполнить протокол с доверенным лицом Алисы, Кэрол. Вот как Кэрол убеждает Дэйва в том, что аиЬ образуют правильную подпись.
(1) Дэйв выбирает случайные и и v, меньшие/;, и посылает Кэрол ifc = gVmod/>
(2) Кэрол выбирает случайное w, , меньшее/;, и посылает Дэйву l = gw mod p
у = (klf mod p
(3) Дэйв посылает Кэрол и и v.
(4) Кэрол проверяет, что gV = ifc(mod/>)
Затем она посылает Дэйву w.
(5) Дэйв проверяет, что
gw = l (mod p)
y/hw = hubv (mod p)
Если все тождества выполняются, то Дэйв считает подпись истинной.
В другом протоколе Кэрол может преобразовать протокол доверенного лица в обычную цифровую подпись . Подробности в [333].
23.6 Вычисления с зашифрованными данными
Проблема дискретного логарифма
Существует большое простое число р и генератор g. Алиса хочет для конкретного х найти такое е, для которого
ge = x{mo&p)
Это трудная проблема, и Алисе не хватает вычислительных мощностей для вычисления результата . У Боба есть такие возможности - он представляет правительство, или мощный вычислительный центр, или еще какую-нибудь влиятельную организацию. Вот как Алиса может получить помощь Боба, не раскрыв ему х [547, 4]:
(1) Алиса выбирает случайное число г, меньшее/;.
(2) Алиса вычисляет x' = xgr mo&p
(3) Алиса просит Боба решить ge' = 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 = r2 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. Затем она вычисляет одно из двух значений:
у = hx то&р,м1шу = f тоАр
Она посылает >> Бобу.
(4) Боб пытается угадать, вычислила Алиса у как функцию h или как функцию t, и посылает свое предположение Алисе.
(5) Если догадка Боба правильна, результатом бросания монеты является "орел", в противном случае -"решка". Алиса объявляет результат броска монеты.
Подпротокол проверки:
(6) Алиса раскрывает Бобу значение х. Боб вычисляет hx mod p и f mod/;, убеждаясь, что Алиса играла чест
но и проверяя результат броска. Он также проверяет, что х ир-1 - взаимно простые числа.
Чтобы Алиса могла смошенничать, она должна знать два целых числа, х и х', для которых выполняется AW' mod p. Для того, чтобы узнать эти значения, ей нужно вычислить :
logth =х'хл mod/;-l и logth =хх'л modp-1.
Это трудные проблемы.
Алиса смогла бы сделать это, если бы она знала log,/z, но Боб выбирает h и t на этапе (2). У Алисы нет другого способа кроме, как попытаться вычислить дискретный логарифм . Алиса может также попытаться смошенничать, выбрав х, которое не является взаимно простым с р-l, но Боб обнаружит это на этапе (6).
Боб может смошенничать, если h и t не являются примитивными элементами в поле in GF(p), но Алиса сможет легко проверить это после этапа (2), так как ей известно разложение р-l на простые множители.
Удачным в этом протоколе является то, что если Алиса и Боб захотят бросить несколько монет, он7и смогут использовать одни и те же значения р, h и t. Алиса просто генерирует новое х, и протокол продолжается с этапа (3).