Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Шнайер - Прикладная криптография.doc
Скачиваний:
13
Добавлен:
01.05.2025
Размер:
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

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

ti = mod p, для i = 1, . . . 5.

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

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

  2. Каждое доверенное лицо проверяет, что

ti = mod p

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

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

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

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

  2. KDC раскрывает B Алисе.

  3. Алиса проверяет вручение этапа (1). Затем она устанавливает свой открытый ключ равным

t = gA gB mod p

а закрытый ключ равным

s = (A + B) mod (p-1)

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

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 меньше p-1.

  2. Пегги вычисляет hi = 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

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

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

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

  1. Пегги посылает Виктору Z, где

Z = (x - rj) mod (p-1)

  1. Виктор проверяет, что AZ Bhj-1 (mod p)

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