t=(t1* t2* t3* t4* t5) mod ,p

Если это так, KDC признает открытый ключ.

В этот момент KDC знает, что у каждого доверенного лица есть правильная часть, и что они при необход и-мости смогут восстановить закрытый ключ. Однако ни KDC, ни любые четыре доверенных лица не могут восстановить закрытый ключ Алисы.

Работы Микали [1084, 1085] также содержат последовательность действия для создания честного RSA и для объединения пороговой схемы с честной криптосистемой , позволяющей m доверенным лицам из n восстановить закрытый ключ.

Отказоустойчивая схема Diffie-Hellman

Как и в предыдущем протоколе у группы пользователей есть общие простое число p и генератор g. Закрытым ключом Алисы является s, а ее открытым ключом t = gs mod p.

(1) KDC выбирает случайное число B из диапазона от 0 до p-2 и вручает B с помощью протокола вручения битов (см. раздел 4.9).

Алиса выбирает случайное число A из диапазона от 0 до p-2. Она пос1лает KDC gA mod p.

(2) Пользователь "разделяет" A с каждым доверенным лицом, используя схему подтверждаемого совместного использования секрета (см. раздел 3.7).

(3) KDC раскрывает B Алисе.

(4) Алиса проверяет вручение этапа (1). Затем она устанавливает свой открытый ключ равным t = gA gB mod p

а закрытый ключ равным s = (A + B) mod (p-1)

Доверенные лица могут восстановить A. Так как KDC знает B, этого достаточно для восстановления s. И Алиса не сможет использовать никаких подсознательных каналов для передачи несанкционированной информации. Этот протокол, рассмотренный в [946, 833] в настоящее время патентуется.

23.11 ZERO-KNOWLEDGE PROOFS OF KNOWLEDGE

Доказательство с нулевым знанием для дискретного логарифма

Пегги хочет доказать Виктору, что ей известно x, являющееся решением

Ax - B (mod p)

где p - простое число, а x - произвольное число, взаимно простое с p-1. Числа A, B и p общедоступны, а x хранится в секрете. Вот как Пегги, не раскрывая значения x, может доказать, что оно ей известно (см. раздел 5.1) [338, 337].

(1) Пегги генерирует t случайных чисел, rl, r2, . . . rt, причем все Г; меньше p-1.

(2) Пегги вычисляет h; = Ar mod p для всех значений , и пос1лает их Виктору.

(3) Пегги и Виктор, воспользовавшись протоколом бросания монеты генерируют t битов: b1, b2, . . . bt.

(4) Для всех t битов Пегги выполняет одну из следующих операций :

a) Если b, = 0, она посылает Виктору r,

b) Если b; = 1, она посылает Виктору s; = (г; - Г/) mod (p-1), где j - наименьшее значение индекса, при котором bj = 1

(5) Для всех t битов Виктор проверяет одно из следующих условий:

a) При b; = 0 что Ar - h; (mod p)

b) При b,- = 1 что As - h,-hj-1 (mod ,p)

(6) Пегги пос1лает Виктору Z, где Z = (x - Г/) mod (p-1)

(7) Виктор проверяет, что AZ - Bh/-1 (mod p)

Вероятность удачного мошенничества Пегги равна 1/2.

Доказательство с нулевым знанием для возможности вскрыть RSA

Алиса знает закрытый ключ Кэрол. Может быть она взломала RSA, а может она взломала дверь квартиры Кэрол и выкрала ключ. Алиса хочет убедить Боба, что ей известен ключ Кэрол. Однако она не хочет ни сообщать Бобу ключ, ни даже расшифровать для Боба одно из сообщений Кэрол . Далее приведен протокол с нулевым знанием, с помощью которого Алиса убеждает Боба, что она знает закрытый ключ Кэрол [888]. Пусть открытый ключ Кэрол - e, ее закрытый ключ - d, а модуль RSA - n.

(1) Алиса и Боб выбирают случайное k и т, для которых km = e (mod n)

Числа они должны выбирать случайным образом, используя для генерации k протокол бросания монеты, а затем вычисляя m. Если и k, и m больше 3, протокол продолжается. В противном случае числа выбираются заново.

(2) Алиса и Боб генерируют случайный шифротекст C. И снова они должны воспользоваться протоколом бр о-сания монеты.

(3) Алиса, используя закрытый ключ Кэрол, вычисляет M = Cd mod n

Затем она вычисляет

X = Mk mod n

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

(4) Боб проверяет, что X*" mod n = C. Если это так, то он убеждается в правильности заявления Алисы .

Аналогичный протокол можно использовать для демонстрации возможности вскрытия проблемы дискретн ого логарифма [888].

Доказательство с нулевым знанием того, что n является числом Блюма

