2212 © 342=2546

Кэрол вычисляет S2, выполняя XOR B2 и второго числа, полученного ей от Алисы. 1988 © 1555 = 471

Протокол работает для любого количества покупателей . Если Боб, Кэрол и Дэйв хотят купить секреты, Алиса выдает каждому покупателю два открытых ключа, по одному на каждого другого покупателя . Каждый покупатель получает набор чисел от каждого другого покупателя . Затем они выполняют протокол с Алисой для каждого из своих наборов номеров и выполняют XOR всех полученных от Алисы результатов, получая свои секр е-ты. Более подробно это описано в [1374, 1175].

К сожалению, пара нечестных участников могут смошенничать . Алиса и Кэрол, действуя на пару, могут легко понять, какой секрет получил Боб : если они знают FBI Cb и алгоритм шифрования Боба, они могут подыскать такое b, что у Cb будет правильный FBI. А Боб и Кэрол, действуя вместе, могут легко заполучить все секреты Алисы.

Если вы считаете, что участники честны, можно использовать протокол попроще [389].

(1)Алиса шифрует все секреты RSA и посылает их Бобу: С,- = S,e mod n

(2)Боб выбирает свой секрет Cb, генерирует случайное число r и посылает Алисе. С = Cbre mod n

(3)Алиса посылает БобуЛ P = С4 mod n

(4)Боб вычисляет P Sb = Pr-1 mod n

Если участники могут жульничать, Боб может доказать с нулевым знанием, что он знает некоторое r, такое что C = Cbre mod n, и хранить в b секрете, пока Алиса не передаст ему на этапе (3) P [246).

23.10 Честные и отказоустойчивые криптосистемы

Честная схема Diffie-Hellman

Честные криптосистемы представляют собой программный способ условного вручения документов (см. раздел 4.14). Этот пример взят из работ Сильвии Микали (Silvia Micali) [1084, 1085]. Он запатентован [1086, 1087].

В базовой схеме Diffie-Hellman группа пользователей использует общее простое число p и генератор g. Закрытым ключом Алисы является s, а ее открытым ключом t = gs mod p Вот как сделать схему Diffie-Hellman честной (в этом примере используется пять доверенных лиц ).

(1)Алиса выбирает пять целых чисел, s1, s2, s3, s4, s5, меньших p-1. Закрытым ключом Алисы является s = (s1+ s2+ s3+ s4+ s5) mod p-1

а ее открытым ключом t = gs mod p

Алиса также вычисляет

t; =gs modp, для , = 1, . . . 5.

Открытыми частями Алисы являются t,, а закрытыми - s,.

(2)Алиса посылает закрытую и соответствующую открытую части каждому доверенному лицу . Например, она посылает s1 и t2 доверенному лицу 1. Она посылает t в KDC.

(3)Каждое доверенное лицо проверяет, что t,- = gs mod ,p

Если это так, доверенное лицо подписывает t, и посылает его в KDC. Доверенное лицо сохраняет s, в безопасном месте.

(4)Получив все пять открытых частей , KDC проверяет, что

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 до /7-2 и вручает B с помощью протокола вручения битов (см. раздел 4.9).

Алиса выбирает случайное число A из диапазона от 0 до p-2. Она посылает 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, причем все ri меньше р1.

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

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

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

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

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

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

a)При bi = 0 что Ar - hi (mod p

b)При bi = 1 что Asi - hihj-1 (mod p

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

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

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

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

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

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

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

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

(3)Алиса, используя закрытый ключ Кэрол, вычисляет M = C 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)Для каждого , = 1, 2, . . . k Алиса посылает Бобу квадратный корень по модулю n для одного из четырех чисел: xb -xb uxb - ux;. Символ Якоби квадратного корня должен быть равен b;.

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

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

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

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

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

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

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