Пока неизвестно никаких действительно практичных доказательств того, что n =pq, где p и q - простые числа, конгруэнтные 3 по модулю 4. Однако если n имеет форму prqs, где r и s нечетны, то у числа n сохраняются свойства, которые делают числа Блюма полезными для криптографии . И тогда существует доказательство с нулевым знанием того, что n имеет такую форму.

Предположим, что Алисе известно разложение на множители числа Блюма n, где n обладает рассмотренной выше формой. Вот как она может доказать Бобу, что n имеет такую форму [660].

(1) Алиса посылает Бобу число м, чей символ Якоби равен -1 по модулю n.

(2) Алиса и Боб совместно выбирают случайные биты: b1, b2, . . . bk.

(3) Алиса и Боб совместно выбирают случайные числа: x1, x2, . . . xk.

(4) Для каждого i = 1, 2, . . . k Алиса пос1лает Бобу квадратный корень по модулю n для одного из четырех чисел: xi, -xi, Mxi, - Mxi. Символ Якоби квадратного корня должен быть равен bi.

Вероятность удачного мошенничества Алисы равна 1/2k.

23.12 Слепые подписи

Понятие слепых подписей (см. раздел 5.3) было придумано Дэвидом Чаумом (David Chaum) [317, 323], который также предложил и первую реализацию этого понятия [318]. Она использует алгоритм RSA.

У Боба есть открытый ключ e, закрытый ключ d и открытый модуль n. Алиса хочет, чтобы Боб вслепую, не читая, подписал сообщение т.

(1) Алиса выбирает случайное число k из диапазона от 1 до n. Затем она маскирует т, вычисляя t = mke mod n

(2) Боб подписывает t td = (mke)d mod n

(3) Алиса снимает маскировку с td, вычисляя

s = td/k mod n (4) Результатом является s = md mod n

Это можно легко показать

td - (mke)d - mdk (mod n), поэтому td/k = mdk/k - md (mod n).

Чаум придумал целое семейство более сложных алгоритмов слепой подписи [320, 324], называемых неожиданными слепыми подписями. Схемы этих подписей сложнее, но они дают больше возможностей .

23.13 Передача с забыванием

В этом протоколе, предложенном Майклом Рабином (Michael Rabin) [1286], Алиса с вероятностью 50 процентов удается передать Бобу два простых числа, p и q. Алиса не знает, успешно ли прошла передача (См. раздел 5.5.) (Этот протокол можно использовать для передачи Бобу любого сообщения с 50-процентной вероятностью успешной передачи, если p и q раскрывают закрытый ключ RSA.)

(1) Алиса посылает Бобу произведение двух простых чисел: n = pq.

(2) Боб выбирает случайное число x, меньшее n и взаимно простое с n. Он посылает Алисе: a = x2 mod n

(3) Алиса, зная p и q, вычисляет четыре квадратных корня a: x, n-x, у и n-у. Она случайным образом выбирает любой из этих корней и посылает его Бобу.

(4) Если Боб получает у или n-у, он может вычислит наибольший общий делитель x+у и n, которым будет либо p, либо q. Затем, конечно же, n ; = q. Если Боб получает x или n-x, он не может ничего вычислить.

У этого протокола может быть слабое место : возможна ситуация, когда Боб может вычислить такое число a, что при известном квадратном корне a он сможет все время раскладывать n на множители.

23.14 Безопасные вычисления с несколькими участниками

Этот протокол взят из [1373]. Алиса знает целое число а Боб - целое число j. Алиса и Боб вместе хотят узнать, что правильно - ,</ или ,>/, но ни Алиса, ни Боб не хочет раскрыть свое число партнеру. Этот особый случай безопасных вычислений с несколькими участниками (см. раздел 6.2) иногда называют проблемой миллионера Яо [162, 7].

В приводимом примере предполагается, что , и j выбираются из диапазона от 1 до 100. У Боба есть открытый и закрытый ключи.

(1) Алиса выбирает большое случайное число x и шифрует его открытым ключом Боба. c = Eb(x)

(2) Алиса вычисляет c-j и посылает результат Бобу.

(3) Боб вычисляет следующие 100 чисел: yu = DB(c-,+u), для 1<u<100

DB обозначает дешифрирование закрытым ключом Боба.

Он выбирает большое случайное число p. (Размер p должен быть немного меньше x. Боб не знает x, но Алиса может легко сообщить ему размер x.) он вычисляет следующие 100 чисел:

zu = (yu mod p), для 1<u<100

Далее он проверяет, что для всех uv

zu - zj > 2

и что для всех u

0 < zu < /7-1

Если это не так, то Боб выбирает другое простое число и пробует снова.

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

zl, z2, . . . z/, zj+1 + 1, zj+2+1, . . . z100+1, P